5
$\begingroup$

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 in horisontal or vertical direction, one step 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?

$\endgroup$
  • $\begingroup$ So you can always move the piece one unit up, down, left or right as long as it stays on the board and doesn't re-enter a previously occurring square? $\endgroup$ – Robert Israel Oct 14 '15 at 22:20
  • 1
    $\begingroup$ If $m=2$, player $A$ has an easy winning strategy: keep the game piece in its current column, forcing $B$ to move it to the next column. $\endgroup$ – Barry Cipra Oct 14 '15 at 22:28
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I really cannot convince myself about a winning strategy in the general case $m \times n$. As Barry Cipra pointed out, A has clearly a winning strategy when $m=2$, but I can't see it as clearly otherwise. $\endgroup$ – Icosahedron Oct 15 '15 at 10:01
  • $\begingroup$ We don't know what the winning strategy is, but because everything is finite it's clear there must be one, for one player or the other. $\endgroup$ – Robert Israel Oct 15 '15 at 15:29
  • $\begingroup$ @RobertIsrael, in case you haven't seen Julian Rosen's remarkably simple solution, we now do know what the winning strategy is. $\endgroup$ – Barry Cipra Oct 19 '15 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.