A winning strategy for a player in a $2 \times 2011$ table.

69 Views Asked by At

Consider a $2 \times 2011$ table. Two players in turn place dominoes on it, the first one place only horizontal dominoes and the second one places only vertical dominoes. The dominoes may not overlap. The player who has no legal moves loses the game.

How can we define a winning strategy for a player?

enter image description here

1

There are 1 best solutions below

2
On

The winner is the first player. Imagine dividing the board into $1005$ $2\times 2$ squares, with one $2\times 1$ domino leftover. For each of her first $503$ moves, the first player will cover the bottom half of one of the $2\times 2$ squares. This is always possible, since each move by the second player can obstruct at most one of these squares. Then, for the next $503$ moves, the first player plays in the top half of the blocks she played in earlier. This ensure the first player gets to play $1006$ dominos. After she plays her $1006^\text{th}$ domino, the board is perfectly filled, and player two loses.