Número de configuraciones de monedas en un tablero de ajedrez

Question

Para cada casilla de un tablero de ajedrez estándar de 8 × 8, hay que poner una moneda en ella o dejarla vacía. También hay que garantizar que cada fila y columna contenga un número impar de monedas. ¿Cuántas configuraciones de monedas de este tipo hay?

Nota: el tablero de ajedrez no está etiquetado, pero la esquina inferior izquierda es negra.

Answer 1

Podemos pensar en el tablero de ajedrez como un $8\times 8$ matriz en $F_2$ . El número de configuraciones con un número impar de monedas en cada fila/columna es el mismo que el número de configuraciones con un número par de monedas en cada una (la biyección viene dada por la suma de la matriz identidad), y será más fácil trabajar con esta última.

Queremos contar el número de matrices que obedecen la condición de paridad fila/columna, hasta rotaciones de 180 grados. El número viene dado, por tanto, por $$(T-S)/2 + S,$$ donde $T$ es el número total de matrices que satisfacen la condición de paridad, y $S$ es el número de tales matrices con simetría de 180 grados.

Afirmación: Cada matriz $M$ con sumas pares de fila/columna se especifica de forma única por $49$ dígitos binarios $\alpha_{i,j}$ con $$M = \sum_{i=1}^7 \sum_{j=1}^7 \alpha_{i,j} A_{i,j},$$ donde $A_{i,j}$ es la matriz que es cero excepto a $2\times 2$ bloque de unos cuya esquina superior izquierda está en $(i,j)$ (y la esquina inferior derecha en $(i+1,j+1)$ ), y la suma se toma en el espacio de las matrices con coeficientes en $F_2$ es decir, los coeficientes se toman mod 2. La prueba: Empezamos por la esquina superior derecha de $M$ y trabaja de izquierda a derecha, de arriba a abajo.

Lo anterior nos da $T = 2^{49}$ . También podemos calcular el número de matrices simétricas con suma par de filas y columnas: podemos emparejar cada $A_{i,j}$ con la correspondiente matriz base $A_{8-i,8-j}$ que se obtiene al girar $A_{i,j}$ en 180 grados. Sólo una matriz base se mapea a sí misma: $A_{4,4}$ . Por lo tanto, tiene dos opciones para $\alpha_{4,4}$ y dos opciones para cada par de coeficientes restantes, para un total de $S=2^{25}$ opciones.

Por lo tanto, la respuesta es $2^{48} + 2^{25} - 2^{24} = 2^{48} + 2^{24}.$