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
    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?2010-11-20
  • 0
    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.2010-11-20
  • 0
    @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.2010-11-21
  • 0
    This lower bound argument would work if each winning position completed uniquely.2010-11-21
  • 0
    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]2010-11-21
  • 0
    @Douglas S. Stones: Fair enough.2010-11-21
  • 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
    Thank 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.