Let there be given an N × 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 × N board for an even number of moves).Problem:How many ways are there to completely break the rotational/reflection symmetry of an N × N grid by placing m copies of X and m copies of O?

Question

Let there be given an   N  ×  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  ×  N board for an even number of moves).Problem:How many ways are there to completely break the rotational/reflection symmetry of an   N  ×  N grid by placing   m copies of   X and   m copies of   O?

lilao8x · Accepted Answer

For fixed m≥1, asymptotically almost all (0,1,-1)-matrices with exactly m 1&#039;s and m -1&#039;s do not admit a non-trivial symmetry (rotation/reflection). For these matrices, we can consider the X&#039;s as the 1&#039;s and the (letter) O&#039;s as the -1&#039;s. The (number) 0&#039;s represent the empty cells.Since m is fixed, there are                 (                          N        2                    m        ,        m        ,                  N          2                −        2        m                        )        =      N          4      m        /  m      !    2    +  o  (      N          4      m        ) (0,1,-1)-matrices in total with exactly m 1&#039;s and m -1&#039;s.The number of such matrices that are preserved under transposition is      ∑          i      ,      j                      (              N              i        ,        j        ,        n        −        i        −        j                        )                      (                                            (                          N          2                                  )                            (        m        −        i        )              /        2                        )                      (                                                            (                                N            2                                          )                          −        (        m        −        i        )              /        2                    (        m        −        j        )              /        2                        )      where i is the number of 1&#039;s on the main diagonal, j is the number of -1&#039;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       c    o    n    s    t    ⋅      N          i      +      j      +      2      (      m      −      i      )          /      2      +      2      (      m      −      j      )          /      2        ≤      N          3      m        =  o  (      N          4      m        ). 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          4      m        ).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&#039;s and m -1&#039;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&#039;t think of how to prove it off-hand.So in answer to the question, unless you&#039;re dealing with a very small case, and unless you&#039;re deliberately trying to create a symmetry, you&#039;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.

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

Answered question

Answer & Explanation

New Questions in Precalculus