Olimpiadas de Matemáticas
Página de preparación y problemas

Por otro lado, si $n$ es par y tocamos las $n^2$ lámparas, también quedarán todas encendidas ya que a cada lámpara le afectan $2n-1$ cambios de estado (en realidad, esto también funciona para $n$ impar pero no es óptimo, como acabamos de ver). Vamos a demostrar que, si no tocamos todas las lámparas, entonces habrá alguna que quede apagada, lo que probará que $n^2$ es óptimo en el caso $n$ par y habremos terminado.

Llamaremos $c_{ij}$ a la casilla de la fila $i$ y la columna $j$ y le asignaremos un valor $0$ o $1$ dependiendo de si se ha tocado o no (no tiene sentido tocarla más de una vez). Comenzaremos probando que en cualesquiera cuatro casillas $c_{ij},c_{ik},c_{hj},c_{hk}$ que forman los vértices de un cuadrado (como las indicadas en naranja en la imagen) hay un número par de toques. Observamos en primer lugar que cada toque en casillas las filas $i$ y $h$ o de las columnas $j$ y $k$ distintas de los vértices del cuadrado (pintadas de morado) cambia exactamente a dos de los vértices naranjas. Como tocar uno de los vértices cambia el estado de tres de ellos, es inmediato que hay que pulsar un número par de vértices para que los cuatro queden encendidos.

Consideremos ahora dos columnas cualesquiera del tablero. El razonamiento anterior (aplicado a todas las casillas que sean vértices un cuadrado contenido en esas dos columnas) nos dice que o bien las dos columnas son iguales (tienen los mismos ceros y unos en la misma posición) o bien son opuestas (una tiene ceros donde la otra tiene unos y viceversa). Esta última situación no es posible si $n$ es par ya que, si nos fijamos en las dos casillas de la primera fila, tendrán paridades distintas de toques provenientes de su columna, pero el mismo número de toques provenientes de su fila, lo que nos lleva a que ambas no pueden estar encendidas. Hemos probado así que todas las columnas son iguales y el mismo razonamiento puede aplicarse a las filas, luego necesariamente hemos tenido que tocar todas las lámparas.