Inicio > Acertijos > Los interruptores y el millón de bombillas
Este acertijo de combinatoria y estrategia, conocido como Los interruptores y el millón de bombillas, combina intuición y método en una proporción muy difícil de equilibrar. A primera vista parece directo, pero suele exigir más estructura de la que parece para no perderse por el camino.
Por eso se usa tanto para entrenar razonamiento formal en nivel experto. Tómate unos minutos y prueba primero una solución propia.
Hay un millón de bombillas en fila, todas apagadas inicialmente. Hay un millón de personas.
La persona 1 acciona todos los interruptores (1, 2, 3, ...). La persona 2 acciona cada segundo interruptor (2, 4, 6, ...).
La persona 3 cada tercer interruptor (3, 6, 9, ...). Así sucesivamente.
¿Cuántas bombillas quedan encendidas al final y por qué?
Respuesta: Quedan encendidas exactamente
$$ 1000 $$
bombillas: las de índice cuadrado perfecto.
1) Modelo matemático
La bombilla $n$ es accionada por las personas cuyos números dividen a $n$.
Número de accionamientos de la bombilla $n$:
$$ \tau(n)\quad (\text{número de divisores positivos de }n). $$
Como empieza apagada y cada accionamiento invierte el estado, queda encendida si y solo si $\tau(n)$ es impar.
2) ¿Cuándo $\tau(n)$ es impar?
Los divisores suelen venir en pares:
$$ (d,\,n/d). $$
Hay divisor "sin pareja" únicamente cuando:
$$ d=n/d\iff d^2=n, $$
es decir, cuando $n$ es cuadrado perfecto.
Por tanto:
3) Conteo final en $1,\dots,10^6$
Los cuadrados perfectos en ese rango son:
$$ 1^2,2^2,\dots,1000^2, $$
porque
$$ 1000^2=1\,000\,000. $$
Hay exactamente 1000 de ellos.
Conclusión: quedan encendidas las bombillas
$$ 1,4,9,16,\dots,1\,000\,000, $$
en total
$$ \boxed{1000}. $$
Si te gustó este reto, prueba más acertijos de lógica pura, explora esta temática, revisa el archivo completo o mira la guía para resolver acertijos.