Covering paired squares on a $10 \times 10$ board

91 Views Asked by At

In a game, the board is a $10 \times 10$ table (in the style of a chessboard). Two players make moves in turns. In a single step, a player covers two neighboring free cells of the table by $2\times 1$ tile. The player who cannot make a step loses the game. Who has a winning strategy - the player who starts the game or his opponent?

2

There are 2 best solutions below

0
On BEST ANSWER

This game is called Cram and the second player has a winning strategy. For every domino the first player places, the second player places a domino at the same spot rotated $180^\circ$ around the original board's centre, thus always leaving a $C_2$-symmetric board to the first player; this is always possible at every move because of the symmetry and because there is no way a domino can be placed "centrally" (either a centre square or edge) to ruin the strategy. Eventually the first player will be unable to move and lose, handing the win to the second player.

3
On

Correction.

My answer is marked as correct though it is in fact inaccurate. The game the OP is describing is called Cram, see this Wikipedia page, in which an argument is discussed as to why the second player will have a winning strategy in the case of a $10 \times 10$ board.

Old answer.

I initially misrecognised the problem as a very similar game called Domineering, which also has its own Wikipedia page. Curiously, unlike Cram, Domineering seems to lack the symmetry to have straightforward strategies like Cram does, and finding an optimal strategy for Domineering seems to be hard. For a $10 \times 10$ board, the Wikipedia page claims that a perfect strategy was found in the Master thesis of Nathan Bullock.