2
$\begingroup$

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 )

  • 0
    user3740 confirmed my description of configuration, but then deleted it. Maybe my count of configs was too high for his/her taste. But Douglas S. Stones' is higher yet.2010-11-21

2 Answers 2

8

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.

  • 0
    Tha$n$k you Douglas. I will try and understand this.2010-11-21
2

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.