Problem

Source: 2018 Pan-African Shortlist - C3

Tags: game, combinatorics, Chessboard



A game is played on an $m \times n$ chessboard. At the beginning, there is a coin on one of the squares. Two players take turns to move the coin to an adjacent square (horizontally or vertically). The coin may never be moved to a square that has been occupied before. If a player cannot move any more, he loses. Prove: If the size (number of squares) of the board is even, then the player to move first has a winning strategy, regardless of the initial position. If the size of the board is odd, then the player to move first has a winning strategy if and only if the coin is initially placed on a square whose colour is not the same as the colour of the corners.