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.
© John Scholes
jscholes@kalva.demon.co.uk
18 Sep 2002