CLR cover
Previous problem

Problem 7: Wythoff's Game and Fibonacci Word

Next problem

Wythoff's game, a variant of the game of Nim, is a two-player game of strategy. It is played with two piles of tokens, one being initially non-empty. Players take turns removing either a positive number of tokens from one pile or the same number of tokens from both piles. When there are no tokens left, the game ends and the last player is the winner.

A configuration of the game is described by a pair of natural numbers $(m,n)$, $m\leq n$, where $m$ and $n$ are the number of tokens on the two piles. Note that $(0,n)$ as well as $(n,n)$, $n\gt 0$, are winning configurations. The smallest losing configuration is $(1,2)$ and then all configurations of the form $(m+1,m+2)$, $(1,m)$ and $(2,m)$ for $m\gt 0$ are winning configurations.

It is known that losing configurations follow a regular pattern determined by the golden ratio. Thus, the following question.

Is there any close relation between Wythoff's game and the infinite Fibonacci word?

References

  • W. A. Wythoff. A modification of the game of Nim. Nieuw Arch. Wisk., 8:199-202, 1907/1909.