juego de mesa: Bombillas de 10 en 10, ¿interruptores mínimos para apagarlas todas?

Question

¡Hola a todos! Mi problema es el siguiente: Hay un tablero de 10 por 10 bombillas. (Así que es un cuadrado con 10 columnas y 10 filas). Cada bombilla tiene su propio interruptor. Sin embargo, algo ha fallado y cuando se utiliza un interruptor no sólo cambia el estado de la bombilla propia sino los estados de todas las otras 18 bombillas en su columna (9) y fila (9). (un cambio de estado significa obviamente: las luces apagadas se encienden, las encendidas se apagan) Así que un clic cambia el estado de la bombilla requerida Y todas las bombillas en su fila y columna. ¿Cuántos clics (interruptores utilizados) serán necesarios como mínimo para apagar todas las bombillas si están todas encendidas?

Me he pasado literalmente horas pensándolo una y otra vez. Es bastante sencillo que el orden de los clics es irrelevante y usar el mismo interruptor más de una vez no tiene sentido. (Quiero decir que usar el mismo interruptor dos veces es como no usarlo, y usarlo tres veces es como una sola vez {sólo importa la paridad (par/impar)}. En consecuencia, hay 2^100 posibilidades, así que lamentablemente más de lo que un ordenador podría comprobar en un tiempo razonable. De todos modos, me gustaría tener un número con algún tipo de prueba matemática.

Mi "conjetura" es 100. Creo que hay que usar todos los interruptores para cambiar el estado de toda la mesa. (lo que funciona porque todas las bombillas cambiarían 19 veces) Aunque puede haber una forma mejor (con un número menor de interruptores)... ¿Alguna idea? :D

Answer 1

El número mínimo de interruptores necesarios es $100$ .

Este rompecabezas puede convertirse en un problema de álgebra lineal sobre ${\Bbb Z}/2{\Bbb Z}$ dejando que el vector $v\in({\Bbb Z}/2{\Bbb Z})^{100}$ registrar qué interruptores se pulsan ( $1$ si se pulsa, $0$ si no), el vector $w\in({\Bbb Z}/2{\Bbb Z})^{100}$ registrar qué luces están inicialmente encendidas ( $1$ si en, $0$ si está apagado), y el $100$ -por- $100$ matriz $M$ en ${\Bbb Z}/2{\Bbb Z}$ Registrar qué interruptores afectan a qué luces. Un determinado $v$ resolverá el rompecabezas si $Mv=w$ .

Como señala el autor de la pregunta, $v=(1,\dots,1)^T$ es una solución. Para demostrar que esta es la única solución, basta con mostrar que $M$ es invertible.

Supongamos que pulsamos todos los interruptores que están en la fila $r$ o en la columna $c$ . Si una luz no está en fila $r$ y no en la columna $c$ su estado cambiará dos veces. Si una luz está en la fila $r$ pero no en la columna $c$ su estado cambiará $10$ veces, y de forma similar para una luz en la columna $c$ pero no en fila $r$ . La luz en $(r,c)$ tendrá su estado cambiado $19$ veces. Por lo tanto, la única luz cuyo estado acaba cambiando es la de $(r,c)$ . Dado que se puede alternar cualquier luz deseada, esto demuestra que se puede apagar cualquier configuración de luces, por lo que $M$ tiene rango completo y por lo tanto debe ser invertible.

Este rompecabezas es similar al juego electrónico Luces apagadas.

Answer 2

La única manera de iluminar todas las casillas es accionando todos los interruptores.

La única forma sencilla de demostrarlo es mostrar que el mapa lineal $f : \Bbb F_2^{100} \to \Bbb F_2^{100}$ que toma el conjunto de interruptores que accionamos y da el conjunto de luces encendidas, es inyectiva. Como $f$ es un endomorfismo de un espacio vectorial de dimensión finita, basta con mostrar que es suryente, y por razones de simetría y linealidad, mostrar que hay una forma de iluminar cualquier luz individual, por ejemplo la de la esquina inferior izquierda (porque las luces individuales generan $\Bbb F_2^{100}$ )

De hecho, prefiero ver $\Bbb F_2^{100}$ como $\Bbb F_2[X,Y]/(X^{10}+1, Y^{10}+1)$ para que el mapa $f$ es ahora la multiplicación por $P = 1+X+X^2+...+X^9+Y+Y^2+...+Y^9$ .

Intentemos invertir $P$ ya que en la característica $2$ , $(1+u)^{-1} = 1+u+u^2+u^3+\ldots$ si $u$ es nilpotente, comprobemos que $(X+...+X^9+Y+...+Y^9)^2 = X^2+\ldots+X^{18}+Y^2+\ldots+Y^{18} = 1+X^2+X^2+\ldots X^8+X^8+1+Y^2+Y^2+\ldots+Y^8+Y^8 = 0$ . (aquí el hecho de que el cuadrado tenga un tamaño uniforme es crucial)

Así, $P$ tiene una inversa, que de hecho es $P$ mismo : $P^2 = 1$ .

Y así el mapa $f$ es una involución, y esto te dice que para obtener una determinada imagen con las luces, la única manera de conseguirla es conmutar los interruptores correspondientes a las luces que se encenderían si conmutas las luces que quieres que se enciendan en tu imagen (¿hay una manera menos confusa de decir esto?).

Por ejemplo, si quieres iluminar el cuadrado inferior izquierdo, tienes que cambiar la fila inferior y la columna izquierda; y si quieres iluminar todo, tienes que cambiar todo.