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?

[url]http://world.std.com/~reinhold/math/nim.html[/url]

The answer is here,

Sorry, Nim is a different game. Please reread the rules.

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 [i]n[/i] as partitions of [i]n[/i].

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.

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. ;)

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 :exclaim: and 1+5+5
P.P.S. It's much harder to analyse the game with modified rules; it's solution is much longer.