Open Problem Garden - Square achievement game on an n x n grid - Comments

A new reference (re: Square achievement game on an n x n grid)

Carolus — Tue, 13 Sep 2011 03:34:49 +0200

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 .

On drawn games for n up to 14 (re: Square achievement game on an n x n grid)

Carolus — Sun, 14 Aug 2011 23:29:05 +0200

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.

This is not mathematics (re: Square achievement game on an n x n grid)

porton — Sat, 13 Aug 2011 22:22:55 +0200

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

An URL of the technical report version of the referenced article (re: Square achievement game on an n x n grid)

Anonymous — Sat, 13 Aug 2011 15:59:14 +0200

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

Drawn game for n=12 (re: Square achievement game on an n x n grid)

Carolus — Sat, 13 Aug 2011 02:03:15 +0200

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

A list of square-free end-configurations for n from 3 to 11 (re: Square achievement game on an n x n grid)

Carolus — Sat, 13 Aug 2011 01:48:15 +0200

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

I withdraw the conclusion (re: Square achievement game on an n x n grid)

Carolus — Sat, 13 Aug 2011 01:43:41 +0200

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 (re: Square achievement game on an n x n grid)

Carolus — Fri, 12 Aug 2011 00:39:19 +0200

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

Drawn games for grid sizes from 3 to 11 (re: Square achievement game on an n x n grid)

Carolus — Thu, 11 Aug 2011 19:17:15 +0200

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.

Square achievement game on an n x n grid

Martin Erickson — Tue, 29 Jun 2010 16:29:51 +0200

Author(s): Erickson

Subject: Combinatorics

Problem Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an 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.