In this game there are three pots, one containing 3 counters, one containing 5 counters, and one containing 7 counters. One their turn a player takes as many counters as they like from one of the pots only (minimum 1 counter). The player to take the last counter loses. In a two player game, what is the winning strategy?
Hint: try considering every possible move, and which positions are guaranteed to win you the game.
Background: I remember this as a game that some boys used to play at school. The secret to winning was closely guarded, and I didn't much care for the air of superiority that those members of that elite held. So rather than have to be indebted to them for teaching me their tricks, I sat down and worked it out myself.
First off, let any state of play be defined by a three digit number representing the number of counters held in each of the three pots. For consistency's sake, always put these numbers in ascending order. For example if, on the first move, one player took three counters from the pot with five in originally, the state of the game would move from 357 to 237.
Let a 'winning position' be any position from which whatever choices your opponent makes, you can always win the game. Clearly the ultimate winning position, and the target you seek to achieve, is 001. Furthermore, if you have reached a winning position, whatever move your opponent makes, you can move to another winning position. Finally, any position that allows your opponent to reach a winning position is itself never a winning position.
Possible winning positions:
022 is a winning position. Whatever move your opponent makes, you can jump to 001:
022 012 001
022 002 001
033 is also a winning position:
033 023 022
033 013 001
033 003 001
Similarly, so is 044:
044 034 033
044 024 022
044 014 001
044 004 001
So is 055, and in fact any position of the form 0XX would be (proof by induction).
055 045 044
055 035 033
055 025 022
055 015 001
055 005 001
111 is a winning position, since your opponent can only make the move to 011, and you can only move to 001, winning the game.
111 011 001
123 is a winning position too:
123 023 022
123 113 111
123 013 001
123 122 022
123 112 111
123 012 001
Interestingly so is 145, which rather destroys the symmetry otherwise naïvely evident:
145 045 044
145 135 123
145 125 123
145 115 111
145 015 001
145 144 044
145 134 123
145 124 123
145 114 111
145 014 001
And 246 is a winning position:
246 146 145
246 046 044
246 236 123
246 226 022
246 126 123
246 026 022
246 245 145
246 244 044
246 234 123
246 224 022
246 124 123
246 024 022
Then the three states 257, 347, 356, each reached by taking away one counter only from the original 357, are also all winning positions:
257 157 145
257 057 055
257 247 246
257 237 123
257 227 022
257 127 123
257 027 022
257 256 246
257 255 055
257 245 145
257 235 123
257 225 022
257 125 123
257 025 022
347 247 246
347 147 145
347 047 044
347 337 033
347 237 123
347 137 123
347 037 033
347 346 246
347 345 145
347 344 044
347 334 033
347 234 123
347 134 123
347 034 033
356 256 246
356 156 145
356 056 055
356 346 246
356 336 033
356 236 123
356 136 123
356 036 033
356 355 055
356 345 145
356 335 033
356 235 123
356 135 123
356 035 033
So the following states are all proven to be winning positions: 001, 022, 033, 044, 055, 111, 123, 145, 246, 257, 347, 356. To complete this I need to prove that every other state is not a winning position, and to do that I simply need to show that there is a winning position one move away. Therefore the following list comprises every possible state in this game. Each state is marked as either a winning position, or with the winning position(s) that can be made from it.
001 : Winning position 055 : Winning position 223 : 022, 123 002 : 001 056 : 055 224 : 022 003 : 001 057 : 055 225 : 022 004 : 001 111 : Winning position 226 : 022 005 : 001 112 : 111 227 : 022 006 : 001 113 : 111 233 : 033, 123 007 : 001 114 : 111 234 : 123 011 : 001 115 : 111 235 : 123 012 : 001 116 : 111 236 : 123 013 : 001 117 : 111 237 : 123 014 : 001 122 : 022 244 : 044 015 : 001 123 : Winning position 245 : 145 016 : 001 124 : 123 246 : Winning position 017 : 001 125 : 123 247 : 246 022 : Winning position 126 : 123 255 : 044 023 : 022 127 : 123 256 : 246 024 : 022 133 : 033, 123 257 : Winning position 025 : 022 134 : 123 333 : 033 026 : 022 135 : 123 334 : 033 027 : 022 136 : 123 335 : 033 033 : Winning position 137 : 123 336 : 033 034 : 033 144 : 044 337 : 033 035 : 033 145 : Winning position 344 : 044 036 : 033 146 : 145 345 : 044, 145 037 : 033 147 : 145 346 : 246 044 : Winning position 155 : 055, 145 347 : Winning position 045 : 044 156 : 145 355 : 055 046 : 044 157 : 145 356 : Winning position 047 : 044 222 : 022 357 : 257, 347, 356
The overall strategy is this, then: remember the winning positions, and move to them whenever possible. If you play first, take one counter from any of the pots. If you play correctly from that point on you cannot lose. If your opponent plays first, and is not familiar with the game, you will have to rely on luck and psychology to get to a winning position, and then continue to victory. The less counters you take, the more scope your opponent has for making a mistake.
Try playing the game again, but with a starting position other than 357. Keeping the rules the same, the winning positions above will still hold, but if you increase the number of counters in any of the pots, there may be some new ones. An interesting variation to play with someone who knows the above game is 1357.
If you want to go for an even bigger challenge, try playing with three players. Working together any pair of players can force the third to lose every time, so it is better to change the winning conditions slightly: instead of losing if you reach 000, you win if you reach 001 (or the equivalent, if you're not using three pots). A subtle difference that doesn't change the two player game, but makes the three player game much more vicious and political. Any more players over three loses the bite.
I have actually theorised a much simpler general solution to the problem of winning this game. This is under the maths section of my website, as the theory of nim.