Variante de Lights Out: Cambiando la toda la fila y la columna.

Question

Así que me encontré con este puzzle similar a las Luces, si alguno de ustedes ha jugado alguna vez. Básicamente el rompecabezas trabaja en una cuadrícula de luces así:

1 0 0 0
0 0 0 0
0 1 0 0
0 0 1 0

Cuando usted selecciona una luz (X), se desplazará a sí mismo y todas las luces de su fila y columna:

1 0 1 0
1 1 X 1
0 1 1 0
0 0 0 0

Este me pregunto cómo se puede saber si hay una solución para un determinado programa de instalación y el tamaño de la cuadrícula, y si es así, ¿cuál fue? Me parece que no puede conseguir en cualquier lugar. Alguien podría empujarme en la dirección correcta?

Answer 1

En primer lugar, considerar el $n\times n$ de los casos.

Yo reclamo las siguientes:

Reclamo:

Si $n$ es igual, siempre hay una solución dada en cualquier partida de configuración.

Si $n$ es impar, hay una solución si el 'en' luces de paridades para cada fila y columna son los mismos.

es decir, si las luces se $1$ a y $0$ off, luego modulo $2$, la suma de cada fila individual, y la suma de cada columna debe ser el mismo.

Prueba:

Caso I: $n$ es incluso. Puede cambiar sólo una luz particular por la alternancia todos las luces en su fila y columna. Así que usted puede apagar todas las luces por ir tras de luces individuales.

Caso II: $n$ es impar.

Observe que si $n$ es impar, en una sola operación, todos los de la fila y la columna de las paridades de cambio de forma simultánea.

Por lo tanto, si ellos no son los mismos, nunca podremos cumplir con todas las luces apagadas. Esto muestra la necesidad de las paridades de ser el mismo.

Para demostrar la suficiencia, considere la posibilidad de un arreglo de $(2k+1)\times(2k+1)$ a que todos los de la fila y columna de las paridades de las mismas.

Considere la posibilidad de la $2k\times 2k$ subgrid que no se incluye el fondo de la fila y la columna de la derecha. El uso de la por encima de la $n$ caso algoritmo de apagar todas las luces en ese $2k\times 2k$ cuadrícula. Desde la fila y la columna de paridades de todos los flip juntos y fueron inicialmente todos el mismo, debemos tener que el resto de las luces, en la parte inferior de la fila y columna de la derecha, son todos de la misma (incluyendo la esquina inferior derecha). Ahora podemos alternar la esquina inferior derecha, si es necesario.

$\circ$

Ahora, lo anterior puede ser generalizado a la $m \times n$ de los casos, cuando se $m$ $n$ tienen la misma paridad.

Si $m$ $n$ tienen diferentes partidos, hay más trabajo por hacer.

Answer 2

De pensar en la luz como una variable que toma valores en $0, 1$. Accionando un interruptor tiene el efecto de la adición de $1$ a cada uno de luz correspondiente, modulo $2$. Con el interruptor en la posición $i, j$ hacer corresponder una variable $s_{i,j}$que representa el número de veces que usted mueve de un tirón el interruptor que. Ahora el valor final de cada luz es igual a su valor inicial, además de cada uno $s_{i,j}$ que comparte una columna o fila con ella - esta es una ecuación lineal en las variables $s_{i,j}$. Para un $m\times n$ cuadrícula, de este modo, obtener $mn$ ecuaciones lineales (uno para cada luz) en $mn$ variables (uno para cada interruptor).

Los enteros modulo $2$ son un campo, por lo que todos los habituales de los resultados de álgebra lineal debe aplicar.

Ejemplo. Vamos a la $2\times2$ de los casos. Que las rejillas se pueden resolver?

Si nos representan "en la medida de lo $1$ y "off" ( $0$ , a continuación, tenga en cuenta que necesitamos para agregar cada una luz para sí mismo. Es decir, si una luz se inicia en el valor de $0$, tenemos que voltear los interruptores de modo de agregar $0$ a que la luz (porque no lo queremos cambiar), pero si se empieza en el valor de $1$, tenemos que voltear los interruptores de modo de agregar $1$ a que la luz. De manera que la ecuación para cada luz se va a parecer a la suma de los interruptores relacionados = estado inicial.

Escrito el estado inicial de la $i,j$ luz $l_{i,j}$, por lo tanto, necesitan resolver:

$$l_{1,1}=s_{1,1}+s_{1,2}+s_{2,1}$$ $$l_{1,2}=s_{1,2}+s_{1,1}+s_{2,2}$$ $$l_{2,1}=s_{2,1}+s_{1,1}+s_{2,2}$$ $$l_{2,2}=s_{2,2}+s_{1,2}+s_{2,1}$$

La matriz de este sistema se parece a esto (la omisión de ceros para mejorar la legibilidad):

\begin{array}{cccc} 1 & 1 & 1 & \\ 1 & 1 & & 1 \\ 1 & & 1 & 1 \\ & 1 & 1 & 1 \end{array}

Eliminación gaussiana funciona fácilmente en esta matriz (sugerencia: recuerde que el mod $2$, $a + a = 0$ para cualquier $a$) y se obtiene una solución explícita para el general $2\times2$ grid:

$$s_{1,1}=l_{1,1}+l_{1,2}+l_{2,1}$$ $$s_{1,2}=l_{1,2}+l_{1,1}+l_{2,2}$$ $$s_{2,1}=l_{2,1}+l_{1,1}+l_{2,2}$$ $$s_{2,2}=l_{2,2}+l_{1,2}+l_{2,1}$$

Así que la respuesta es que todos los $2\times2$ rejillas tienen solución, y no es la solución (coincidiendo con Aryabhata de la proposición).

Como el número de ecuaciones es igual al número de celdas de la cuadrícula, este método rápidamente se vuelve muy tedioso y complicado de realizar con la mano. Me gustaría tratar de investigar el determinante de las matrices en el caso en abstracto y a ver si te salen con cualquier cosa. Que al menos decirte que el tamaño de las redes tienen una garantía de solución.