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