Contar el número de maneras de romper la simetría de un N x N de la cuadrícula mediante la colocación de uno X y uno O en un momento

Question

Recientemente he estado trabajando fuera el juego completo árbol de tic-tac-dedo del pie, sólo por diversión. Estoy usando el bien conocido de equivalencia de la relación de las rotaciones/reflexiones para simplificar este árbol en la forma estándar (que comienza por señalar que sólo hay 3 movimientos de apertura: borde, en la esquina, y en el centro). Yo realmente no pude encontrar una imagen de la versión completa del juego árbol de tic-tac-dedo del pie, así que si alguien puede proporcionar un enlace te lo agradecería.

Este trabajo motiva la siguiente;

Vamos haber dado un N x N de la cuadrícula; y deje $m$ ser un número natural.

Deje $I$ ser el conjunto de todas las formas posibles para colocar $m$ copias de la carta $X$ en la red, y $m$ copias de la carta $O$ en la red (con la restricción de que sólo podemos colocar una letra por el espacio de la cuadrícula; en otras palabras, imagínate jugando a un juego de tic-tac-dedo del pie en un N x N de la junta para un número par de movimientos).

Problema:

De cuántas maneras existen para romper por completo la rotación/reflexión de simetría de un N x N de la cuadrícula mediante la colocación de $m$ copias de $X$ $m$ copias de $O$?

Answer 1

Creo que estás tratando de preguntar: ¿cuántos de esos rejillas de admitir que no trivial de la simetría (en el diedro grupo)?

Fijo m≥1, asintóticamente casi todos (0,1,-1)-matrices con exactamente m 1 y m -1 s no admite un no-trivial de simetría (rotación/reflexión). Para estas matrices, se puede considerar que la X como la 1 y la (carta) O como el -1. El (número) 0 representan las celdas vacías.

Puesto que m es fijo, hay ${{N^2} \choose {m,m,N^2-2m}}=N^{4m}/m!^2+o(N^{4m})$ (0,1,-1)-matrices en total con exactamente m 1 y m -1.

El número de matrices que se conservan bajo la transposición es \[\sum_{i,j} {N \elegir {i,j,n-i-j}} {{N \elegir 2} \elegir (m-i)/2} {{{N \elegir 2}-(m-i)/2} \elegir (m-j)/2}\] donde i es el número de 1's en la diagonal principal, j es el número de -1 en la diagonal principal. Por tanto, necesitamos 0≤i+j≤m y m-i y m-j incluso. Un crudo límite superior a la anterior sumando es $\mathrm{const} \cdot N^{i+j+2(m-i)/2+2(m-j)/2} \leq N^{3m}=o(N^{4m})$. Puesto que m es fijo, sólo hay un número finito de pares i,j, que se suman a lo largo, por lo que el resultado global es $o(N^{4m})$.

El número de matrices que admitir que cualquiera de los otros no-trivial simetrías está acotada arriba por la fórmula de arriba también. Así asintóticamente casi todos (0,1,-1)-matrices con exactamente m 1 y m -1 s no admite un no-trivial de simetría.

En realidad, sospecho que este resultado sería verdadero sin el fijo m condición, pero no puedo pensar de cómo demostrarlo con la mano.

Así que en respuesta a la pregunta, a menos que usted está tratando con un muy pequeño de casos, y a menos que usted está tratando de crear una simetría, no es probable que para crear una matriz que tiene un no-trivial de simetría. Para el árbol de búsqueda, la mayoría del tiempo usted será capaz de identificar 8 nodos correspondientes a los equivalentes de los juegos de naughts y cruces.

[PS: sería complicado (aunque es posible) para encontrar una fórmula exacta a lo largo de estas líneas para que el número de matrices que admitir que no trivial de la simetría.]

Answer 2

Este no es el juego completo árbol, pero el total de óptima árbol de tic-tac-toe.