Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 )

share|improve this question
    
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

2 Answers 2

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.

share|improve this answer
    
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.

share|improve this answer

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.