Board game on a $m\times n$ board - winning strategy

Question

Two friends, $A$ and $B$, play a game with one single game piece on a rectangular board with $m$ rows and $n$ columns. $A$ begins the game by moving the game piece from its starting point $(1, 1)$ to either $(1, 2)$ or $(2,1)$ i.e one can only move one step in a horizontal or vertical direction every move. No point is allowed to be entered twice. The player that no longer can make any move loses.

Is there any winning strategy?

Intuitively, it feels like we need to consider rows and columns with equal and non-equal parities, and I tried to reduce the problem to smaller cases, but it gave me nothing. Any suggestions?

Answer 1

Yes, there is a winning strategy. In a two-player game with perfect information that can only end in a win or a loss, there is always a winning strategy for one of the players.

Answer 2

To keep track of what squares have been used, say the squares are initially white, and you colour them black when the piece leaves them. Thus a game position consists of a set of black squares and a white square containing the piece. It is $A$'s move if the number of black squares is even.

In principle, you can label each possible game position as a win for $A$ or $B$: the position is a win for the player whose move it is if there is at least one legal move that goes to a position that is a win for this player, otherwise it is a win for the other player. Start with positions where all but one square are black, and work backwards.

Of course this will not be computationally feasible unless $m$ and $n$ are very small, because the number of possible positions is large.

Answer 3

If either $m$ or $n$ (or both) is even, then an $m\times n$ board can be tiled by $2\times 1$ rectangles. Player $A$ then has a winning strategy: always move the piece to the other square of the $2\times 1$ rectangle it is currently in. Player B is then forced to move the piece to a new $2\times 1$ rectangle, and the process repeats.

In the event that $m$ and $n$ are odd, then an $m\times n$ board with the initial corner square removed can be tiled by $2\times 1$ rectangles. Player B then has a winning strategy, which is the same as Player A's strategy above: always move the piece to the other square of the $2\times 1$ rectangle it is currently in. The strategy is available to Player B in this case because Player A's first move must put the piece in a new $2\times 1$ rectangle.