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.

I have recently been working out the full game tree for tic-tac-toe, just for fun. I am using the well known equivalence relation of rotations/reflections to simplify this tree in the standard way (which begins by noting that there are only 3 opening moves: edge, corner, and center). I actually could not find an image of the full game tree for tic-tac-toe, so if anyone can provide a link I'd appreciate that.

This work motivates the following;

Let there be given an N x N grid; and let $m$ be a natural number.

Let $I$ be the set of all possible ways to place $m$ copies of the letter $X$ in the grid, and $m$ copies of the letter $O$ in the grid (with the restriction that we can only place one letter per space of the grid; in other words, just imagine playing a game of tic-tac-toe on an N x N board for an even number of moves).

Problem:

How many ways are there to completely break the rotational/reflection symmetry of an N x N grid by placing $m$ copies of $X$ and $m$ copies of $O$?

share|improve this question
    
I am having a bit of difficulty understanding your question, could you clarify a little what you mean by breaking the symmetry? As it stands, my current interpretation, is how many configurations of m X's and m O's are in their own equivalence class with respect to rotation and reflection. –  BBischof Oct 1 '10 at 4:32
    
I'm still trying to work this out, I should have thought it through more carefully before posting. –  Matt Calhoun Oct 2 '10 at 23:50

2 Answers 2

up vote 2 down vote accepted

I think you're trying to ask: how many such grids admit a non-trivial symmetry (in the dihedral group)?

For fixed m≥1, asymptotically almost all (0,1,-1)-matrices with exactly m 1's and m -1's do not admit a non-trivial symmetry (rotation/reflection). For these matrices, we can consider the X's as the 1's and the (letter) O's as the -1's. The (number) 0's represent the empty cells.

Since m is fixed, there are ${{N^2} \choose {m,m,N^2-2m}}=N^{4m}/m!^2+o(N^{4m})$ (0,1,-1)-matrices in total with exactly m 1's and m -1's.

The number of such matrices that are preserved under transposition is \[\sum_{i,j} {N \choose {i,j,n-i-j}} {{N \choose 2} \choose (m-i)/2} {{{N \choose 2}-(m-i)/2} \choose (m-j)/2}\] where i is the number of 1's on the main diagonal, j is the number of -1's on the main diagonal. Therefore we require 0≤i+j≤m and m-i and m-j even. A crude upper bound to the above summand is $\mathrm{const} \cdot N^{i+j+2(m-i)/2+2(m-j)/2} \leq N^{3m}=o(N^{4m})$. Since m is fixed, there is only a finite number of pairs i,j which is summed over, so the overall result is $o(N^{4m})$.

The number of such matrices that admit any of the other non-trivial symmetries is bounded above by the above formula also. So asymptotically almost all (0,1,-1)-matrices with exactly m 1's and m -1's do not admit a non-trivial symmetry.

Actually, I suspect that this result would be true without the fixed m condition, but I can't think of how to prove it off-hand.

So in answer to the question, unless you're dealing with a very small case, and unless you're deliberately trying to create a symmetry, you're unlikely to create a matrix that has a non-trivial symmetry. For the search tree, most of the time you will be able to identify 8 nodes corresponding to equivalent games of naughts and crosses.

[PS: it would be messy (although possible) to find an exact formula along these lines for the number of such matrices that admit a non-trivial symmetry.]

share|improve this answer
    
I really like this answer! This is what I was trying to ask, and I should have thought about the matrix representation, it seems so obvious in hindsight. –  Matt Calhoun Oct 17 '10 at 18:51

This is not the full game tree, but the complete optimal tree for tic-tac-toe.

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.