Un millón de interruptores, un millón de bombillas, un millón de pasadas. La pregunta parece monumental, pero se reduce a algo mucho más íntimo: la historia individual de cada bombilla.
Los interruptores y el millón de bombillas
Enunciado
En un pasillo hay un millón de bombillas, numeradas del 1 al 1.000.000. Al principio, todas están apagadas.
Una persona recorre el pasillo muchas veces. En la primera pasada cambia el estado de todas las bombillas. En la segunda, cambia el estado de las bombillas pares. En la tercera, cambia el estado de las bombillas numeradas con múltiplos de 3. Y así sucesivamente: en la pasada número k, cambia el estado de todas las bombillas cuyo número es múltiplo de k.
Después de completar la pasada número 1.000.000, ¿cuántas bombillas quedan encendidas?
Ver solución
Solución
Respuesta: Quedan encendidas exactamente 1000 bombillas: las que ocupan posiciones cuadradas perfectas.
Explicación:
La bombilla $n$ cambia de estado en la pasada $k$ si y solo si $k$ divide a $n$. Por tanto, cambia tantas veces como divisores positivos tenga $n$.
Cuando el número de cambios es par, la bombilla termina apagada (vuelve a su estado inicial). Cuando es impar, termina encendida.
Normalmente los divisores vienen en parejas: si $d$ divide a $n$, también lo hace $n/d$, y ambos son distintos. Esto da siempre un número par de divisores.
La excepción son los cuadrados perfectos. En ellos existe un divisor $d$ tal que $d = n/d$, es decir, $d^2 = n$, que no forma pareja con ningún otro. Eso hace que el total de divisores sea impar, y la bombilla queda encendida.
Entre 1 y 1.000.000 hay exactamente 1000 cuadrados perfectos: