EDIT: Nope! Not far wrong, but definitely wrong.
My strategy of starting with the easy cases and building out to more complex cases was used successfully by other solvers. My analysis of the easy cases was correct, but there was a mistake in the way I built out. My diagram probably didn’t help; the one drawn by the winner didn’t distinguish between the larger and smaller piles, and I think that’s where my error crept in.
For example, when I considered (9, 5), I thought it was a losing position because I didn’t see that taking six coins from the larger pile produced (5, 3), since the larger pile became the smaller pile in that move. So the “simplification” I introduced, of specifying one pile as larger, while not wrong, made it easier for me to make a mistake. It helped to break my mental model by suggesting an identity for the piles (“larger” or “smaller”) that isn’t persistent, but depends on the progress of the game. Will try not to do that again!
EDIT 2: Revised the original spread sheet showing the rows that I had calculated wrongly, and producing a correct game state table.
The puzzle is a coin-picking game, with the usual aim of taking the last coins, but the unusual condition of having two coin stacks:
The game starts with somewhere between 20 and 30 pennies, which I then divide into two piles any way I like. Then we alternate taking turns, with you first, until someone wins the game. For each turn, a player may take any number of pennies he or she likes from either pile, or instead take the same number of pennies from both piles. Each player must also take at least one penny every turn. The winner of the game is the one who takes the last penny.
If we both play optimally, what starting numbers of pennies (again, between 20 and 30) guarantee that you can win the game?
The only way I can see to tackle game problems like this one is to start with the simplest game positions, and try to work backwards to more complex positions.
The simplest positions in the game are these, with three coins or less:
|Current Pile Sizes||Result||Only one stack||Stacks equal|
The Result column is your best result, with perfect play, if you face this position in your turn. If there’s only one stack of coins, you take the whole stack, and you’ve won. Similarly, if there are two stacks of equal size, you take all of the coins from both stacks, and you’ve won. If there are no coins left, your opponent has won.
If there are two coins on one stack, and one coin on the other (call that position “2, 1”), then you haven’t lost yet, but you’re in a losing position. No matter how many coins you take, you will leave your opponent in a winning position: you must leave them in one of the positions with a Result of WIN.
Let’s add more positions to the table:
|Current Pile Sizes||Result||Only 1 stack||Stacks equal||Win by making the next position 2,1|
Now as well as winning by taking all of the coins (when there is only one stack, or two equally-sized stacks), we can also win by putting our opponent into a losing position. If the game position is 3, 1 we can take one coin from the larger pile, giving our opponent the losing position of 2, 1, and then whatever they do, we’ll be left in a winning position. Similarly, if the game position is 3, 2, we take two coins from the larger pile, again making our opponent face the losing position of 2, 1.
I won’t give you the whole breakdown here. There are 256 possible game positions, and I worked through all of them in this Excel sheet. Ten of the positions are losing positions, including 0, 0 and 2, 1. The other 246 are winning ones: whichever position you’re in, there’s a way to put your opponent into one of the losing positions on their turn.
All of the possible game positions are in this table:
The possible starting positions for the game are those cells with numbers in them; the numbers are the total number of coins in both stacks in that state. In this diagram it’s more obvious that the game is not so complicated. Every legal move must take the game from one position to another that is either to the left of the initial position (shrinking the larger pile), above it (shrinking the smaller pile), or above and to the left (shrinking both piles). Eventually we have to reach the top left corner!
Anyway, you can see that for 20, 23, 26, and 29 starting coins, there is one possible way of dividing them into stacks that means the first player to remove coins is in a losing position – these are the red cells.
For the other starting coin possibilities (21, 22, 24, 25, 27, 28, 30), no matter how they are divided, the player that removes coins first can always put the second player into a losing position. The correct move can be found from colour key for the starting cell. And those seven starting possibilities are the answer!