This game starts with some noughts and some crosses. You and your opponent take turns removing two shapes, and adding a new one according to this rule: if the shapes are identical, add a nought; otherwise, add a cross. When only one shape remains, you win if it's a nought, and lose if it's a cross.

Is there a winning strategy for any of the players? How should you play?

(In reply to Solution by David Shin)

If the interpretation of the rules is that the player who leaves the sole O or X is the winner or loser, the following applies:

If the game starts with XXO, and I go first, I'll leave two identical shapes for my opponent, who will change them into one O and win.

If, however, the game starts with XXOO and I go first, I'll leave my opponent with either OOO or XXO. In either case he'll leave me with two identical pieces, and I'll win.

More generally, as the parity of the X's doesn't change, the parity of the O's flips back and forth.  So if there are an even number of X's, someone will win by leaving a(n) O: if there are an even number of O's, the first player will win; if an odd number of O's the second player will win.

Conversely if there are an odd number of X's, one of the players will lose by leaving a sole X.  If there are an even number of O's, that will be the second player (making the first player the winner).

So in either case, if there are an even number of O's the first player will win, and an odd number of O's leads to the second player's win.

Posted by Charlie on 2004-09-16 08:58:39