74 Chapter 7

Welcome back. Did you find a winning strategy? I was surprised to find the following

winning strategy, which was much simpler than I had expected at first would be possible.

Theorem 51. The winning strategy in the game Buckets of Fish is to play so as to ensure

that every bucket has an even number of fish.

Proof. Notice first that in the case that there is only one bucket, then if it contains an even

number of fish, the second player can win, since the first player will necessarily make it

odd, and then the second player will make it even again. Thus, it will be the second player

who will make it zero, winning the game. So in the trivial instance of the game with only

one bucket, the player who can make the bucket even will be the winner.

Next, notice that if you play so as to give your opponent an even number of fish in every

bucket, then whatever move your opponent makes will result in an odd number of fish in

the bucket from which he or she takes a fish (and possibly also an odd number of fish in

some of the earlier buckets as well, if your opponent happens to add an odd number of fish

to some of them). So if you give your opponent an all-even position, then your opponent

cannot give you back an all-even position.

Finally, notice that if you are faced with a position that is not all even, then you can

simply take a fish from the rightmost odd bucket, thereby making it even, and add fish if

necessary to the earlier buckets so as to make them all even. In this way, you can turn

any position that is not all even into an all-even position in one move. By following this

strategy, a player will ensure that he or she will take the last fish, since the winning move is

to make the all-zero position, which is an all-even position, and we have already observed

that the opponent cannot produce an all-even position.

In the particular position of the game mentioned before the theorem, therefore, the win-

ning move is to take a fish from the bucket with seven fish and add an odd number of fish

to the bucket with five fish, thereby producing an all-even position.

7.3 The game of Nim

The game of Nim is a mathematician’s delight. The winning strategy is fundamentally

mathematical, with just the right level of complexity so that a person can enjoyably imple-

ment it in actual games, but difficult enough so that an opponent who does not know the

strategy is unlikely to play reliably in accordance with it. Those in the know can therefore

usually expect to win—nearly every time—against those who do not know the strategy,

even when starting from a random or losing position. I have taught young children the

strategy, who then go on to defeat adults systematically. What fun!

Nim is a two-player game. To play, set up finitely many piles of coins in front of you, and

decide who will go first. Any starting pattern is fine (1, 3, 5, 7 is common). On each turn, a

player selects a pile and removes one or more coins from that pile—taking the whole pile

is fine. The player who takes the very last coin wins.