Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an n x n grid.
The first player to occupy the vertices of a square with horizontal and vertical sides is the winner. What is the smallest n such that the first player has a winning strategy?

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.

share|improve this question
add comment

2 Answers

I realised after I wrote the following answer that I probably have interpreted "square" the wrong way. I expected the winner to construct a 2x2 square submatrix formed by their own symbol. Upon re-reading the question, it seems that the question requires the distance between the rows and columns in the submatrix to be the same. Nonetheless, perhaps you might find this of interest, since it answers a related question.

I found that when n>=4 the o's win. First note that permuting the rows and columns of the matrix does not affect the result, nor does taking the matrix transpose. If it's a win for the o's for some n, then it's also a win for n+1, n+2, etc.

In the diagram below, the o's can force the top diagram (up to equivalence), with x to move. x's move is equivalent to one of the diagrams in the second row. Afterwards, o can play a sequence of forcing moves, illustrated in the column (the yellow highlights where x is forced to play).

It's fairly easy to see that n=3 will be a draw.

share|improve this answer
2  
I believe that in your version of the problem, where the players are trying to form a 2x2 subrgrid in their own symbol, then the game is a draw. The second player can consider the board as tiled in a brick pattern by dominos, and complete each domino that the first player enters. This blocks the 2x2 subgrid pattern. –  Martin Erickson Jun 28 '10 at 15:39
    
@Douglas: what graphic package did you use to produce these neat diagrams? I have been looking precisely for one where it would be easy to do something similar. Thank you. –  Yaakov Baruch Jul 28 '10 at 14:18
2  
Well... I used Excel -- I shrunk the column size, added borders and cell colours to draw these things, then I did a screendump, copy/paste to paintbrush and chop the borders. [yes, it's all a bit hacky] –  Douglas S. Stones Jul 29 '10 at 1:02
add comment

I believe the first player has a winning strategy for N=7.

In the configuration below (with "o" having the next move), "o" can force a win by making a "cross". Note that the "cross" can also be applied to two non-adjacent "o"s in the same row or column.

alt text

The first player plays in the center. The second player has 9 unique responses. I'll consider the 3 most interesting responses here.

Below, the first player places the second "o" next to the first, threatening to make a cross. So, the second player has 2 unique moves available. However, both moves allow the first player to force a few moves and achieve the "cross", as illustrated. (The two starting pieces for the "cross" are marked with a square around them.)

alt text

Another possible position for the initial "x". This is also a win for "o".

alt text

Another possible position for the initial "x". This is also a win for "o". (I omitted 2 branches to save space, but they follow the same pattern).

alt text

I didn't consider the other 6 initial moves for "x", but I think the same techniques can be used to solve them.

FWIW, I'm pretty sure N=5 is a draw. I haven't considered N=6, yet.

share|improve this answer
    
Tom, This is a nice argument. When you mentioned N=5 being a possible draw, I had another look at that and I don't quite have it, but it does appear to be a draw. ---Martin –  user7975 Jul 28 '10 at 12:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.