Puppies, Kittens, and the Golden Ratio
We're going to look at Wythoff's Nim, a variation of the more familiar game of Nim and a game can easily be played with children...
Now that the dog days of summer are here, it seems like a good time to play a game, especially one that reveals a rich mathematical structure. We're going to look at Wythoff's Nim, a variation of the more familiar game of Nim and a game can easily be played with children. In fact, Wythoff's Nim is often played at math circles under the name "Puppies and Kittens."
Here's how to play: imagine you have two boxes, one of which has a number of puppies and the other a number of kittens.
Two players alternate turns in which they take some number of puppies or kittens to a good home so long as one of the following conditions is met.
The winner is the player who removes the last pet.
Thinking visually, we find an equivalent version of the game that Martin Gardner called "Corner the Lady." Imagine an infinite chessboard occupying, say, the first quadrant of the plane. The players take turns moving a queen, which starts out at some location, in the usual horizontal, vertical, and diagonal directions so long as she moves toward the origin. The winner of the game is the one who moves the queen to the origin.
Note: To see why this game is equivalent to "Puppies and Kittens," imagine one axis is labeled “puppies,” and one “kittens.” The queen’s diagonal moves correspond to removing an equal number of puppies and kittens, while its horizontal or vertical moves correspond to removing only puppies or kittens. Moving to the origin amounts to removing the last pet(s).
Finding winning positions
Our goal is to determine and characterize the positions on the board that guarantee a win if we move to one of them. The first position is simple: if we can move to the origin $(0,0)$, we win.
But now we can also see more: if we move to a position that allows our opponent to move to $(0,0)$, then we lose. Therefore, the shaded gray squares are losing positions.
Here is the key for finding more winning positions; if we move to a position that forces our opponent to move to a losing position, then we will win. Therefore, the positions $(1,2)$ and $(2,1)$ are winning positions.
Of course, the game has a natural symmetry so if $(x,y)$ is a winning position, then $(y,x)$ is as well.
Our new winning positions produce a new set of losing positions; for instance, if we move to a position that allows our opponent to move to $(1,2)$ or $(2,1)$, then we will lose.
We next identify $(3,5)$ and $(5,3)$ as winning positions,
which leads to a new set of losing positions and so on.
But in fact, this suggests an algorithm for constructing the winning positions. Let's focus on the winning positions $(x_n,y_n)$ for which $y_n > x_n$. We can construct the following table: $$ \begin{array}{|c||c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 \\ \hline \hline x_n & 0 & 1 & 3 \\ \hline y_n & 0 & 2 & 5 \\ \hline \end{array} $$ which gives the winning positions shown in the figure.
Since we want to leave our opponent with only the option of moving to a losing position, the next winning position appears in a column without a winning position. Due to the symmetry of the game, the columns we have seen that have winning positions are simply given by the coordinates in the table; namely, $C = \{0,1,2,3,5\}$ is the set of columns having winning positions.
Notice that the smallest positive integer not in $C$ is 4, which tells us that the fourth column has no winning entries. Therefore, $x_3 = 4$.
How do we find $y_3$? We need to avoid the diagonals formed by the first few winning positions. Notice that these satisfy $|y_j - x_j| \leq 2$ so to avoid one of these diagonals, we choose $y_3 - x_3 = 3$. Hence, $y_3 = 7$, and we obtain the next winning position $(x_3,y_3) = (4,7)$ giving us the next entry in our table: $$ \begin{array}{|c||c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 \\ \hline \hline x_n & 0 & 1 & 3 & 4 \\ \hline y_n & 0 & 2 & 5 & 7 \\ \hline \end{array} $$
This demonstrates how we can construct all the winning positions inductively:
$$ \begin{array}{|c||c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & \ldots \\ \hline \hline x_n & 0 & 1 & 3 & 4 & 6 & 8 & \ldots \\ \hline y_n & 0 & 2 & 5 & 7 & 10 & 13 & \ldots \\ \hline \end{array} $$
Beatty sequences
There is a particularly nice representation of these coordinates that allows us to describe $(x_n, y_n)$ without reference to the recursive construction. By $X$, we denote the set of the positive $x$-coordinates in the table; likewise, $Y$ denotes the positive $y$-coordinates. In particular, $$ \begin{aligned} X & {}={} \{1,3,4,6,8,\ldots\} \\ Y & {}={} \{2,5,7,10,13,\ldots\} \\ \end{aligned} $$
Notice first that $X$ and $Y$ are disjoint since any common integer would label a column having two winning positions due to the symmetry of the game. Second, the recursive construction shows that their union is the set of positive integers. In other words, $X$ and $Y$ form a partition of the positive integers.
In fact, these sequences are examples of what are known variously as Beatty sequences or spectra, as we now explain. Remember that the floor of a real number $x$ is the largest integer less than or equal to $x$. We denote the floor of $x$ by $\lfloor x\rfloor$ so, for example, we have $\floor{2.7} = 2$. Similarly, the fractional part of a real number $x$ is $\fractional{x} = x - \floor{x}$ so that $\fractional{2.7} = 0.7$.
The Beatty sequence defined by a real number $\alpha$ is the set of integers $${\cal B}_{\alpha} = \{\floor{\alpha}, \floor{2\alpha},\floor{3\alpha}, \ldots\,\floor{n\alpha},\ldots\}.$$ For instance, $${\cal B}_{2.7} = \{2, 5, 8, 10,\ldots\}.$$
Beatty's theorem asserts that
The Beatty sequences of two irrationals $\alpha$ and $\beta$ partition the positive integers if and only if $$ \frac1\alpha + \frac1\beta = 1. $$
To understand why this is true, we will count the number of elements in ${\cal B}_{\alpha}$ that are less than or equal to some integer $N$ and denote this count by $\#\{\alpha, N\}$. This count is also the largest $n$ such $\floor{n\alpha} \leq N$. We then have $$ \begin{aligned} n\alpha & {}\lt{} N+1 \\ n & {}\lt{} \frac{N+1}{\alpha}, \\ \end{aligned} $$ which shows that $$ \#\{\alpha, N\} = \floor{\frac{N+1}{\alpha}} = \frac{N+1}{\alpha} - \fractional{\frac{N+1}{\alpha}}. $$
Suppose now that we have two irrationals $\alpha$ and $\beta$ satisfying $$ \frac1\alpha + \frac1\beta = 1. $$ This leads to $$ \begin{aligned} \#\{\alpha,N\} + \#\{\beta, N\} & {}={} \frac{N+1}{\alpha} - \fractional{\frac{N+1}{\alpha}} + \frac{N+1}{\beta} - \fractional{\frac{N+1}{\beta}} \\ & {}={} (N+1)\left(\frac{1}{\alpha}+\frac1{\beta}\right) - \left(\fractional{\frac{N+1}{\alpha}} + \fractional{\frac{N+1}{\beta}}\right) \\ & {}={} N+1 - \left(\fractional{\frac{N+1}{\alpha}} + \fractional{\frac{N+1}{\beta}}\right) \\ & {}={} N. \end{aligned} $$
To summarize, we have $$ \#\{\alpha,N\} + \#\{\beta, N\} = N $$ for all $N$, which is enough to imply that ${\cal B}_\alpha$ and ${\cal B}_\beta$ partition the integers. To see why, note that $$ \#\{\alpha,1\} + \#\{\beta, 1\} = 1, $$ which means that $1$ belongs to exactly one of ${\cal B}_\alpha$ and ${\cal B}_\beta$. In the same way, $$ \#\{\alpha,N\} + \#\{\beta, N\} - \left( \#\{\alpha,N-1\} + \#\{\beta, N-1\}\right) = 1, $$ which means that $N$ belongs to exactly one of these sequences. This explains why Beatty's theorem holds.
Suppose that our sequences $X$ and $Y$, formed from winning positions in Wythoff's Nim, are Beatty sequences: $X={\cal B}_\alpha$ and $Y={\cal B}_\beta$, for some irrationals $\alpha$ and $\beta$. Then we have $$ \begin{aligned} x_n & {}={} \floor{n\alpha} \\ y_n & {}={} \floor{n\beta} \\ \end{aligned} $$ If we also remember that $y_n = x_n + n$, we see that $\beta = \alpha + 1$. Because $X$ and $Y$ partiion the integers, we also have $$ \begin{aligned} \frac1\alpha + \frac1\beta & {}={} 1 \\ \frac1\alpha + \frac1{\alpha+1} & {}={} 1 \\ \alpha^2 + \alpha & {}={} 2\alpha+1 \\ \alpha^2 - \alpha - 1& {}={} 0. \\ \end{aligned} $$ This shows that $$ \alpha = \frac{1+\sqrt{5}}{2} = \phi = 1.618\ldots, $$ which is the golden ratio, one of mathematics' celebrated numbers.
To this point, we have only shown that $X={\cal B}_{\phi}$ and $Y={\cal B}_{\phi + 1}$ if we assume that $X$ and $Y$ are Beatty sequences. However, the sequences $X$ and $Y$ $$ \begin{array}{|c||c|c|c|c|c|c|c|c|c|} \hline n & 1 & 2 & 3 & 4 & 5 & \ldots \\ \hline \hline x_n & 1 & 3 & 4 & 6 & 8 & \ldots \\ \hline y_n & 2 & 5 & 7 & 10 & 13 & \ldots \\ \hline \end{array} $$ satisfy the following three properties:
In fact, these properties uniquely determine the sequences $x_n$ and $y_n$. Moreover, these properties are also satisfied by the Beatty sequences ${\cal B}_\phi$ and ${\cal B}_{\phi+1}$, which explains why $$ \begin{aligned} x_n & {}={} \floor{n\phi} \\ y_n & {}={} \floor{n(\phi+1)}. \\ \end{aligned} $$
Fibonacci sequences
Of course, anytime we have a sequence associated to the golden ratio, we expect that the Fibonacci numbers are lurking somewhere nearby. This becomes apparent if we extend the table somewhat: $$ \begin{array}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline \hline x_n & 1 & 3 & 4 & 6 & 8 & 9 & 11 & 12 & 14 & 16 & 17 & 19 & 21 \\ \hline y_n & 2 & 5 & 7 & 10 & 13 & 15 & 18 & 20 & 23 & 26 & 28 & 31 & 34 \\ \hline \end{array} $$
Here we see that $$ \begin{aligned} & n = 1: x_1 = 1, y_1 = 2 \\ & n = 2: x_2 = 3, y_1 = 5 \\ & n = 5: x_5 = 8, y_5 = 13 \\ & n = 13: x_{13} = 21, y_{13} = 34 \\ \end{aligned} $$ This pattern continues and is, in fact, relatively straightforward to verify after first confirming the identity: $$ x_{y_n} = x_n+y_n. $$ For instance, when $n=3$, we have $x_{y_3} = x_7 = x_3+y_3 = 11$.
In the same way, many other Fibonacci-like sequences emerge. For instance, the sequence $4,7,11,18,29,47,\ldots$, which satisfies the same recurrence relation as the Fibonacci numbers, appears as $$ \begin{aligned} & n = 3: x_3 =4, y_3=7 \\ & n = 7: x_7=11,y_7=18 \\ & n = 18: x_{18}=29,y_{18}=47 \\ \end{aligned} $$ Every winning position $(x_j, y_j)$ generates such a sequence.
Summary
The literature on Wythoff's Nim is quite extensive. In his original 1907 paper on the subject, Wythoff claims that he pulled $x_n = \floor{n\phi}$ "out of the hat." A proof appears in Coxeter's 1953 paper.
Several connections to the Fibonacci numbers, especially the Fibonacci number system, are explored in the papers by Sibler and Carlitz, et al. The survey article by Duchêne, et al places these ideas in a broader number theoretic context.
I am grateful to Paul Zeitz for introducing me to this game.
References
-
Willem Wythoff. A modification of the game of nim. Nieuw Archief voor wiskunde. 2 (1905-07) 199-202.
-
H.S.M. Coxeter. The golden section, Phyllotaxis and Wythoff's game. Scripta Math. 19 (1953) 135-143.
-
Eric Duchêne, Aviezri Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, Urban Larsson. Wythoff Wisdom. 2016.
-
Robert Silber. A Fibonacci property of Wythoff pairs. Fibonacci Quarterly. 14 (1976) 380-384.
-
L Carlitz, R. Scoville, and V. E. Hoggatt, Jr. Fibonacci representations. Fibonacci Quarterly. 10 (1972) 1-28.
-
Ronald Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics. Addison-Wesley. 1994.
Graham, Knuth, and Patashnik have a fairly lengthy discussion of Beatty sequences, which they call spectra, and indicate the proof of Beatty's theorem given here.
David Austin 
