IMO 1994 SL C6

Origin: FIN | Category: Combinatorics

Problem

On an infinite square grid, two players alternately mark sym- bols on empty cells. The first player always marks X’s, the second O’s. One symbol is marked per turn. The first player wins if there are 11 con- secutive X’s in a row, column, or diagonal. Prove that the second player can prevent the first from winning.

Solution

Tile the table with dominoes and numbers as shown in the picture. The second player will not lose if whenever the first player plays in a cell of a domino, he plays in the other cell of the domino, and when- ever the first player plays on a num- ber, he plays on the same number that is diagonally adjacent.