Consider the following game between two players. The players take turns moving a rock among cells of an m × n matrix. At the beginning of the game (before the first move), the rock is placed in the bottom-right cell of the matrix [cell (m, n)]. Player 1 goes first.
At each turn, the player with the move must push the rock into one of the three cells above or to the left (or both) of the cell where the rock currently sits. That is, the player may move the rock to the cell above the current position, to the cell to the left of the current position, or to the cell diagonal to the current position in the up-left direction, as pictured below.
A player may not move the rock outside of the matrix. The player who is forced to move the rock into the top-left cell of the matrix [cell (1, 1)] loses the game.
(a) Suppose the dimensions of the matrix are 5 × 7. Does either player have a strategy that guarantees a victory? If so, which of the two players has such a strategy?
(b) In general, under what conditions on m and n does player 1 have a winning strategy and under what conditions does player 2 have a winning strategy?