Win at Nim! The secret mathematical strategy for kids (with challange problems in transfinite Nim for the rest of us)

Welcome to my latest instance of Math for Kids!

Today I had the pleasure to make an interactive mathematical presentation at my son’s school to the 7th / 8th grade Math Team, about 30 math-enthusiastic kids (twelve and thirteen years old) along with their math teachers and the chair of the school math department.

The topic was the game of Nim! This game has a secret mathematical strategy enabling anyone with that secret knowledge to win against those without it. It is a great game for kids, because with the strategy they can realistically expect to beat their parents, friends, siblings and parent’s friends almost every single time!

DSC00078

To play Nim, one player sets up a number of piles of blocks, and the opponent chooses whether to go first or second. The players take turns removing blocks — each player may remove any number of blocks (at least one) from any one pile, and it is fine to take a whole pile — whichever player takes the last block wins.

For the math team, we played a few demonstration games, in which I was able to beat all the brave challengers, and then the kids paired off to play each other and gain familiarity with the game. Then, it was time for the first strategy discussion.

What could the secret winning strategy be? I explained to the kids a trick that mathematicians often use when approaching a difficult problem, namely, to consider in detail some very simple special cases or boundary instances of the problem. It often happens that these special cases reveal a way of thinking about the problem that applies much more generally.

Perhaps one of the easiest special cases of Nim occurs when there is only one pile. If there is only one pile, then clearly one wants to go first, in order to make the winning move: take the entire pile!

Two balanced piles

A slightly less trivial and probably more informative case arises when there are exactly two piles. If the stacks have the same height, then the kids realized that the second player could make copying moves so as to preserve this balanced situation. The key insight now is that this copying strategy is a winning strategy, because if one can always copy, then in particular one will have a move whenever the opponent did, and so the opponent will never take the last block. With two piles, therefore, one wants always to make them balanced. If they are initially unbalanced, then choose to go first and follow the balancing strategy. If they are initially balanced, then choose to go second, and copy whatever moves your opponent makes to rebalance them.

DSC00076

A balanced position

With that insight, it is not difficult to see that it is winning to leave a position with any number of pairs of balanced piles. One can in effect play on each pair separately, because whenever the opponent makes a move on one of the piles, one can copy the move with the corresponding partner pile. In this way, we may count such a position overall as balanced. The more fundamental game-theoretic observation to make is that balanced piles in effect cancel each other out in any position, and one can ignore them when analyzing a position. When two balanced piles are present in a possibly more complicated position, one can pretend that they aren’t there, precisely because whenever your opponent plays on one of them, you can copy the move on the other, and so any winning strategy for the position in which those piles are absent can be converted into a winning strategy in which the balanced piles are present.

This idea now provides a complete winning strategy in the case that all piles have height one or two at most. One wants to leave a position with an even number of piles of each height. If only one height has an odd number of piles, then take a whole pile of that height. And if there are odd numbers of piles both of height one and two, then turn a height-two pile into a pile of height one, and this will make them both even. So any unbalanced position can be balanced, and any move on a balanced position will unbalance it.

DSC00074

1+2+3 counts as balanced

Let’s now consider that there may be piles of height three. For example, consider the basic position with piles of height one, two and three. The observation to make here is that any move on this position can be replied to with a move that leaves it balanced (check it yourself to be sure!). It follows that this position is winning to leave for the other player (and so one should go second on $1+2+3$). It would be nice if we could consider this position itself as already balanced in some sense. Indeed, we may incorporate this situation into the balancing idea if we think of the pile of height three as really consisting of two subpiles, one of height two and one of height one. In this way, 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.

This way of thinking produces a complete winning strategy for Nim positions involving piles of height at most three. (And this is a strategy that can be mastered even by very young children — a few years ago I had talked about Nim with much younger children, Math for six-year-olds: Win at Nim!, first-graders at my daughter’s school, and at that time we concentrated on posititions with piles of height at most three. Older kids, however, can handle the full strategy.) Namely, the winning strategy in this case is to strive to balance the position, to make an even number overall of piles of height one and two, where we count piles of height three as one each of one and two. If you always give your opponent a balanced position, then  you will win!  Faced with an unbalanced position, it is a fact that 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.

The general winning strategy, of course, goes beyond three. The key idea is to realize that what is really going on when we represent $3$ as $2+1$ is that we are using the binary representation of the number $3$. To explain, I wrote the following numbers on the chalkboard $$1,\ 2,\ 4,\ 8,\ 16,\ 32,\ 64,\ \cdots$$ and was very pleased when the kids immediately shouted out, “The powers of two!” I explained that any natural number can be expressed uniquely as a sum of distinct powers of two. Asked for a favorite number less than one hundred, one student suggested $88$, and together we calculated $$88=64+16+8,$$ which means that the binary representation of $88$ is $1011000$, which I read off as, “one $64$, no $32$s, one $16$, one $8$, no $4$s, no $2$s and no $1$s. This is just the same as thinking of $9572$ as 9 thousands, 5 hundreds, 7 tens and 2 ones, using the powers of ten. It is interesting to learn that one may easily count very high on one hand using binary, up to 1023 on two hands!

The general strategy is to view every Nim pile as consisting of subpiles whose height is a power of two, and to make sure that one leaves a position that is balanced in the sense that every power of two has an even number of such instances in the position. So we think of $3$ as really $2+1$ for the purposes of balancing; $4$ counts as itself because it is a power of two, but $5$ counts as $4+1$ and $6$ counts as $4+2$ and $7$ as $4+2+1$. Another way to describe the strategy is that we express all the pile heights in binary, and we want an even number of $1$s in each binary place position.

The mathematical facts to verify are (1) any move on a balanced position in this powers-of-two sense will cause it to become unbalanced, and (2) any unbalanced position can be balanced in one move. It follows that leaving balanced positions is a winning strategy, because the winning move of taking the last block is a balancing move rather than an unbalancing move.

One can prove statement (1) by realizing that when you move a single stack, the binary representation changes, and so whichever binary digits changed will now become unbalanced.  For statement (2), consider the largest unbalanced power of two $2^k$ and move on any stack that contains a $2^k$ size substack. Since $2^k-1=111\cdots11$ in binary, one can attain any binary pattern for the smaller height stacks by removing between $1$ and $2^k$ many blocks. So one can balance the position.

As a practical matter, the proof of (2) also shows how one can find a (winning) balancing move, which can otherwise be difficult in some cases: look for the largest unbalanced power of two, and move on any pile containing such a subpile, making sure to leave a balanced position.

In most actual instances of Nim, the pile heights are rarely very tall, and so one is usually considering just $1$, $2$ and $4$ as the powers of two that arise.  A traditional starting configuration has piles of height 1, 3, 5, and 7, and this position is balanced, because one may view it as: $1, 2+1, 4+1, 4+2+1$, and there are an even number of 1s, 2s and 4s.

It is interesting to consider also the Misère form of Nim, where one wants NOT to take the last block. This version of the game also has a secret mathematical strategy, which I shall reveal later on.

Challenge 1.   What is the winning strategy in Misère Nim?

If you figure it out, please post a comment! I’ll post the solution later. One might naively expect that the winning strategy of Misère Nim is somehow totally opposite to the winning strategy of regular Nim, but in fact, the positions $1,2,3$ and $1,3,5,7$ are winning for the second player both in Nim and also in Misère Nim. Indeed, I claim that all nontrivial Nim positions that are winning for regular Nim (with a suitable meaning of “nontrivial”) are also winning for Misère Nim. Can you prove it?

Another interesting generalization, for the set-theorists, is to consider transfinite Nim, where the piles can have transfinite ordinal height. So we have finitely many piles of ordinal height, perhaps infinite, and a move consists of making any one pile strictly shorter. Since there are no infinite descending sequence of ordinals, the game will terminate in finitely many moves, and the winner is whowever removes the last block.

Challenge 2.  Who wins the transfinite Nim game with piles of heights: $$1\qquad \omega+3\qquad \omega^\omega+5\qquad \omega^{\omega+3}+\omega^\omega\cdot3+\omega\cdot 5+7\qquad \epsilon_0\qquad \omega_1$$ and what are the winning moves? What is the general winning strategy for transfinite Nim?

Post your solutions! You can also see my solution and further discussion.

 

27 thoughts on “Win at Nim! The secret mathematical strategy for kids (with challange problems in transfinite Nim for the rest of us)

  1. You wrote “find the (winning) balancing move” when you meant, as is immediately clear, “find a (winning) balancing move”.

    On a more interesting note, the first variant studied after Bouton’s paper is with the moves: take any number from any piles, but you must take the same number from all the piles you take from. The two-pile version is often called the game of the southwest queen, and can be played on a chessboard.

  2. Dear Joel,

    I’m writing a sketchy partial answer to your riddle. Hope it makes some sense. (Btw, may I use LaTeX here?!?)

    First I tried to mimic the already expounded strategy, by expressing these ordinals in “binary”. So, before that I had to make some two-to-the-alpha calculations. One thing I got is that $2^{\omega^\omega}$ equals $\omega^{\omega^\omega}$, and hence, for every $\beta$ greater than $\omega$,

    $2^{\omega^\beta} = \omega^{\omega^\beta}$.

    (If these equations don’t work, the rest of the argument is useless.)
    Then actually the bigger ordinals $\epsilon_0$ and $\omega_1$ are powers of 2, but the smaller ones on the list aren’t.

    So, if I managed to write all the ordinals in binary, there are several unbalanced powers of 2 in the piles. Hence I would like to play first here; and my first move would be to replace $\omega_1$ by

    $\epsilon_0 + \omega^{\omega+3} + \omega^\omega\cdot 2 + \omega\cdot 4$.

    This would face my adversary with a set of balanced piles.

    Best wishes,
    PST.-

    PS. Two things I’m assuming: Every ordinal has a unique base-2 expansion, and (!) the same strategy as above works.

  3. [I might have been banned from your site already, because it’s the second time I try to post this partial solution and it doesn’t appear, nor I’m not getting news about new posts on my mail either. In any case, sorry for the spam!]

    Dear Joel,

    I’m writing a sketchy partial answer to your riddle. Hope it makes some sense. (Btw, may I use LaTeX here?!?)

    First I tried to mimic the already expounded strategy, by expressing these ordinals in “binary”. So, before that I had to make some two-to-the-alpha calculations. One thing I got is that $2^{\omega^\omega}$ equals $\omega^{\omega^\omega}$, and hence, for every $\beta$ greater than $\omega$,

    $2^{\omega^\beta} = \omega^{\omega^\beta}$.

    (If these equations don’t work, the rest of the argument is useless.)
    Then actually the bigger ordinals $\epsilon_0$ and $\omega_1$ are powers of 2, but the smaller ones on the list aren’t.

    So, if I managed to write correctly all the ordinals in binary, there are several unbalanced powers of 2 in the piles. Hence I would like to play first here; and my first move would be to replace $\omega_1$ by

    $\epsilon_0 + \omega^{\omega+3} + \omega^\omega\cdot 2 + \omega\cdot 4$.

    This would face my adversary with a set of balanced piles.

    PS. Two things I’m assuming: Every ordinal has a unique base-2
    expansion (I think that the argument in Cantor’s normal form goes through), and (!) the same strategy as above works.

  4. Thank you! That was rather quick.

    Actually, I submitted the comment once before I set this wordpress account, and that one (I think) was not successful.

    And before that, I also commented on your CH talk at Einstein Chair (did that reach you?). It was very nice (saw the video), and you had a very receptive and curious audience. AFAIK, no one in my country is doing set theory right now. Not sure if I’m a little too old for starting a new research theme almost from scratch, but I really like it very much. With a little luck and effort I might be able to achieve this goal.

    Best wishes from Argentina,
    PST.-

    • It seems that my spam filter had unfortunately held some of your previous messages, which I have now released. Please let me know if you have issues in the future, since I value your comments!

      Good luck with set theory in Argentina! Let me know if there is anything I can do to help. I know that there are other set theorists in South and Central America, but they may not be so close. There are some logicians in Columbia, and logic friendly researchers in Brazil.

      • Thank you, Erin. I’m kinda old for this kind of riddles, nevertheless it’s always rewarding to solve any sort of problem! Specially if it’s about set theory.

  5. Pingback: Transfinite Nim | Joel David Hamkins

    • With two stacks of ten, I want to go second, since whatever you do to one stack, I will copy you on the other stack, and thereby always have a move. So I’ll win.

      With three stacks of ten, however, I want to go first, since then on my first move I remove an entire stack of ten, and be in exactly the desirable position of the previous case.

  6. “….I wrote the following numbers on the chalkboard
    1, 2, 4, 8, 16, 32, 64, ⋯
    1, 2, 4, 8, 16, 32, 64, ⋯
    and was very pleased when the kids immediately shouted out, “The powers of two!” ….”
    This may be off the mark. But..
    I have been searching for a good brief name for this set of very special numbers, (other than ‘Powers of two) something showing its link with Binary. In vain. Kindly make one up.

    Subramanyan

    • I hadn’t yet posted—sorry for the delay!

      The winning strategy in misère nim is to play exactly the same as in regular nim, by always moving to balance the position in the way I had described, except when the position would have all piles of height only one; in this special case, then make sure to leave an odd number of such piles, rather than an even number. So optimal play in misère nim is almost exactly the same as in regular nim, until the very end of the game, when all piles have height one.

    • When the piles are height 3 4 5, then the first player can win by playing to 1 4 5. This is a balanced position, to use the terminology of the post, because if you think of 5 as 4+1, then you have two fours and two ones. And there is nothing that the second player can do to avoid losing, if the first player plays the balancing strategy.

  7. Pingback: The Secrets of Zugzwang in Chess, Math and Pizzas | Quanta Magazine - 2NYZ.com

  8. Pingback: Quanta Magazine

  9. I think your explanation of how to win and how this game works is overly complex. I could explain it using a few paragraphs at the very most.

    • I’m sure you are right. I tried to have a full discussion of the easy cases, with piles of height up to 3, since this is a case that even very young children can learn (I have taught this to classes of first-graders). But then deriving the strategy for the general case makes the whole discussion somewhat longer. Of course, it is possible to describe the strategy and proof in just a few sentences: make a move so that when you represent the pile heights as sums of distinct powers of two, then the number of powers of two appearing overall is even; if this is possible, you will win, since any move on a position with this feature will lack it, and so your opponent will never be able to reach the empty (winning) position; and if a position lacks the property, then there is always such a balancing move.

      Perhaps you will prefer the discussion of Nim in my book, Proof and the Art of Mathematics, where I treat this game in the chapter on the theory of games.

Leave a Reply

Your email address will not be published. Required fields are marked *