The latest installment of math for six-year-olds…

Win at Nim!
Fold up the bottom flap to prevent parents from learning the super-secret strategy.

This morning once again I went into my daughter’s first-grade classroom, full of inquisitive six-and-seven-year-old girls, and made a mathematical presentation on the game of Nim.   

                   Win at Nim!

The game of Nim, I explained, begins with one player setting up a number of stacks of blocks,while the opponent chooses whether to go first or second.  Taking turns, each player removes one or more blocks from a stack of their choosing. (It is fine to take a whole stack on your turn.) The player who takes the last block wins.

We demonstrated the game by playing a number of exhibition rounds, and then the girls divided into pairs to play each other and also me.  They were surprised that I was able to win against them every single time.  In explanation, I told them that this was because in the game of Nim, there is a super-secret mathematical strategy!  Did they want to learn?  Yes!  I took as my goal that they would all learn the Nim strategy, so that they could go home and confound their parents by beating them again and again at the game.

Since this was a first-grade class, we concentrated at first on games with stacks of heights 1, 2 and 3 only, a special case of the game which can still challenge adults, but for which six-year-olds can easily learn the winning strategy.

Two balanced stacks

After gaining some familiarity with the game by playing several rounds amongst each other, we gathered again for the secret strategy session. We began by thinking about the case of a game of Nim with only two stacks. They had noticed that sometimes when I played them, I had made copying moves; and indeed I had purposely said, “I copy you,” each time this had occurred.  The copying idea is surely appealing when there are only two stacks.  After some discussion, the girls realized that with just two stacks, if one played so as to equalize them, then one would always be able to copy the opponent’s move.  In particular, this copying strategy would ensure that one had a move to make whenever the opponent did, and so one would win the game.

A balanced position

In short order, the girls also realized that if one had any number of pairs of such balanced stacks—so that every stack had a partner—then the whole position was also winning (for one to give to the other player), since one could copy a move on any stack by making the corresponding move on the partner stack.  Thus, we deduced that if we could match up stacks of equal height in pairs, then we had a winning strategy, the strategy to copy any move on a partner stack.

In particular, this balancing idea provides a complete winning strategy in the case of Nim games for which all stacks have height one or two.  One should play so as to give a balanced position to one’s opponent, namely, a position with an even number of stacks of height one and an even number of stacks of height two.  Any unbalanced position can always be balanced in this way, and any move on a balanced position will unbalance it.

1+2+3 counts as balanced

To handle positions with stacks of height three, the super-secret trick is that one can balance a stack of height three either with another stack of height three, of course, but also with two stacks:  one of height one and one of height two.   Thus, one should regard a stack of height three as consisting of two sub-stacks, one of height one and one of height two, for the purposes of balancing. Thus, the Nim position 1+2+3 counts as balanced, since the 3 counts as 2+1, which balances the other stacks.  The 1+2+3 position has two stacks of height two and two of height one, when one regards the stack of height three as having a substack of height two and a substack of height one.

In this way, one arrives at a complete winning strategy for Nim positions involving stacks of height at most three, and furthermore, this is a strategy that can be mastered by first-graders. The strategy is to strive to balance the position.  If you always give your opponent a balanced position, then  you will win!  Faced with an unbalanced position, you can always find a balancing move, and any move on an balanced position will unbalance it.  If the game is just starting, and you are deciding whether to go first or second, you should determine whether it is balanced yet or not.  If it unbalanced, then you should go first and make the balancing move; if it is already balanced, then you should go second and adopt the copying strategy, in which you re-balance the position with each move.

More advanced players will want to consider Nim positions with taller stacks than three, and we talked about this a little in the classroom.  Some of the girls realized that the copying strategy and the idea of balanced positions still worked with taller stacks.  One can balanced stacks of height four against other stacks of height four, and so one, but the trick for these taller stacks is that one may balance 5 with 4+1; balance 6 with 4+2; and 7 with 4+2+1. Mathematicians will recognize here the powers of two.

To teach the strategy to children, it is a great opportunity to talk about the powers of two. Any child knows how to count 1, 2, 3, 4 and so on, and most can count by twos 2, 4, 6, 8, 10, …; by fives 5, 10, 15, 20, …; by tens, by threes; by sevens; and so on.  , The powers of two are the numbers 1, 2, 4, 8, 16, 32, 64, 128, and so on, doubling each time.  Climbing this exponential growth, children are often amazed at how quickly one reaches very large numbers:

One plus one is two;

two plus two is four;

four plus four is eight;

eight plus eight is sixteen;

sixteen plus sixteen is thirty-two;

thirty-two plus thirty-two is sixty-four;

sixty-four plus sixty-four is one hundred twenty-eight.

For Nim, we don’t in practice need such big powers of two, since one doesn’t usually encounter stacks of height eight or larger, and usually just 1s, 2s and 4s suffice. The relevant fact for us here is that every natural number is uniquely expressible as a sum of distinct powers of two, which of course is just another way of talking about binary representation of a number in base two.  We regard a Nim stack as consisting of its power-of-two substacks.  Thus, a stack of height 3 counts as 2+1; a stack of height 5 counts as 4+1; a stack of height 6 counts as 4+2; and a stack of height 7 counts as 4+2+1.

Ultimately, the winning general strategy for Nim is always to play so as to balance the position, where one regards every stack as being composed of its power-of-two sub-stacks, and a position counts as balanced when these stacks and sub-stacks can be matched up in pairs. This is a winning strategy, since every unbalanced position can be balanced, and any move on a balanced position will unbalance it.  To balance an unbalanced stack, play on any stack containing the largest size unbalanced power of two substack, and reduce it so as to balance the parity of all the stacks.  If one thinks about it, at bottom what we are doing is ensuring that if we represent the stack heights in their binary representation, then we should play so as to ensure that the position has a even number of one digits in each place.