Although I did this in class, I thought it might be useful to write out a proof here. There are many variations, but it should look something quite similar to this.
Claim: For \(n = 0,1,2,\ldots\) a non-negative integer, the winner of the sticks game is as follows:
- If there are \(3n+1\) sticks, then the player to move loses.
- If there are \(3n+2\) sticks, then the player to move wins.
- If there are \(3n+3\) sticks, then the player to move wins.
Proof: We give a proof by induction starting from \(n = 0\). Let \(P(n)\) mean that the three listed statements above are true for \(n\).
Base Case: Suppose that \(n=0\).
- If there is one stick, then the player to move has to pick up the stick and so loses.
- If there are two sticks, then the player to move can pick up one stick, and then the next player has to pick up the final stick and so loses, and hence the first player wins.
- If there are two sticks, then the player to move can pick up two sticks, and then the next player has to pick up the final stick and so loses, and hence the first player wins.
These three statements prove \(P(0)\) is true, which is the base case.
Inductive Step: We shall assume \(P(k)\) and show \(P(k+1)\).
- If there are \(3(k+1) + 1 = 3k+4\) sticks, and the player to move picks up one stick, then there are \(3k+3\) sticks remaining. But since we are assuming \(P(k)\), this means that the second player (who is now the player to move) wins, which means that the first player loses. On the other hand, if the first player picks up two sticks, there are \(3k+2\) sticks remaining. Again by our assumption \(P(k)\), this means the second player wins and the first player loses. So whatever the first player does, he will lose. So if there are \(3(k+1)+1\) sticks, the player to move loses.
- If there are \(3(k+1) + 2 = 3k+5\) sticks, then the player to move can pick up one stick, and there are \(3k+4\) sticks remaining. Now by part \(1\), the second player (who is now the player to move) must lose. Thus the first player can always win.
- If there are \(3(k+1) + 3 = 3k+6\) sticks, then the player to move can pick up two sticks, and there are \(3k+4\) sticks remaining. Now by part \(1\), the second player (who is now the player to move) must lose. Thus the first player can always win.
Thus assuming \(P(k)\) we have shown \(P(k+1)\) is true, and so by induction we are done!
Remarks:
- Notice how wordy the proof is! That’s a feature not a a bug; communicating in sentences is often a really clear way to convey ideas. It is often the case that mathematical notation is more compact and it is useful for that purpose, just make sure it doesn’t obscure what you are actually doing.
- Note that in the case \(n = 3k+5\) and \(n=3k+6\) we used the case \(n = 3k+4\) which was not part of \(P(k)\), but part of our argument showed that the case \(n = 3k+4\) did follow from \(P(k)\). That is fine — it just means that it took a few steps for us to prove \(P(k+1)\) only assuming \(P(k)\). Another interesting feature of the argument is that when deducing \(P(k+1)\) we didn’t even use the fact about the game with \(3k+1\) players.
- The sticks game is a special case of a more general game called nim. Although the more general game is a little more complicated, ultimately the analysis is quite similar and the proof (given at the link) is by induction.
Added: A real life application of the sticks game: