mersenneforum.org Pick and Choose
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2003-07-14, 19:41 #1 Wacky     Jun 2003 The Texas Hill Country 32·112 Posts Pick and Choose Here's another strategy game for you to analyze. Two players make a single line of twelve tokens. They could be dominoes, coins, or whatever. They are placed so that each token (except the two end tokens) touches each of its two neighbors, and no other. Now, one of the end tokens is moved away a bit so that there are two lines. The first contains one token and the second contains all the rest. The players take turns removing the tokens. In each turn, a player must take either one token or two. However, if he takes two, they must be touching neighbors. No tokens are ever moved except when they are removed. For clarification, if the tokens are taken from the end of a line, the line gets shorter (or disappears). If they are taken from any interior place in the line, that line is divided into two lines by the gap left by the tokens removed. The objective is to remove the last token. Is there a winning strategy for either player? If so, what is the strategy?
 2003-07-14, 21:06 #2 alienz   Jun 2003 3×7 Posts http://world.std.com/~reinhold/math/nim.html The answer is here,
 2003-07-14, 21:24 #3 Wacky     Jun 2003 The Texas Hill Country 32·112 Posts Sorry, Nim is a different game. Please reread the rules.
 2003-07-14, 23:15 #4 Orgasmic Troll Cranksta Rap Ayatollah     Jul 2003 641 Posts I have been approaching this problem in a less than graceful manner, namely, working backwards from winning positions (i.e. *, **) representing the possible positions at n as partitions of n. So far (assuming I haven't made an error .. that would suck), I have gotten up through 9 pieces, and the positions where the next player will lose with optimal playing on both sides is 8+1, 6+3, 6+2+1, 5+3+1, 4+1+1+1+1+1, and 3+3+3 for eight pieces left, the losing positions are 4+4, 4+2+2, 3+2+1+1+1, 2+2+2+2, 2+2+1+1+1+1, and 1+1+1+1+1+1+1+1 This was much more manageable at 5 pieces :) I suppose I could keep on going until I exhaust the possibilities at 10 and 11 pieces left, but I still don't have a really graceful definition of the optimal strategy.
 2003-07-15, 00:16 #5 Maybeso     Aug 2002 Portland, OR USA 27410 Posts Travis, Ive been trying to do the same, with not much more luck. :? Something that might help you is to eliminate "good" positions that the previous player wouldn't give to you. ie. The final winning position of **. The possible positions before that are (I think): [code:1] ***, ****, ** *, and ** ** which a good player would make **, ** *, * *, and ** * respectively. [/code:1]Notice that only the first one, ***, leads to your result, and based on its previous positions, it can be avoided by a good player. (again, I think) So it should be pruned from your search. The only winning stratagy I can think of is: 1. Reduce the game to an even number of lines of one or two tokens each. 2. Always leave an even number of lines of one or two tokens each. The trick is how to complete step 1 while preventing your opponent from doing so. ;)
 2003-07-16, 20:02 #6 c00ler   Jul 2003 110012 Posts The first one wins! hints: 1)first move - make 1+3+7 2)one, who makes a+a+b+b+a+a (symmetrical position), loses P.S. If objective is not to remove the last token then the first wins too. And first winning moves are 1+3+7 and 1+5+5 P.P.S. It's much harder to analyse the game with modified rules; it's solution is much longer.

 Similar Threads Thread Thread Starter Forum Replies Last Post robert44444uk Hardware 50 2018-04-07 20:41 Uncwilly Lounge 12 2018-02-14 15:00 jmb1982 Software 2 2009-04-07 09:33 Unregistered PrimeNet 3 2003-12-10 04:32 Wacky Puzzles 5 2003-06-24 16:11

All times are UTC. The time now is 12:03.

Mon May 17 12:03:44 UTC 2021 up 39 days, 6:44, 0 users, load averages: 1.40, 1.58, 1.66