Two players play alternatively on an infinite square grid. The first player puts an $X$ in an empty cell and the second player puts an $O$ in an empty cell. The first player wins if he gets $11$ adjacent $X$'s in a line - horizontally, vertically or diagonally. Show that the second player can always prevent the first player from winning.
Problem
Source: IMO Shortlist 1994, C6
Tags: combinatorics unsolved, combinatorics, IMO Shortlist, Combinatorial games, game strategy, game
mavropnevma
05.06.2012 12:24
It is known that a "$k$-in-a-row" game is a draw for $k\geq 8$, with a simple pairing strategy for $k\geq 9$. See http://www.weijima.com/index.php?option=com_content&view=article&id=11&Itemid=15. The $5$-in-a-row is also called Gomoku, and its outcome is not known. $4$-in-a-row (and less) are a win for first player.
mindpuzzler
30.06.2017 11:15
Divide the infinite grid into staggered columns of 3x3 grids, and treat them as separate tic-tac-toe games where you can force a draw. To get 11-in-a-row, it's clear that should it occur in a column or row, one must have 3-in-row in one of those 3x3 grids. After drawing it out, we can see that at most ten can be placed in a diagonal so that none of the 3x3 grids has 3 diagonally in a row.
th1nq3r
08.07.2022 03:31
Our intuition leads us to first consider a finite grid. Most easy to work with being a square. Playing around with various squares, we begin to develop a strategy to tie in an odd square board. (Boards of the form $(2k + 1) \times (2k + 1)$ for some integer $k$).
Lemma: We have a winning strategy for $(2k + 1) \times (2k + 1)$ boards described as follows. If the first player $A$ puts an $X$ in a corner of a square board, then reflect over the line $"y = x"$. If $A$ marks an $X$ on an edge that is on the top or bottom of a square board, $B$ places an $O$ to the reflection of $X$ over the $y$-axis. If $A$ marks an $X$ on an edge that is on the left or right of a square board, $B$ places and $O$ to the reflection of $X$ over the $x$-axis.
Proof of lemmaWe induct on $k$. For $k = 1$, we actually have a slight variation in the figure below. If $k = 2$, then this strategy holds true. Now assume this is true for $k - 1$. We show it is true for $k$. If $A$ marks and $X$ anywhere that isn't an edge then this is simply the case for $k - 1$ or smaller. Now if $A$ marks an $X$ in a corner, $(\pm 2k + 1) \times (\pm 2k + 1)$, then we just swap the signs and now it is guaranteed $A$ cannot make any diagonal of length $2k + 1$.
If $A$ marks an $X$ on an edge from the $x$-axis, $(x, \pm 2k + 1), x \neq 0$, then mirorr about the $y - axis$. This guarantees he cannot make a row of $2k + 1$ adjacent $x$'s along that row. If $x = 0$, then mirror about the $x$-axis.
Similarly if $A$ marks an $X$ on an edge from the $y$-axis, $(\pm 2k + 1, y), y \neq 0$, then mirror about the $x$-axis. If $y = 0$, mirror about the $y$-axis.
This always guarantees that $A$ can never fully make a row consisting of $2k + 1$ adjacent $X$'s. Thus we have that this strategy holds for the case of the $(2k + 1) \times (2k + 1)$ board. $\blacksquare$
With this lemma we can now implement the following strategy in the case of infinite boards: If $A$ places $X$ somewhere, $B$ should imagine the smallest board of the form $(2k + 1) \times (2k + 1)$ centered at the origin such that $X$ lies on its edges or corners. We then have using the above lemma that we have a winning strategy. $\blacksquare$
Sorry my solution is wrong. Don't read it.
Ali-Seyedpour13
15.11.2022 17:11
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. 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. n 1 2 3 4 5 6 6 7 n 8 8 1 2 3 4 5 9 7 10 11 12 12 n 13 14 15 9 10 16 11 17 18 18 13 14 15 n 16 19 17 20 n 21 22 23 24 24 19 25 20 26 n 21 23 22 27 27 25 28 26 29 n n n n 30 30 28 31 29 32 33 n n n n 34 34 31 32 35 33 36 37 38 39 40 41 41 n 35 42 42 36 37 38 39 40 n (put this numbers respectively in a 10*10 grid and follow the strategy that I have represented earlier.) (if you check the grid you'll see that it doesn't matter what you want to put instead of {n}.) [Note that to prove the result for 11 in this way the square can be at most 10 x 10 (not 11 x 11).]