El problema de las 1.000 bombillas

Los problemas son el alma de las matem¨¢ticas. Todos los grandes avances en matem¨¢ticas han comenzado con alg¨²n problema, se han creado importantes ramas de las matem¨¢ticas a partir de la resoluci¨®n de alg¨²n problema (recordad, por ejemplo, la teor¨ªa de grafos y la probabilidad moderna) y, adem¨¢s, son fundamentales para aprender a aplicar convenientemente los conocimientos matem¨¢ticos a cuestiones m¨¢s concretas.

Dejando aparte la mayor o menor dificultad que puede tener, un problema puede ser feo, del mont¨®n, t¨ªpico, bonito, de gran belleza¡­ Seguro que muchos de vosotros os hab¨¦is encontrado con problemas de todos estos tipos, nos ha pasado a todos. Pues hoy os voy a hablar de un problema que me ha encantado desde la primera vez que lo vi y que, adem¨¢s, nos muestra que con conceptos muy b¨¢sicos podemos crear problemas interesantes a la par que bellos.

El problema en cuesti¨®n puede enunciarse de varias maneras. Yo os voy a dar la siguiente:

¡°Despu¨¦s de ser secuestrado, te despiertas en una gran sala donde vemos 1.000 bombillas apagadas, numeradas del 1 al 1.000. Notas que te est¨¢s quedando sin ox¨ªgeno, por lo que necesitas salir de esa habitaci¨®n. Al fondo ves una puerta. Intentas abrirla, pero no hay manera, es imposible, est¨¢ bloqueada¡­

En ese momento, una voz grave sale de alg¨²n lugar de la habitaci¨®n y dice lo siguiente:

¡®Imagine que pudiera encender y apagar cada una de las bombillas que hay en la habitaci¨®n. En esa hipot¨¦tica situaci¨®n, comenzando con la bombilla 1 y siguiendo un orden ascendente, col¨®quese mentalmente delante de cada bombilla y cambie de estado todas las que tengan un n¨²mero que sea m¨²ltiplo de la bombilla en la que est¨¢ situado en ese instante.

Tras llegar a la bombilla 1.000 y realizar dicha operaci¨®n con ella, ?qu¨¦ bombillas terminar¨¢n encendidas? Pi¨¦nselo bien, de su respuesta depende que salga de la habitaci¨®n o que permanezca ah¨ª para siempre. Si da con la respuesta correcta, recuperar¨¢ su libertad. Tiene un minuto para dar con ella.¡¯

?Conseguir¨ªais salir de la habitaci¨®n o, por el contrario, vuestra vida terminar¨ªa en aquel lugar? Analizad el problema y pensadlo durante un rato mientras aclaro algunos detalles:

- Cambiar de estado una bombilla es encenderla si estaba apagada o apagarla si estaba encendida.

- No puedes volver atr¨¢s, es decir, primero haces lo que te dicen en la bombilla 1, luego en la 2, despu¨¦s en la 3, y as¨ª sucesivamente en orden ascendente.

- Un n¨²mero es m¨²ltiplo de s¨ª mismo.

Sigue pensando, analiza la situaci¨®n, hazte un dibujito o un esquema, intenta ver qu¨¦ ocurre con casos particulares o caso m¨¢s simples¡­ En definitiva, utiliza t¨¢cticas de resoluci¨®n de problemas para intentar resolver este problema (parece una obviedad, pero en muchas ocasiones no lo es).

?Lo has conseguido? Espero que s¨ª, pero por si acaso vamos a mostrar la soluci¨®n y a dar una forma de resolverlo usando un concepto muy sencillo que se conoce desde la educaci¨®n primaria: el concepto de divisor de un n¨²mero.

Pero antes vamos a pensar el problema con menos bombillas, 10 por ejemplo. Vamos paso a paso haciendo lo que nos han ordenado (si segu¨ªs el proceso con papel y boli lo ver¨¦is m¨¢s claro):

- Bombilla 1: encendemos las bombillas 1, 2, 3, 4, 5, 6, 7, 8, 9 y 10.

- Bombilla 2: apagamos las bombillas, 2, 4, 6, 8, y 10.

- Bombilla 3: apagamos la 3, encendemos la 6 y apagamos la 9.

- Bombilla 4: encendemos la 4 y la 8.

- Bombilla 5: apagamos la 5 y encendemos la 10.

- Bombilla 6: apagamos la 6.

- Bombilla 7: apagamos la 7.

- Bombilla 8: apagamos la 8.

- Bombilla 9: encendemos la 9.

- Bombilla 10: apagamos la 10.

Despu¨¦s de todo esto, quedan encendidas las bombillas 1, 4 y 9. Uhmmm¡­

Tomad ahora 20 bombillas y haced lo mismo. Enseguida el resultado¡­

.

?Ya? Si hab¨¦is seguido el proceso sin errores, os quedar¨¢n encendidas las bombillas 1, 4, 9 y 16. Y si tom¨¢is 50 bombillas, quedar¨¢n encendidas las bombillas 1, 4, 9, 16, 25, 36 y 49¡­ ?Veis la relaci¨®n? Correcto: quedan encendidas las bombillas que corresponden a n¨²meros que son cuadrados perfectos. No me negar¨¦is que el resultado no es realmente hermoso.

Y ahora toca explicar si esta es la soluci¨®n para cualquier n¨²mero de bombillas y por qu¨¦ ocurre esto, ya que podr¨ªa ser que al aumentar la cantidad de bombillas se rompiera la magia. Y aqu¨ª es donde entra en juego el concepto de divisor.

Cada bombilla cambia de estado una cantidad de veces que corresponde exactamente con la cantidad de divisores que su n¨²mero tenga. Por ejemplo, como el 6 tiene cuatro divisores (1, 2, 3 y 6), la bombilla 6 se enciende, se apaga, se enciende y despu¨¦s se apaga, y as¨ª se queda; y como el 9 tiene tres divisores (1, 3 y 9), la bombilla 9 se enciende, se apaga y posteriormente se enciende, terminando as¨ª.

A partir de esto, es sencillo deducir que las bombillas que quedar¨¢n encendidas ser¨¢n las que tienen un n¨²mero con una cantidad impar de divisores. Y ahora la pregunta es: ?c¨®mo se calcula la cantidad de divisores que tiene un n¨²mero natural?

El teorema fundamental de la aritm¨¦tica nos dice que todo n¨²mero natural N mayor que 2 puede expresarse de forma ¨²nica (salvo el orden) como producto de potencias de n¨²meros primos. Si los exponentes de estos n¨²meros primos son a₁, ¡­ , a_k, se tiene que la cantidad de divisores de N es:

Cantidad de divisores de N = (a₁ + 1) ¡¤ (a₂ + 1) ¡¤ ¡­ ¡¤ (a_k + 1)

Hemos dicho que, para que la bombilla N quede encendida, debe darse que N tenga una cantidad impar de divisores. Para ello, todos los factores de este producto deben ser impares (si alguno de ellos fuera par, el producto completo ser¨ªa par). Y, para que eso ocurra, debe ocurrir obligatoriamente que todos los exponentes sean pares.

?Y cu¨¢les son los n¨²meros que cumplen que todos los exponentes de su descomposici¨®n en factores primos son pares? Exacto, los cuadrados perfectos: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256,¡­ Ya tenemos la soluci¨®n del problema y la explicaci¨®n del porqu¨¦ de la misma.

Estoy seguro de que algunos (quiz¨¢s muchos) de vosotros ya conoc¨ªais este problema. Espero que a vosotros os haya gustado recordarlo, y que los que os hab¨¦is encontrado con ¨¦l por primera vez hay¨¢is disfrutado con ¨¦l tanto como lo hice yo en su momento.

Problemas de este tipo, de bello resultado y resoluci¨®n simple, los hay de todo tipo. Si conoc¨¦is alguno que cre¨¢is que puede ser de inter¨¦s, no dud¨¦is en hablarnos de ¨¦l en los comentarios.