On a $5\times 5$ chessboard, two players play the following game: The first player places a knight on some square. Then the players alternately move the knight according to the rules of chess, starting with the second player. It is not allowed to move the knight to a square that was visited previously. The player who cannot move loses. Which of the two players has a winning strategy?
Problem
Source: Baltic Way 1997
Tags: combinatorics proposed, combinatorics
29.01.2011 18:30
The first player has the winning strategy. Denote the squares with the chess notation (lower-left corner is A1, lower-right corner is E1, and upper-right corner is E5). The first player puts the knight at a corner. Say it is A1. The second player must move it to either C2 or B3, both equal by symmetry. Assume it's C2. The first player moves the knight to E1. Now, the second player's move is forced to D3. Continuing clearing each corner, the next moves are E5, C4, A5, B3. Next, we move the knight to C1. The second player needs to move it to either A2 or E2, both equal by symmetry. Now, for anywhere the second player moves, the first player replies with a move that doesn't bring the knight to the center. All of the second player's moves are forced (in fact, all of the first player's moves too), which can be verified by the reader. Finally, the knight must be at a space in which the first player can move to the center. Thus, the second player can't move due to the board being full, so the first player wins.
23.05.2023 06:19
Player 1 chooses the center C3. Then picture the board as fully covered with domino pieces (where each piece covers two of the remaining 24 fields). Player 2 moves the knight somewhere and Player 1 chooses the remaining half of the domino piece until the game ends and Player 1 wins.
23.05.2023 06:50
Alternatively, considering the 1728 knight's tours of the 5x5 chessboard, we see that each of them will result in an odd number of moves and thus the first player can guarantee a win on any white square as there are 13 white and 12 black squares.