Question 18
Two players play a game by moving a piece on an $n \times n$ chessboard. The piece is initially in a corner square. Each player may move the piece to any adjacent square (which shares a side with its current square), except that the piece may never occupy the same square twice. The first player who is unable to move loses. Show that for even $n$ the first player can always win, and for odd $n$ the second player can always win. Who wins if the piece is initially on a square adjacent to the corner?