3
$\begingroup$

Wythoff Nim is an impartial game where 2 players take turns in reducing the heights of two finite heaps of tokens. Two types of moves are allowed

(I) Remove any number of tokens from precisely one of the heaps, at least one and at most a whole heap. (These are the allowed moves in 2 heap Nim.)

(II) Remove the same number of tokens from both heaps, at least one from each heap and at most the number of tokens in the smallest heap.

The positions of an impartial game are partitioned into P and N. The second player to move wins if and only if the position is in P. The unique teminal position for both Nim and Wythoff Nim is empty heaps.

The P-positions of 2 heap Nim are all configurations with the same number of tokens in both heaps. The P-positions of Wythoff Nim are of the forms $(\lfloor \phi n\rfloor, \lfloor\phi^2 n\rfloor),(\lfloor\phi^2 n\rfloor,\lfloor\phi n\rfloor), n\in {\bf Z}_{\ge 0}$, where $\phi = \frac{1 + \sqrt{5}}{2}$.

It is clear that Wythoff Nim is an extension of Nim. By adjoining the type (II) moves to the game of Nim the unique "accumulation point" of P-positions of Nim has \emph{split} into two new accumulation points of P-positions of Wythoff Nim.

We wonder whether this splitting of P-positions continues if we adjoin the following new type of (symmetric) moves to the game of Wythoff Nim.

(III) Remove $t>0$ tokens from one of the heaps and $2t$ tokens from the other, provided the remaining heap sizes are non-negative.

The initial (upper) P-positions of this new game (called (1,2)-GDWN) are $(0,0), (1,3), (2,6), (4,5),\ldots$.

Experimental results gives four distinct "accumulation points" for the P-positions of this game (with upper convergents of ratios of heap sizes $1.478\ldots$ and $2.247\ldots$). It is known that the upper P-positions of the new game do not converge.

It is not hard to prove that the non-terminal P-positions partition the positive integers. (Use that the type (I) and (II) moves are a subset of all moves.)

$\endgroup$
1
  • $\begingroup$ I have recently proved a split. It is available at the arXiv. However the convergence properties of the splitted sequences remains a mystery. Included is an interesting Lemma bounding lower asymptotic density of P-positions lower heap sizes for any extension of Wythoff Nim to the inverse of the Golden section. $\endgroup$
    – Urban
    Jul 10, 2012 at 16:45

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.