Wythoff Nim extensions and splitting sequences

Larsson, Urban

Journal of integer sequences, Tome 17 (2014) no. 5.

Résumé

Summary: We study extensions of the classical impartial combinatorial game of Wythoff Nim. The games are played on two heaps of tokens, and have $symmetric$ move options, so that, for any integers $0 \le x \le y$, the outcome of the $upper$ position $(x, y)$ is identical to that of $(y, x)$. First we prove that $\phi ^{-1} = 2/(1+\sqrt 5)$ is a lower bound for the lower asymptotic density of the $x$-coordinates of a given game's $upper$ P-positions. The second result concerns a subfamily, called a Generalized Diagonal Wythoff Nim, recently introduced by Larsson. A certain $split$ of P-positions, distributed in a number of so-called P-beams, was conjectured for many such games. The term $split$ here means that an infinite sector of upper positions is void of P-positions, but with infinitely many upper P-positions above and below it. By using the first result, we prove this conjecture for one of these games, called (1,2)-GDWN, where a player moves as in Wythoff Nim, or instead chooses to remove a positive number of tokens from one heap and twice that number from the other.

Détail

Keywords: combinatorial game, complementary sequence, golden ratio, impartial game, integer sequence, lower asymptotic density, splitting sequence, Wythoff nim