# 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 )

-
By configuration, do you mean a filled board with half the cells X and half the cells O? There are $\frac{n^2!}{(\frac{n^2}{2}!)^2}$ of those. So you want to know how many of those have a line of $\frac{n}{2}$ X's? – Ross Millikan Nov 20 '10 at 16:38
No. Consider a 10x10 board. In 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. – user3740 Nov 20 '10 at 19:10
@user3740: Doesn't matter: imagine that the players keep playing even after one of them wins so that they fill up the board regardless. The number of filled boards is a lower bound for the total possible number of games, because different sequences may lead to the saame end-filled board. Your count is still way off in that case, as Ross Millikan points out in his answer. – Arturo Magidin Nov 21 '10 at 3:10
This lower bound argument would work if each winning position completed uniquely. – Douglas S. Stones Nov 21 '10 at 3:57
A much easier argument (to show that 144 is far too small) is that there are 2*4*3*14=336 winning configurations with two player 1 moves and one player 2 move. [2*4*3 ways of placing two neighbouring 1's and 14 ways of placing a single 2] – Douglas S. Stones Nov 21 '10 at 5:09

I believe the answer is 643888. Here's how I arrived at this number:

• Let $C_k$ be the set of $4 \times 4$ $(0,1)$-matrices with $k$ 1's for which there do not exist two neighbouring 1's.
• Let $B_k$ be the set of $4 \times 4$ $(0,1)$-matrices with $k$ 1's for which there exists two neighbouring 1's, and for which deletion of some 1 implies membership in $C_{k-1}$.
• For any two (0,1)-matrices, $L$ and $M$, let $\chi(L,M)=1$ if $L$ and $M$ do not have a 1 in the same position and $0$ otherwise.

We need the sets $B_k$ and $C_k$ to avoid multiple win situations.

The number you seek is given by $\sum_{k=0}^{n^2/2} \Big(\sum_{L \in B_k} \sum_{M \in C_{k-1}} \chi(L,M) + \sum_{L \in C_k} \sum_{M \in B_k} \chi(L,M)\Big).$ The first term counts when player 1 wins, and the second term counts when player 2 wins. I implemented this formula in GAP with the code below.

This function determines if a (0,1)-matrix has n/2 lines in a horizontal or vertical line.

user3740Win:=function(L,n)
local m,i,j;
if(n mod 2=1) then return fail; fi;
m:=n/2;
for i in [1..n] do for j in [1..m+1] do
if(ForAll([0..m-1],k->L[i][j+k]=1)) then return true; fi;
if(ForAll([0..m-1],k->L[j+k][i]=1)) then return true; fi;
od; od;
return false;
end;;


This function determines if a (0,1)-matrix has n/2 lines in a horizontal or vertical line, and that deletion of one of the 1's results in falsifying user3740Win(L,n).

user3740StrongWin:=function(L,n)
local M,i,j;
if not(user3740Win(L,n)) then return false; fi;
M:=List([1..n],i->List([1..n],j->L[i][j]));
for i in [1..n] do for j in [1..n] do
M[i][j]:=0;
if(user3740Win(M,n)=false) then return true; fi;
M[i][j]:=L[i][j];
od; od;
return false;
end;;


This function generates the (0,1)-matrices with at most n^2/2 1's.

user3740MatricesStep1:=function(n)
local A,B,L,M,i,j;
A:=Filtered(Tuples([0,1],n^2),i->Sum(i)<=n^2/2);
B:=[];
for L in A do
M:=List([1..n],i->List([1..n],j->0));
for i in [1..n] do for j in [1..n] do
M[i][j]:=L[n*(i-1)+j];
od; od;
Append(B,[M]);
od;
return B;
end;;


Starting from A (the set of (0,1)-matrices with at most n^2/2 1's), I run through k=0..n^2/2. B is $B_k$ above. C1 is $C_{k-1}$ above. C2 is $C_k$ above.

user3740Count:=function(n)
local A,B,C1,C2,S,i,j,k,L,M;
A:=user3740MatricesStep1(n);
S:=[];
for k in [0..n^2/2] do
B:=Filtered(A,L->user3740StrongWin(L,n) and Sum(Sum(L))=k);
C1:=Filtered(A,L->(not user3740Win(L,n)) and Sum(Sum(L))=k-1);
C2:=Filtered(A,L->(not user3740Win(L,n)) and Sum(Sum(L))=k);
Print("k=",k," ",Size(B)," ",Size(C1)," ",Size(C2),"\n");
for L in B do for M in C1 do
if(not 2 in Union(L+M)) then Append(S,[L+2*M]); fi;
od; od;
for L in C2 do for M in B do
if(not 2 in Union(L+M)) then Append(S,[L+2*M]); fi;
od; od;
Print("count=",Size(S),"\n");
od;
return S;
end;;


Just so the reader can independently confirm these calculations, here is the output:

gap> S:=user3740Count(2);;
k=0 0 0 1
count=0
k=1 4 1 0
count=4
k=2 0 0 0
count=4
gap> S:=user3740Count(4);;
k=0 0 0 1
count=0
k=1 0 1 16
count=0
k=2 24 16 96
count=2072
k=3 284 96 276
count=58808
k=4 1200 276 405
count=315836
k=5 2276 405 304
count=571892
k=6 2032 304 114
count=638352
k=7 848 114 20
count=643752
k=8 156 20 2
count=643888
gap> Random(S);
[ [ 0, 0, 0, 0 ], [ 2, 0, 1, 2 ], [ 0, 1, 1, 0 ], [ 1, 2, 0, 0 ] ]
gap> Random(S);
[ [ 2, 0, 2, 1 ], [ 1, 1, 0, 2 ], [ 0, 0, 1, 0 ], [ 1, 2, 0, 0 ] ]
gap> Random(S);
[ [ 0, 1, 1, 0 ], [ 1, 2, 0, 2 ], [ 0, 0, 0, 1 ], [ 2, 1, 0, 2 ] ]
gap> Random(S);
[ [ 0, 2, 1, 0 ], [ 0, 0, 0, 0 ], [ 1, 1, 1, 2 ], [ 2, 0, 0, 0 ] ]
gap> Random(S);
[ [ 0, 2, 0, 2 ], [ 1, 1, 2, 0 ], [ 1, 0, 0, 1 ], [ 0, 1, 2, 0 ] ]
gap> Size(Filtered(S,L->Sum(Sum(L))=4));
336
gap>


The numbers are k (as in the above formula), |B|, |C1|, |C2|, then "count" is the running sum.

-
Thank you Douglas. I will try and understand this. – user3740 Nov 21 '10 at 6:02

For the 4x4 case there are only two drawn configurations-a checkerboard. As there are 12870 evenly filled boards, there are 12868 winning ones. This is not the 144 you calculated.

-