Showing that losing positions in Wythoff's game are generated by $(\lfloor n\phi\rfloor, \lfloor n\phi^2\rfloor)$, where $\phi$ is the golden ratio

Question

A very neat problem in combinatorial game theory:

In Wythoff's Game, how do I show that all the losing positions are generated by the formula

$$\left(\lfloor n\phi\rfloor, \lfloor n\phi^2\rfloor\right)$$ where $n \in \mathbb{N}$ and $\phi$ is the golden ratio?

More precisely, the $k^{\text{th}}$ losing position is $\left(\lfloor k\phi\rfloor, \lfloor k\phi^2\rfloor\right)$ where $k \in \mathbb{N}$ and $\phi$ is the golden ratio.

I have tried this problem for a while and got a way to show that the sequences $\lfloor n\phi\rfloor$ and $\lfloor n\phi^2\rfloor$ are disjoint and their union is $\mathbb{N}$, this can be easily showed using the Beatty's theorem, but I'm unsure how to prove that all the losing positions are generated by the formula $\left(\lfloor n\phi\rfloor, \lfloor n\phi^2\rfloor\right)$.

I have gone through wikipedia and its references for the proof, but it doesn't seem like the proof for the formula is present anywhere in the sources or references.

Any help or hint would be highly appreciated. Thanks.

Answer 1

Wythoff’s argument is actually quite straightforward. He first identifies the $P$-positions (which he calls safe positions), i.e., the positions in which the previous player wins; equivalently, they are the positions in which the player whose turn it is to move must lose, assuming that the other player plays correctly. He lists the first few:

$$\begin{array}{rcc} n:&0&1&2&3&4&5&6&7&8&9&10\\\hline u_n:&0&1&3&4&6&8&9&11&12&14&16\\ \ell_n:&0&2&5&7&10&13&15&18&20&23&26 \end{array}$$

(I’ve shortened his table a bit.) Clearly $\langle 0,0\rangle$ is a $P$-position: if you face this, the previous player has already won. The others in the table can be described as follows. For $n\in\Bbb Z^+$ let $U_n=\{u_k:0\le k<n\}$ and $L_n=\{\ell_k:0\le k<n\}$; then

$$u_n=\min\big(\Bbb Z^+\setminus(U_n\cup L_n)\big)\,,$$

and $\ell_n=u_n+n$.

Let $\mathscr{P}$ be the set of positions generated in this way. To show that $\mathscr{P}$ really is the set of $P$-positions, we need only show that every legal move from a position in $\mathscr{P}$ yields a position not in $\mathscr{P}$, while from every position not in $\mathscr{P}$ there is a legal move to a position in $\mathscr{P}$.

• Suppose first that $\langle u,\ell\rangle$ is a position not in $\mathscr{P}$ such that $u\le\ell$, and let $n=\ell-u$. If $u>u_n$, let $d=u-u_n$; taking $d$ from each pile leaves the position $\langle u_n,\ell_n\rangle\in\mathscr{P}$. If $u<u_n$, there is a $k<n$ such that $u\in\{u_k,\ell_k\}$. If $u=u_k$, removing $\ell-\ell_k$ counters from the larger pile leaves the position $\langle u_k,\ell_k\rangle\in\mathscr{P}$. If $u=\ell_k$, removing $\ell-u_k$ counters from the larger pile also leaves the position $\langle u_k,\ell_k\rangle\in\mathscr{P}$.
• Now let $n\in\Bbb Z^+$, and consider moves from the position $\langle u_n,\ell_n\rangle$. If the result of such a move is in $\mathscr{P}$, it clearly must be $\langle u_k,\ell_k\rangle$ for some $k<n$. But then $$\begin{align*}\ell_n-\ell_k&=(u_n+n)-(u_k+k)\\&=(u_n-u_k)+(n-k)\\&>u_n-u_k\\&>0\,,\end{align*}$$ which is not possible with a legal move. Thus, there is no move from $\langle u_n,\ell_n\rangle$ to a position in $\mathscr{P}$.

This shows that $\mathscr{P}$ really is the set of $P$-positions. (Wythoff did not include the arguments given at the bullet points, merely noting that are easy.)

He then claims essentially that $u_n=\lfloor n\varphi\rfloor$ and $\ell_n=\left\lfloor n\varphi^2\right\rfloor$. Certainly

$$\begin{align*} \left\lfloor n\varphi^2\right\rfloor-\lfloor n\varphi\rfloor&=\lfloor n(\varphi+1)\rfloor-\lfloor n\varphi\rfloor\\ &=\lfloor n\varphi+n\rfloor-\lfloor n\varphi\rfloor\\ &=\lfloor n\varphi\rfloor+n-\lfloor n\varphi\rfloor\\ &=n\\ &=\ell_n-u_n\,, \end{align*}$$

and $\lfloor n\varphi\rfloor=\left\lfloor n\varphi^2\right\rfloor=0$ when $n=0$, so it only remains to show that when $n\ge 1$, $\lfloor n\varphi\rfloor$ is the smallest positive integer not equal to $\lfloor k\varphi\rfloor$ or $\left\lfloor k\varphi^2\right\rfloor$ for any $k\in\{0,\ldots,n-1\}$. He does this by showing that $\langle n\varphi:n\in\Bbb N\rangle$ and $\left\langle n\varphi^2:n\in\Bbb N\right\rangle$ are complementary Beatty sequences, something that you’ve already done.