Question 2.6.19: Two players play the following game on a 100 × 100 board. Th......
Two players play the following game on a 100 × 100 board. The first player marks a free square, then the second player puts a 1 × 2 domino down covering two free squares, one of which is marked. This continues until one player is unable to move. The first player wins if the entire board is covered, otherwise the second player wins. Which player has a winning strategy?
The first player has a winning strategy. Let us say a position is stable if every square below or to the right of a free square is free. Then we claim the first player can always ensure that on his turn, either the position is stable or there is a free square with exactly one free neighbor (or both).
Let us label the square in the i-th row and j-th column as (i, j), with (1, 1) in the top left. We call a free square a corner if is not below or to the right of another free square. Let (a_{1},b_{1}),\;(a_{2},b_{2}),\;.\;.\;.\;,(a_{k},b_{k}) be the corners from top to bottom.
First notice that if (a, b) is a corner such that both (a + 1, b − 1) and (a − 1, b + 1) are nonfree (or off the board), then the first player may mark (a, b), and however the second player moves, the result will be a stable position. More generally, if (a, b),(a + 1, b − 1), · · · ,(a + k, b − k) are corners and (a − 1, b + 1) and (a + k + 1, b − k − 1) are both nonfree or off the board, the first player can be sure to return to a stable position.
To show this, first note that we cannot have both a = 1 and b − k = 1, or else the number of nonfree squares would be odd, which is impossible. Without loss of generality, assume that b − k ≠ 1 is not the final corner. The first player now marks (a, b). If the second player covers (a, b) and (a, b + 1), the position is again stable. Otherwise, the first player marks (a + 1, b − 1) and the second player is forced to cover it and (a + 2, b − 1). Then the first player marks (a + 2, b − 2) and the second player is forced to cover it and (a + 3, b − 2), and so on. After (a + k, b − k) is marked, the result is a stable position. (Note that the assumption b − k ≠ 1 ensures that the moves described do not cross the edge of the board.)
To finish the proof, we need to show that such a chain of corners must exist. Write the labels (a_{1},b_{1}),\ldots,(a_{k},b_{k}) in a row, and join two adjacent labels by a segment if they are of the form (a, b),(a + 1, b − 1). If two adjacent labels (a, b),(a + i, b − j) are not joined by a segment, then either i = 1 or j = 1 but not both. If i = 1, draw an arrow between the labels pointing towards (a + i, b − j); otherwise draw the arrow the other way. Also draw arrows pointing to (a_{1},b_{1}) and (a_{k},b_{k}). There is now one more chain of corners (joined by segments) than arrows, so some chain has two arrows pointing to it. That chain satisfies the condition above, so the first player can use it to create another stable position. Consequently, the first player can ensure victory.