### 35th IMO 1994 shortlist

Problem C6

Two players play alternatively on an infinite square grid. The first player puts a X in an empty cell and the second player puts a O in an empty cell. The first player wins if he gets 11 adjacent Xs in a line, horizontally, vertically or diagonally. Show that the second player can always prevent the first player from winning.

Solution

Consider the following 10 x 10 square. There is one pair of numbered squares in every row, column and diagonal of length 5 or more. [Eg in the rows we have 6, 8, 12, 18, 24, 27, 30, 34, 41, 42.] Repeat this square indefinitely. Then any line of 11 adjacent squares must include a numbered pair. Whenever the first player plays on a numbered square, the second player plays on the other number of the pair.

``` x   1   2   3   4   5   6   6   7   x
8   8   1   2   3   4   5   9   7  10
11  12  12   x  13  14  15   9  10  16
11  17  18  18  13  14  15   x  16  19
17  20   x  21  22  23  24  24  19  25
20  26   x  21  23  22  27  27  25  28
26  29   x   x   x   x  30  30  28  31
29  32  33   x   x   x   x  34  34  31
32  35  33  36  37  38  39  40  41  41
x  35  42  42  36  37  38  39  40   x
```
[Note that to prove the result for 11 in this way the square can be at most 10 x 10 (not 11 x 11).]

Comment

This, of course, is the basis for a well-known game. It is usually played as "five in a row". The first player to get 5 of his symbols adjacent in a line wins. The first player clearly has an advantage, but a good player playing second will regularly win against a novice.

The official solutions note that as proposed by Finland the problem simply required the second player to be able to stop the first player getting N in a line for N sufficiently large, and states that N = 11 was the best the problems committee could do. But the best result must be substantially lower. The first player can win easily with N = 5. The answer may be as low as N = 6.