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\qquad \omega+3\qquad \omega^\omega+5 \qquad \omega^{\omega+3}+\omega^\omega\cdot3+\omega\cdot 5+7\qquad \epsilon_0\qquad \omega_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 $\alpha+\beta$ is the ordinal whose order type is isomorphic to a copy of $\alpha$ followed by a copy of $\beta$, and $\alpha\cdot\beta$ is the ordinal whose order type is isomorphic to $\beta$ many copies of $\alpha$. Consider now ordinal exponentiation, which can be defined recursively as follows:
$$\alpha^0=1$$ $$\alpha^{\beta+1}=\alpha^\beta\cdot\alpha$$ $$\alpha^\lambda=\sup_{\beta<\lambda} \alpha^\beta\qquad\lambda\text{ limit}$$ It turns out that $\alpha^\beta$ is the order-type of the finite-support functions from $\beta$ to $\alpha$, 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^\omega=\sup_{n<\omega}2^n=\omega,$$which of course is not the case with cardinal exponentiation. In this post, I use only ordinal exponentiation.
Theorem. Every ordinal $\beta$ has a unique representation as a decreasing finite sum of ordinal powers of two. $$\beta=2^{\beta_n}+\cdots+2^{\beta_0}, \qquad \beta_n>\cdots>\beta_0$$
The proof is easy! We simply prove it by transfinite induction on $\beta$. If the theorem holds below an ordinal $\beta$, first let $2^\alpha$ be the largest power of two that is at most $\beta$, so that $\beta=2^\alpha+\gamma$ for some ordinal $\gamma$. It follows that $\gamma<2^\alpha$, for otherwise we could have made $2^{\alpha+1}\leq\beta$. Thus, by induction, $\gamma$ has a representation with powers of two, and so we may simply add $2^\alpha$ at the front to represent $\beta$. 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 $\beta$ as above must have used $2^\alpha$ just as we did for the first term, because otherwise it couldn’t be large enough, and then the representation of the remaining part $\gamma$ is unique by induction, and so we get uniqueness for the representation of $\beta$. 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 $\eta_0,\ldots,\eta_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:
$\omega+3=2^\omega+2+1$
$\omega^\omega+5 = (2^\omega)^\omega+5=2^{\omega^2}+4+1$
$\omega^{\omega+3}=(2^\omega)^{\omega+3}=2^{\omega^2+\omega\cdot 3}$
$\omega^\omega\cdot3=(2^\omega)^\omega\cdot 3=2^{\omega^2}\cdot 2+2^{\omega^2}=2^{\omega^2+1}+2^{\omega^2}$
$\omega\cdot 5+7 =2^{\omega}\cdot 2^2+2^\omega+7=2^{\omega+2}+2^\omega+4+2+1$
$\epsilon_0 = 2^{\epsilon_0}$
$\omega_1=2^{\omega_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 $\omega_1$ term among others appears only once. Thus, we definitely want to go first in this position. And since $\omega_1$ is the largest unbalanced power of two and it appears only once, we know that we must play on the $\omega_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 $\omega_1$ pile to have ordinal height
$$\epsilon_0+\omega^{\omega+3}+\omega^\omega\cdot 2+\omega\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!
