# Square achievement game on an n x n grid

 Importance: Medium ✭✭
 Author(s): Erickson, Martin
 Subject: Combinatorics
 Keywords: game
 Posted by: Martin Erickson on: June 29th, 2010

\begin{problem} Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $n \times n$ grid. The first player (if any) to occupy four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play?

Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15. \end{problem}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

## Bibliography

R. Bacher and S. Eliahou, "Extremal binary matrices without constant 2-squares," J. of Combinatorics, Volume 1, Number 1, 77-100, 2010.

* Erickson, Martin, "Pearls of Discrete Mathematics," CRC Press, 2010

* indicates original appearance(s) of problem.

### A new reference

My new article "Guaranteed successful strategies for a square achievement game on an n by n grid" concerning that problem is now accessible via http://arxiv.org/abs/1109.2341 .

### This is not mathematics

I suspect this problem can be solved only with brute force for every particular n and is not a nice mathematical conjecture (just like the question who wins in chess, white or black, playing both with the optimal strategy).

-- Victor Porton - http://www.mathematics21.org

### On drawn games for n up to 14

I should have read the referenced article by Bacher and Eliahou before trying to find drawn games. But I've read it now.
Among many other things, the authors describe parametric families of square-free configurations for n=14.
Not all of those configurations do provide the required relation of the numbers of symbols of both sorts needed to be an end-configuration of the game.
But one can, for example, take the family A1, give the variables x1 up to x8 the value 0 (or O, resp.) and the variables x9 up to x16 the value 1 (or X, resp.).
Then the numbers of symbols of both sorts are equal and that square-free configuration is also a correct end-configuration of the game for n=14.

### An URL of the technical report version of the referenced article

http://www-lmpa.univ-littoral.fr/publications/articles/lmpa404.pdf

### Drawn game for n=12

I've had not much hope to find one in an acceptable time but after running another couple of hours my program delivered this square-free end-configuration for n=12:
 oooooooxxxox xoxoxoxoxoxx xoxxooxooxxo oooxxxooxxoo oxooxoxxxoxo xxxooxoxoxox xoxxxxooooxx oxoxoxxoxoox ooxoooxxoxox xxooxooxoxxo oooxoxoxooxx xoxxxoxxxoox 

### Drawn games for grid sizes from 3 to 11

Running a self-written program I've found the square-less end-configurations to be listed (because of the 1000 characters limit) in a comment of this comment for the grid sizes (n) from 3 to 11.
If I understand the note in the problem text right, this proofs that there is no sure winning strategy for those sizes.
On my 1 GHz Celeron/PIII the search for n=11 took 65 seconds.
But I gave up the search for n=12 after circa 12 hours of calculation estimating the 130-fold duration for the complete search. On the other side: In the first 8 hours there was a square-less configuration just before the occupation of the last field.

### I withdraw the conclusion

The note in the problem text let me assume that it is proven that if the game for some grid size n must have a winner there is a sure winning strategy for the first player.
Taking in account that implication only, one cannot, as I did, conclude that there is no sure winning strategy if a game could be drawn.

### Text corrections

It should stand 'proves' instead of 'proofs' and 'square-free' instead of 'square-less'.

### A list of square-free end-configurations for n from 3 to 11

 3 ooo oxo xxx 4 oooo oxox xoxx xxxo 5 ooooo oxoxo ooxxo xoxox xxxxx 6 oooooo oxoxox ooxxoo xoxoxx xxxxox xooxxx 7 ooooooo oxoxoxo ooxxoox xxooxxx oxoxxox xxxooox xoxxxxo 8 oooooooo oxoxoxox ooxxooxx xxooxxxo oxoxxoxx xxxoxoox xoxoxxox xooooxxx 9 ooooooooo oxoxoxoxo ooxxooxxo xoooxxxoo oxoxxoxxx xxxoxooox xoxoxxoxx xxoxoxoox oxxxoxxox 10 ooooooooox oxoxoxoxoo oxxooxxxxo ooxxxoxoxo oxooxoxxoo xxxooooxxx xoxoxxoxox xooxoxxoxx xxoxxoxoox xoxxooxxox 11 oooooooooxx oxoxoxxoxox oxxoxxooxox ooxxxooxxoo oxooxoxxoox xxxxoooooxx xoxooxoxxxo xooxoxxoxoo xxooxxoooxo xoxxxooxoxx xoxoxoxxxxo