Transfinite Nim

Posted on May 27, 2015 by Joel David Hamkins

Shall we have a game of transfinite Nim? One of us sets up finitely many piles of wooden blocks, each pile having some ordinal height, possibly transfinite, and the other of us decides who shall make the first move. Taking turns, we each successively remove a top part of any one pile of our choosing, making it strictly shorter. Whoever takes the very last block wins. (It is fine to remove an entire pile on a turn or to remove blocks from a different pile on a later turn.)

In my challenge problem last week, for example, I set up six piles with heights:
$1 ω + 3 ω^{ω} + 5 ω^{ω + 3} + ω^{ω} \cdot 3 + ω \cdot 5 + 7 ϵ_{0} ω_{1}$ Would you want to go first or second? What is the best move? In general, we can start with any finite number of piles of arbitrary ordinal heights — what is the general winning strategy?

Before proceeding with the transfinite case, however, let’s review the winning strategy in ordinary finite Nim, which I explained in my post last week concerning my visit to the 7th/8th grade Math Team at my son’s school. To say it quickly again, a finite Nim position is balanced, if when you consider the binary representations of the pile heights, there are an even number of ones in each binary place position. Another way to say this, and this is how I explained it to the school kids, is that if you think of each pile height as a sum of distinct powers of two, then any power of two that arises in any pile does so an even number of times overall for all the piles. The mathematical facts to establish are that (1) any move on a balanced position will unbalance it; and (2) any unbalanced position admits a balancing move. Since the winning move of taking the very last block is a balancing move, it follows that the winning strategy is to balance whatever position with which you are faced. At the start, if the position is unbalanced, then you should go first and balance it; if it is already balanced, then you should go second and adopt the balancing strategy. It may be interesting to note that this winning strategy is unique in the sense that any move that does not balance the position is a losing move, since the opposing player can adopt the balancing strategy from that point on. But of course there is often a choice of balancing moves.

Does this balancing strategy idea continue to apply to transfinite Nim? Yes! All we need to do is to develop a little of the theory of transfinite binary representation. Let me assume that you are all familiar with the usual ordinal arithmetic, for which $α + β$ is the ordinal whose order type is isomorphic to a copy of $α$ followed by a copy of $β$ , and $α \cdot β$ is the ordinal whose order type is isomorphic to $β$ many copies of $α$ . Consider now ordinal exponentiation, which can be defined recursively as follows:
$α^{0} = 1$ $α^{β + 1} = α^{β} \cdot α$ $α^{λ} = sup_{β < λ} α^{β} λ limit$ It turns out that $α^{β}$ is the order-type of the finite-support functions from $β$ to $α$ , under the suitable lexical order. Ordinal exponentiation should not be confused with cardinal exponentiation, since they are very different. For example, with ordinal exponentiation, one has $2^{ω} = sup_{n < ω} 2^{n} = ω,$ which of course is not the case with cardinal exponentiation. In this post, I use only ordinal exponentiation.

Theorem. Every ordinal $β$ has a unique representation as a decreasing finite sum of ordinal powers of two. $β = 2^{β_{n}} + \dots + 2^{β_{0}}, β_{n} > \dots > β_{0}$

The proof is easy! We simply prove it by transfinite induction on $β$ . If the theorem holds below an ordinal $β$ , first let $2^{α}$ be the largest power of two that is at most $β$ , so that $β = 2^{α} + γ$ for some ordinal $γ$ . It follows that $γ < 2^{α}$ , for otherwise we could have made $2^{α + 1} \leq β$ . Thus, by induction, $γ$ has a representation with powers of two, and so we may simply add $2^{α}$ at the front to represent $β$ . To see that the representations are unique, first establish that any power of two is equal to or more than the supremum of the finite decreasing sums of any strictly smaller powers of two. From this, it follows that any representation of $β$ as above must have used $2^{α}$ just as we did for the first term, because otherwise it couldn’t be large enough, and then the representation of the remaining part $γ$ is unique by induction, and so we get uniqueness for the representation of $β$ . QED

Thus, the theorem shows that every ordinal has a unique binary representation in the ordinals, with finitely many nonzero bits. Suppose that we are given a position in transfinite Nim with piles of ordinal heights $η_{0}, \dots, η_{n}$ . We define that such a position is balanced, if every power of two appearing in the representation of any of the piles appears an even number of times overall for all the piles.

The mathematical facts to establish are (1) any move on a balanced position will unbalance it; and (2) every unbalanced position has a balancing move. These facts can be proved in the transfinite case in essentially the same manner as the finite case. Namely, if a position is balanced, then any move affects only one pile, changing the ordinal powers of two that appear in it, and thereby destroy the balanced parity of whichever powers of two are affected. And if a position is unbalanced, then look at the largest unbalanced ordinal power of two appearing, and make a move on any pile having such a power of two in its representation, reducing it so as exactly to balance all the smaller powers of two appearing in the position.

Finally, those two facts again imply that the balancing strategy is a winning strategy, since the winning move of taking the last block or blocks is a balancing move, down to the all-zero position, which is balanced.

In the case of my challenge problem above, we may represent the ordinals in binary. We know how to do that in the case of 1, 3, 5 and 7, and actually those numbers are balanced. Here are some other useful binary representations:

$ω + 3 = 2^{ω} + 2 + 1$

$ω^{ω} + 5 = (2^{ω})^{ω} + 5 = 2^{ω^{2}} + 4 + 1$

$ω^{ω + 3} = (2^{ω})^{ω + 3} = 2^{ω^{2} + ω \cdot 3}$

$ω^{ω} \cdot 3 = (2^{ω})^{ω} \cdot 3 = 2^{ω^{2}} \cdot 2 + 2^{ω^{2}} = 2^{ω^{2} + 1} + 2^{ω^{2}}$

$ω \cdot 5 + 7 = 2^{ω} \cdot 2^{2} + 2^{ω} + 7 = 2^{ω + 2} + 2^{ω} + 4 + 2 + 1$

$ϵ_{0} = 2^{ϵ_{0}}$

$ω_{1} = 2^{ω_{1}}$

I emphasize again that this is ordinal exponentiation. The Nim position of the challenge problem above is easily seen to be unbalanced in several ways. For example, the $ω_{1}$ term among others appears only once. Thus, we definitely want to go first in this position. And since $ω_{1}$ is the largest unbalanced power of two and it appears only once, we know that we must play on the $ω_{1}$ pile. Once one represents all the ordinals in terms of their powers of two representation, one sees that the unique winning move is to reduce the $ω_{1}$ pile to have ordinal height
$ϵ_{0} + ω^{ω + 3} + ω^{ω} \cdot 2 + ω \cdot 4.$ This will exactly balance all the smaller powers of two in the other piles and therefore leaves a balanced position overall. In general, the winning strategy in transfinite Nim, just as for finite Nim, is always to leave a balanced position.

Special honors to Pedro Sánchez Terraf for being the only one to post the winning move in the comments on the other post!

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

Posted on May 22, 2015 by Joel David Hamkins

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!

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.

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.

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, \dots$ 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 \dots 11$ 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 ω + 3 ω^{ω} + 5 ω^{ω + 3} + ω^{ω} \cdot 3 + ω \cdot 5 + 7 ϵ_{0} ω_{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.

Win the game of Nim! CSI Math Club, October, 2013

Posted on October 24, 2013 by Joel David Hamkins

This will be a talk for the CSI Math Club on October 31, 2013 at 2:30 pm in room 1S-107.

Abstract Come and learn how to play and win the game of Nim! The game has two players, faced with several small piles of blocks. Each player, on their turn, can remove one or more blocks from one pile, but only one pile. (Removing a whole pile is fine.) The player who removes the last block wins. This simple-to-describe game is maddening for those who don’t know the secret mathematical winning strategy. Come and learn the mathematical secret that will allow you to win every time against someone who doesn’t know it.

More math for six-year-olds: Win at Nim!

Posted on May 20, 2013 by Joel David Hamkins

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.

Joel David Hamkins

mathematics and philosophy of the infinite

Tag Archives: Nim

Transfinite Nim

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

Win the game of Nim! CSI Math Club, October, 2013

More math for six-year-olds: Win at Nim!

Share:

Share:

Share:

Share: