Last night I watched the French film Last Year at Marienbad. In it, characters played a game with 16 matchsticks (or cards, or whatever) arranged in four rows, like this:
I
III
IIIII
IIIIIII
Players take turn removing as many matchsticks as they want on each turn, provided the matchsticks all come from the same row. The loser of the game is the person who removes the last matchstick.
It became clear that there was some strategy through which you could always win the game, although the actual strategy eluded me. Any ideas?
Here’s strategy I figured out in college. Write down all 142 combinations from 0-0-0-1 to 1-3-5-7 (consider 0003 the same as 0030 or 0300). Since 0-0-0-1 is a losing combination, check off all combintations that can get you to 0001: (e.g. 0002 thru 0007; 0011 thru 0017). These are winning combinations. Now the lowest combination not checked (0022) must be a losing combination. A winning combination is one that can get to 0022 (such as 0122 or 0026). Proceed this way until all 142 combinations are listed as either winning or losing. You’ll find that some losing combinations are (1) any pair other than 0011 or 1111; (2) 01xy where “y” is one more than “x”; etc. Of the 142 combinations, about 15 are losers, including 1357. So if both players know the strategy, the one who goes first loses.
The idea is probably to go first as long as there’s only two players. This way you trap your opponent into an impossible win situation on the first move.
It’s the same thing with the X(any number) stones and each person can take 1,2 or 3 stones each turn. With the stones, if you go first you drop it to the “magic” number, being 1 + (4 * x) where X is any integer. Then whatever the other person takes, you take an amount that would make it 4, (they take 1, you take 3) and so on and they’ll always be left with the last 1.