512 Combinatorial games
17.5 Wythoff’s game ..................
Wythoff’s game is a variant of Nim. Given two piles of marbles, a
player either removes an arbitrary positive amount of marbles from any
one pile, or an equal (positive) amount of marbles from both piles. The
player who makes the last move wins.
We describe the position of the game by the amounts of marbles in
the two piles.
If you can make(2,1), then you will surely win no matter how your
opponent moves. Now, to forbid your opponent to get to this position,
you should occupy(3,5).
The sequence of winning positions: starting with(a 1 ,b 1 )=(1,2),
construct(ak,bk)by setting
ak:= min{c:c>ai,bi,i<k},
bk:=ak+k.
Here are the 18 smallest winning positions for Wythoff’s game:
1 3 4 6 8 9 11 12 14 16 17 19 21 22 24 25 27 29
257101315182023262831343639414447
Theorem 17.5.The winning positions of Wythoff’s game are the pairs
(nφ, nφ^2 ), whereφ=
√5+1
2 is the golden ratio.
