Sequences and games generalizing the combinatorial game of Wythoff Nim

Sammanfattning: One single Queen is placed on an arbitrary starting position of a (large) Chess board. Two players alternate in moving the Queen as in a game of Chess but with the restriction that the $L^1$ distance to the lower left corner, position $(0,0)$, must decrease. The player who moves there wins. Let $phi =frac{1+sqrt{5}}{2}$, the golden ratio. In 1907 W. A. Wythoff proved that the second player wins if and only if the coordinates of the starting position are of the form ${a_n,b_n}$, where $a_n=leftlfloor nphi ight floor, b_n=a_n+n$ for some non-negative integer $n$. Here, we introduce the game of emph{Imitation Nim}, a emph{move-size dynamic} restriction on the classical game of (2-pile) Nim. We prove that this game is a 'dual' of emph{Wythoff Nim} in the sense that the latter has the same solution/$P$-positions as the former. On the one hand we define extensions and restrictions to Wythoff Nim---including the classical generalizations by I.G. Connell (1959) and A.S. Fraenkel (1982)---and Imitation Nim. All our games are purely combinatorial, so there are no 'hidden cards' and no 'chance device'. In fact we only study so-called emph{Impartial games} where the set of options does not depend on whose turn it is. In particular we introduce rook-type and bishop-type emph{blocking manoeuvres/Muller twists} to Wythoff Nim: For each move, the previous player may 'block off' a predetermined number of next player options. We study the solutions of the new games and for each blocking manoeuvre give non-blocking dual game rules. On the other hand, observing that the pair of sequences $(a_n)$ and $(b_n)$---viewed as a permutation of the natural numbers which takes $a_n$ to $b_n$ and $b_n$ to $a_n$---may be generated by a 'greedy' algorithm, we study extensive generalizations to these. We also give interpretations of our sequences as so-called emph{Interspersion arrays} and/or emph{Beatty sequences}.