Se Puede!!!!!!!!!

Contrariamente a lo sospechado, Juansito Ramón Cortabitarte tenía razón. Se puede hacer el Alllights!!!

Como ya te conté, se puede pensar al tablero como {0,1}5x5 con la operación xor. Cada vez que se pulsa sobre un cuadro se hace el xor con la cruz centrada en el que se pulsó. Afortunadamente, xor le da a {0,1}5x5 una estructura de grupo conmutativo isomorfo a Z 25x5. Como es conmutativo, no importa el orden en que se aprieten los botones.

Entonces puedo poner en una tabla de 5x5 un uno en los que apreto y un cero en los que no. Un cuadro quedará encendido si su numero y los adyacentes suman 1 (en Z2 ). Así, si se sabe el valor de la primera columna, es fácil calcular el de las otras cuatro para que las luces de las primeras cuatro columnas queden encendidas.

De esa forma, si A, B, C, D y E son los valores de la primera columna:

A A+B+1 A+C+1 B+C+D+1 E
B A+B+C+1 D A+B+D+E+1 D+1
C B+C+D+1 A+E A+C+E C+1
D C+D+E+1 B A+B+D+E+1 B+1
E D+E+1 C+E+1 B+C+D+1 A

Siguiendo esta tabla, poniendo cualquier cosa en la primera columna, quedan encendidas las primeras cuatro columnas.

Para que quede encendida la última A, B, C, D y E deben cumplir:

(1) B+C+E = 1

(2) A+B+C=0

(3) A+B+D+E=0

(4) C+D+E=0

(5) A+C+D=1

Hay que resolver estas ecuaciones.

El det del sistema es cero. Las ecuaciones no son linealmente independientes, por lo que habrá mas de una solución. Simplificando se llega a:

C=A+B

E=A+1

D=B+1

Por lo tanto A y B definen unívocamente la solución. Hay cuatro soluciones:

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

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

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

En caso de que no hayas entendido nada, andá al cuadro de Alllights y vas a ver que si apretás exactamente donde están los 1en estos cuadros vas a obtener congratulations.

El lector observador habrá notado que los cuatro tableros de arriba son iguales salvo simetrías.

Cabe preguntarse a esta altura si hay alguna configuración del tablero a la que no se puede alcanzar con los movimientos a nuestro alcance. La respuesta es sí!!! Se puede definir un morfismo de grupos (más aún, un morfismo de Z2 espacios vectoriales) que aplique el elemento que tiene un uno en (i,j) en el que tiene unos en (i,j) más todos los adyacentes a él. La interpretación de esta función sería que le decís que botones apretás y te dice como va a quedar el tablero. Es obvio que las posiciones alcanzables son exactamente la imagen de este morfismo. La pregunta es si es un epimorfismo. Como Z25x5 es un conjunto finito, cualquier función sobre sí mismo, será sobreyectiva si y solo si es biyectiva. Pero el morfismo no es biyectivo porque los cuatro tableros de arriba van al que está todo lleno. Por lo tanto no es epimorfismo y hay posiciones que no se pueden alcanzar. Como es un morfismo de grupos, la preimagen de todos los elementos tiene el mismo cardinal (4). Por lo tanto hay exactamente 2^(5*5)/4 = 2^23 posiciones que se pueden alcanzar apretando botones.

¿Cuáles son las que no se pueden alcanzar? Todas las demás. ¿Un ejemplo? Quien sabe.

Luis Silvestre

Volver al Juego

Ver enunciados de la práctica