Wythoff's Game. (Wythoff (1907)) The positions of the

Wythoff's game are given by a queen on a chessboard. Players, sitting on the

same side of the board, take turns moving the queen. But the queen may only

be moved vertically down, or horizon-tally to the left or diagonally down to the

left. When the queen reaches the lower left corner, the game is over and the

player to move last wins. Thinking of the squares of the board as vertices and

the allowed moves of the queen as edges of a graph, this be-comes a graph game.

Find the Sprague-Grundy function of the graph by writing in each square of the

8 by 8 chessboard its Sprague-Grundy value.

Suppose you are playing a three-pile subtraction game. For

the rst pile of 18 chips, the rules of Exercise 1 hold. For the second pile of 17

chips, the rules of Exercise 2 apply. For the third pile of 7 chips, the rules of

nim apply. What is the Sprague-Grundy value of this position? Find an optimal

move.