Setup
Let there be a board looking like a rectangular table. A piece is placed at any square of the board. Two players play a game. They move the piece in turns. The piece can only be moved to an adjacent square (no diagonal moves). The piece can’t be moved to a square that it has already visited (the starting square counts as visited). A player who can’t make a move loses. Who has a winning strategy: the player who makes a first move or their opponent?
Motivation
This question comes in continuation of this MathSE thread discussing a particular case where the starting square is in the corner of the board. It is proven there (by dividing the board into dominoes) that for an odd area board the second player wins, for an even area board the first player wins.
Reasoning
We can apply the dominoes argument here, too. If the board has even area, one of its sides has even length. We can divide the board into dominies along that even side. The first player has a following winning strategy: he makes a move inside a domino where the piece currently is. The second player then moves to a new domino, the first player again makes a move inside of it, and so on. It is clear that the first player always has a possible move, so the second player eventually loses.
Now let’s consider a board of odd area. An answer to the question starts to depend on a starting square! Let us color the board in a chess-like manner. Since the area of the board is odd, its sides are of odd length, and all four corners are of the same color. Let it be blue color.
It is easy to see that if a starting square is blue, then the rest of the board can be divided into dominoes. Since all four corners and the starting square share the same color, the parity of all four distances from the starting square to the borders is the same. If all the distances are odd, we can make a frame around the starting square, and the rest of the board is split into four rectangles with an even side:
If all the distances to the borders are even, we can make rows of dominoes towards the borders and, again, get four even-sided rectangles.
The second player has a winning strategy. The first player moves into a new domino, the second player makes a move inside of it. This process iterates. The second player always has a move and eventually wins.
Now, what if a starting square is not blue, but grey? The board can’t be split into dominoes, since it has odd area. The rest of the board can’t be split into dominoes either, since the number of the blue squares is greater than the number of grey squares by $2$, but each domino takes exactly one square of each color.
It is easy to see, that on the board $3\times3$ the first player wins no matter what players do. It seems the same is true for the board $3\times5$.
Question
Who has a winning strategy in the case of an odd area board, when a starting square is grey? Is it true that the first player has a way to guarantee a win? Is it true that the first player wins no matter what the players do?
Best Answer
Yes, the first player wins on an odd x odd board if the knight starts on gray square (where the board is colored like a checkerboard such that the corners are blue).
To describe the first player's winning strategy, tile almost all of the board with dominoes, where only one corner is uncovered. The first move will be to the other half of the domino containing the starting square. For all subsequent moves, the second player will move into a new domino, and the first player moves to the other square in that domino.
Note that the second player can never move onto the uncovered square, because the second player always moves onto a gray square.