# How many winning configurations can you have in a nxn Tic-Tac-Toe game where players win if a they get n/2 in either a row or column, consecutively.

Just today I had a bet with my friend over the following problem:

How many winning configurations can you have in a nxn Tic-Tac-Toe game where players win if a they get n/2 in either a row or column, consecutively.

n is even.

For example, in a 4x4 game, players win if a they get 2 of their symbols in either a row or column, consecutively.

I bet the figure to be "2 * ( 2 * n ) * ( 3 ** ( n / 2 ) )"

Do I win?

How to proceed if we were to count only draws? ( how many board configurations can there be so that they are always draws - i.e. no one wins )

Note that I do not think that the board always need to have as many X's as there are O's:

Consider a 10x10 board.

At the minimum, the winning player needs to make 5 moves to win, and the loser gets to make 4. So it's not always a filled board with half the cells X and half the cells O.

-
If $n=2$, I count 4 winning configurations, which doesn't fit your formula. Perhaps you'd like to show us why you think your formula works? – Gerry Myerson Nov 21 '10 at 3:28
Yes - I will expand this post to include my reasoning, which is indeed faulty, but I need to know where I went wrong. – user10987 Nov 21 '10 at 3:40
As Gerry says, yes, if $n=2$, then the first player to move obviously wins by picking any one of the four open spots, and the game is over. If $n=3$ (you don't define the game for odd $n$, but let's say for odd $n$, $(n+1)/2$ spaces wins), then the first player to move wins automatically also, because no matter which space they take in the $3 \times 3$ grid, the next player can only block one space, and in the 2nd round, first player easily wins. A similar argument can be used for $n=4$. You don't state whether $A$ and $B$ play intelligently and optimally, or stupidly. More rigor, please. – sleepless in beantown Nov 21 '10 at 5:18
What's the motivation behind this? Homework? Searching for an optimal game strategy? Boredom on a saturday night? Where'd you come up with the problem? How'd you derive your answer, or conjectured answer on the number of configurations? If this is homework, please see that FAQ: mathoverflow.net/faq – sleepless in beantown Nov 21 '10 at 5:20
Note that a lower bound for the number of winning configurations is the number of distinct configurations of the loser: this is strictly more than (n^2 - n) choose (n/2 - 1). As I interpret the post, the poster has lost because his figure is too low for n > 6, and is probably too low for n > 3. Gerhard "Ask Me About System Design" Paseman, 2010.11.21 – Gerhard Paseman Nov 22 '10 at 3:57

The answer depends upon, of course, if the players make their moves intelligently or stupidly. In either case, build an alpha-beta tree of move sequences and search either depth-first or breadth-first, stopping and backtracking as winning configurations are found. However, there are some rigorous points you have not defined about this question, including whether perhaps it came to you as a homework problem. Hoping that this is not the case, here's a take on it:

Yes, if $n=2$, then the first player to move obviously wins by picking any one of the four open spots, and the game is over. If $n=3$ (which you don't define for odd $n$, but lets say for odd $n$, $(n+1)/2$ spaces wins, then the first player to move wins automatically also, because no matter which space they take in the $3 \times 3$ grid, the next player can only block one space, and in the 2nd round, first player easily wins.

For $n=4$, the first player wins, with the same strategy as shown for $n=3$. $A$ picks any square in the $4 \times 4$ grid, $B$ picks any other square but can only block $A$ in one of the two dimensions in which this grid lies, therefore on the first step of the second round, $A$ wins by picking a square adjacent to his first square.

Are you sure that you've thought this out for the smaller grid games?

So for the $4 \times 4$ configuration, assuming that $A$ plays intelligently, there are

$4 \times 4 = 16$ first moves for $A$

$16 - 1 = 15$ first moves for $B$, if $B$ plays stupidly, or either $2, 3,$ or $4$ moves if $B$ plays intelligently

$4 \times 1 + 8 \times 2 + 4 \times 3 = 4+16+12=32$ second moves for $A$ which win the game and end the game ($A$ could have picked one of the $4$ corners, $B$ blocks one way leaving $1$ way for $A$ to play, if $A$ picks one of the non-corner edge pieces (8 ways to do that), then $B$ blocks one way leaving two ways for $A$'s second winning move, and if $A$'s first move is a center piece, $B$ can block one of the $4$ adjacent squares, leaving $3$ adjacent squares for $A$ to pick and win.

So if $A$ and $B$ both play intelligently, the sum of these are the possible games for a $4 \times 4$ grid:

$4 \cdot 2 \cdot 1 + 8 \cdot 3 \cdot 2 + 4 \cdot 4 \cdot 3 = 8 + 48 + 48 = 104$

If $A$ and $B$ do not play intelligently, then the number of possible games is much larger, and the number of "winning configurations" or "end positions" is much larger.

-
$A$'s second move could be any of the $14$ unpicked squares if they played stupidly. – sleepless in beantown Nov 21 '10 at 5:15
The difference between 2nd player intelligence and stupidity is not clear to me - either way, 1st player wins. Also, you've counted the number of move sequences, while OP asked for number of winning configurations. – Gerry Myerson Nov 21 '10 at 5:19
Gerry, if the 2nd player plays "intelligently", $B$ at least tries to block $A$'s move by picking one of the squares adjacent to $A$'s first move. Of course, it is to no avail as $A$ will win on the 2nd round anyway. If $B$ plays stupidly, $B$ picks any of the 15 squares not picked, and $A$ also wins on the next move. It doesn't really matter since $A$ wins as long as $A$ plays intelligently. I don't believe the original poster thought the question out too far, and I can't tell if it was a homework problem or a partially thought out puzzle. It needs to be more rigorous to admit an answer. – sleepless in beantown Nov 21 '10 at 6:10
If both players are playing intelligently, in the poor way which I have defined it, then the number of move sequences which lead to $A$ winning are the total number of winning configurations. I guess if the original poster admits/allows for the possibility of "losing configurations", then both $A$ and $B$ must play like blind buffoons, and the answer is a larger number. Though not the answer the original poster gives. I'm hoping the question will be clarified and explained. Have a good evening, Gerry. – sleepless in beantown Nov 21 '10 at 6:13
@sleepless, you're right about number of move sequences being equal to number of winning configurations (and you're also right about wanting to wring some more information out of OP). – Gerry Myerson Nov 21 '10 at 11:34

If I am not mistaken, it is easy to see that the number is even, at least in the case $n$ even (for n odd, if the strategy matter, it could make a difference).

If $n$ is even than the winning possitions are symmetric with respect to reflection in the centre of the table, and we can use this symmetry to split them in pairwise disjoint pairs; thus it is even.

If $n$ is odd and $"n/2"$ is even, the winning possitions are still symmetric in reflection in the centre of the table, and no winning possition is invariant under this reflection, so again one can split them in pairs.

If $n$ is odd and $"n/2"$ is odd, the winning possitions are still symmetric in reflection in the centre of the table, but we get $4$ winning strings (horisontal, vertical, and two diagonal ones, with the middle exactly in the centre of the table) which are invariant under reflection. Excepting these winning possitions containing one of the $4$ winning strings, everything else can be paired.

For the symmetric posstions containing one of the $4$ winning strings, rotation by $\pi/2$ pairs the ones with horisontal winning string with the ones with vertical winning string, and those with the winning string on one diagonal with the winning string on the other diagonal.

EDIT: Fixed the last case. I wonder if a direct rotation by $\pi_2$ doesn't do directly the trick in all three casess. Rotation by $\pi$ leads to a nicer argument in the first two cases.

-