Encuentra el número de cuadrículas mágicas.

Question

Pregunta-

Considere una cuadrícula N ×N en la que cada celda tiene +1 o 1. Llamamos a esta cuadrícula una cuadrícula binaria. El producto de una fila cualquiera se define como el producto de todos los elementos de esa fila. Del mismo modo, el producto de columna de una columna se define como el producto de todos los elementos de esa única columna. Una cuadrícula binaria N ×N se denomina cuadrícula mágica si exactamente uno de los N productos de fila es 1, y exactamente uno de los N productos de columna es 1. Es decir, los otros N1 productos de fila deben ser todos +1, y los otros productos de columna N1 deben ser todos ser +1. Encuentre el número de cuadrículas mágicas de tamaño N × N. (Sólo me interesa el caso N=3,4,5).

Mi intento- Realmente no he encontrado una manera de atacar el problema pero aquí hay algunas deducciones que he hecho:

1. El número de $-1$ s en una sola fila será impar. Lo mismo ocurre con las columnas.

2. Podría dividir el problema en subcasos, encontrando el número de cuadrículas mágicas para una sola $-1$ , entonces dos $-1$ s pero eso llevará mucho tiempo, y muy poco elegante.

¿Alguien podría dar alguna pista?

Answer 1

Esta es otra forma de ver el problema

Paso 1

Decida la fila y la columna cuyo producto fila/columna desea realizar $-1$ Las filas se pueden seleccionar en $n$ y para cada fila seleccionada, la columna puede ser seleccionada en $n$ formas: $n^2$ formas en total.

Paso 2

Ahora llene el resto de $(n-1)^2$ celdas (ninguna de las cuales pertenece a su fila o columna previamente seleccionada) al azar. Esto puede hacerse en $2^{(n-1)^2}$ formas.

Paso 3

Ahora rellenamos las celdas de nuestra fila y columna seleccionadas. Tenga en cuenta que después del paso 2, terminamos con un $N \times N$ cuadrícula en la que se conocen todos los productos de las filas y las columnas. Empiece a rellenar las filas de la rejilla a las que sólo les falta una celda. Como se conocen todos los demás elementos de esa fila y el producto, podemos únicamente determinar el signo del número que se va a insertar. Proceda de la misma manera con las columnas y habrá terminado su celda. En el paso 3, no tenemos ninguna opción y al final del paso 2, para tener una cuadrícula mágica válida, simplemente rellenamos la cuadrícula según los requisitos. En otras palabras, sólo hay una manera de completar el paso 3.

Por el Principio Fundamental de Contabilidad-

Número total de rejillas mágicas- $n^2\times 2^{(n-1)^2}$

Answer 2

PISTA por ahora... si necesitas más, puedo dar la solución completa siempre y cuando esto no sea una tarea, concurso, etc.

• Dada una cuadrícula cualquiera, si se cambia una celda (de $+1$ a $-1$ o viceversa) cambiará el producto-fila de su fila y el producto-columna de su columna, y ningún otro producto.

• Dada una cuadrícula mágica, en la que el $i$ y el producto de la fila $j$ La columna-producto es $-1$ y, a continuación, cambiar la celda $(i,j)$ dará lugar a una cuadrícula con todos los productos de las filas y las columnas $+1$ . A esto lo llamaremos una Rejilla de Aburrimiento. Esta operación define un mapeo de muchos a uno de las Rejillas Mágicas a las Rejillas Aburridas.

• ¿Puede contar el número de rejillas de perforación?

• ¿Puedes entonces contar el número de cuadrículas mágicas? Asegúrate de que manejas cualquier recuento doble (o múltiple) (si lo hay) cuando "inviertes" el mapeo.

Avísame si necesitas más ayuda.

Answer 3

Empecemos por todas las cuadrículas positivas, es decir, las que tienen todos los productos fila y columna positivos, y determinemos su número. Lo más sencillo que se nos ocurre es rellenar $(N-1)\times(N-1)$ subgrid arbitrario y usar la última fila y columna para arreglar cualquier problema de signos que encontremos $$ \begin{matrix} 1 & 1 & -1 & ?\\ -1 & 1 & -1 & ?\\ 1 & -1 & 1 & ?\\ ? & ? & ? & ?\\ \end{matrix} $$ Exigiendo cada uno de los escritos $N-1$ filas y $N-1$ columnas para tener un producto positivo podemos encontrar $$ \begin{matrix} 1 & 1 & -1 & -1\\ -1 & 1 & -1 & 1\\ 1 & -1 & 1 & -1\\ -1 & -1 & 1 & ?\\ \end{matrix} $$ Ahora la única preocupación es la última celda diagonal. El problema es que no conocemos los signos de los productos de la última fila y la última columna, que están controlados por la matriz $(N-1)\times(N-1)$ . Si sus productos tienen ambos $+$ o $-$ señal de que estamos bien -- la última celda vacía está bien definida, de lo contrario estamos en problemas.

Aquí viene el truco vamos a probar lema El producto en la última fila y la última columna, que se forman como se ha descrito anteriormente, tienen siempre el mismo signo. Prueba: en lugar del signo de interrogación pongamos $x$ para terminar la matriz. $$ \begin{matrix} 1 & 1 & -1 & -1\\ -1 & 1 & -1 & 1\\ 1 & -1 & 1 & -1\\ -1 & -1 & 1 & x\\ \end{matrix} $$ Sin pérdida de generalidad supongamos que el último producto de columna es $-x$ mientras que el producto de la última fila es $+x$ . Consideremos ahora el producto de todos los números de la cuadrícula. Por un lado es igual al producto de todas las columnas-producto (excepto la última, todas son $+1$ por construcción) así $-x$ . Por otro lado es igual al producto de todos los productos-fila (excepto el último todos son $+1$ por construcción) así $+x$ . Pero $x$ debe ser $+1$ o $-1$ por lo que no puede ser $x = -x$ , por lo tanto, una contradicción. Esto último significa que siempre podemos llenar definitivamente el último elemento para que la matriz de todas las filas-columnas sea positiva, QED.

Ahora volvamos al problema. Primero, formamos un $(N-1) \times (N-1)$ submatriz (totalmente $2^{(N-1)^2}$ posibilidades). Entonces calculamos la última fila y columna para que sea todo positivo, lo que siempre es posible por lema, así $2^{(N-1)^2}$ rejillas totalmente positivas posibles. Lo que hay que hacer a continuación está bien descrito en la otra respuesta, así que no lo duplicaré. Como resultado final deberías obtener $N^2\,2^{(N-1)^2}$ .