Skip to content

Solución: luces y sombras

by en 23/06/2013

¡Hola!

Aquí estamos un domingo más, resolviendo el acertijo de la semana 🙂

En esta ocasión os contábamos la extraña forma que un carcelero tenía de apagar las luces de los calabozos que tenía a su cargo. Se dedicaba a recorrer el pasillo una y otra vez pulsando primero todos los interruptores, luego uno de cada dos, luego uno de cada tres… y así hasta que en el último recorrido se pulsaba únicamente el interruptor del último calabozo. Con cada pulsación, la luz del calabozo correspondiente se invertía, pasando de apagada a encendida o viceversa.

Os preguntábamos el estado final de la luz de algunos calabozos sabiendo que de partida todos estaban encendidos.

En esta ocasión, David, en los comentarios, puso su propuesta de solución pero ¡no acertó del todo! Es verdad que esta vez pusimos un montón de preguntas, y si no se hacía con cuidado era fácil equivocarse.

Empecemos con el estado del primer calabozo por el que os preguntábamos, el número 9. Lo que necesitamos saber es cuántas veces se pulsará su interruptor. Es obvio que en el primer paseo del carcelero pulsará el interruptor, porque en ese momento está pulsándolos todos, por lo que la luz pasará de estar encendida a estar apagada. En el segundo paseo, donde el carcelero pulsa uno de cada dos, cambiará el estado de los calabozos 2, 4, 6, 8, 10 … por lo que el 9 se queda inmune a este recorrido. Esto cambia en el tercero, donde pulsa sobre los interruptores de los calabozos 3, 6, 9, … por lo que la luz de nuestro calabozo pasará de estar apagada a estar encendida. Siguiendo este proceso, es fácil ver que la luz no volverá a cambiar hasta el noveno recorrido, que volverá a apagarse; y ya no se cambiará más, sin importar el número de calabozos que haya en el pasillo.

De esta explicación la conclusión importante, como dijo David, es que lo que nos interesa es saber los divisores del número por el que preguntamos. El carcelero tocará el interruptor de nuestro calabozo en los paseos cuyo número sea un divisor exacto del número del calabozo. Pongamos los divisores de los tres primeros números que os proponíamos:

Nº calabozo Divisores
9 1, 3, 9
10 1, 2, 5, 10
11 1, 11

Por cada divisor que tengamos, la luz invierte su estado. Esto significa que si el número de divisores es par, la luz terminará encendida (igual que empieza), y si es impar la luz terminará apagada. Por lo tanto, el preso del calabozo 9 dormirá con la luz apagada, pero los de los calabozos 10 y 11 lo harán con la luz encendida.

Con esto, hacer un programa que nos diga si un calabozo acaba encendido o apagado no es demasiado complicado: podemos ir probando con todos los valores entre 1 y el número del calabozo, y cada vez que nos encontramos un divisor invertimos el estado de la luz. Cuando terminemos escribimos ese estado, y hemos acabado.

Pero poner un acertijo así ¡sería injusto para nuestros lectores que no saben programar! Porque responder a la pregunta del estado final del calabozo 529 sería muy muy aburrido. De modo que seguro que podemos pensar un poco más…

En realidad no nos interesa saber los divisores exactos, es decir no nos importa saber que los divisores de 10 son 1, 2, 5 y 10. Lo que nos interesa es saber que hay 4 divisores. De hecho, ni siquiera nos interesa saber que son 4 exactamente… nos interesa saber que tiene un número par de divisores.

¿Hay alguna manera de averiguar esto? ¡¡Pues sí!! ¡La hay! Y ahí es donde estaba el acertijo 🙂 Hay dos formas de explicarlo. Una es informal y la otra es matemática. Vamos con la primera 🙂

Para eso, vamos a coger un número, de los que os preguntábamos, que tenga más divisores, como por ejemplo el 24. El primer divisor del número 24 es, como con todos los demás, el número 1. Ahora bien, el número 1 tiene como “divisor pareja” al propio número 24. Esto se debe a que si 1 es divisor de 24, entonces al dividir 24 entre 1 da otro número que también es divisor, y ese número es el propio 24.

Veamos otro ejemplo. El siguiente divisor de 24 es el 2. Si dividimos 24 entre 2, nos da 12; por tanto el 12 es también divisor de 24, pues 24 entre 12 es 2. ¿Veis? Cada divisor de un número tiene siempre un divisor “pareja”. Los podemos poner de colores:

Divisores de 24
1 2 3 4 6 8 12 24
4*6=24
3*8=24
2*12=24
1*24=24

Esta tabla nos demuestra que el número 24 tiene también un número de divisores par, por tanto en el calabozo 24 la luz terminará encendida.

Pero si todos los divisores de cualquier número tienen otro divisor “pareja” entonces ¿tienen todos los números un número par de divisores? ¡Claramente no! Al fin y al cabo, ya vimos hace un momento que el calabozo 9 acababa con la luz apagada, porque tenía un número impar de divisores. ¿Por qué el 9 es especial? Pintémoslo:

Divisores de 3
1 3 9

El número 9 tiene una característica peculiar: el divisor 3 se tiene a sí mismo como “divisor pareja” (3*3 = 9). Eso hace que el número de divisores de 9 sea impar.

Y en general, ¿cuando ocurre esto? Pues, como seguro que ya has averiguado, un número tiene una cantidad impar de divisores cuando es un cuadrado perfecto, es decir cuando su raíz cuadrada es exacta, como les ocurre al 4 (=2*2), 9 (=3*3), 16 (=4*4), … Por ejemplo, el número 16 tiene como divisores al 1, 2, 4, 8 y 16. El 4, que queda en el centro, se tiene a sí mismo como “divisor pareja”, pero sólo “cuenta una vez”, y hace que el 16 tenga un número impar de divisores.

Una vez que nos hemos dado cuenta de esto ¡ahora sí que podemos contestar deprisa a nuestras preguntas, sin necesidad de programar! Basta calcular la raíz cuadrada y, si da justo, sabremos que el número de divisores es impar y la luz quedará por tanto apagada. En otro caso, quedará encendida. Las respuestas a nuestras preguntas son:

  • 9 (=3*3) : apagada
  • 10 : encendida
  • 11 : encendida
  • 23 : encendida
  • 24 : encendida
  • 25 (=5*5) : apagada
  • 527 : encendida
  • 528 : encendida
  • 529 (=23*23): apagada

La demostración matemática es un poco más complicada y pasa, como intuyó David, por factorizar los números. Pero en cualquier caso se terminará llegando a la misma conclusión que hemos llegado aquí 🙂 ¡Esperamos haberos convencido!

Como siempre, si te gusta programar, puedes probar tu solución aquí. Si lo haces ¡ten cuidado! Aunque el ejercicio es similar al del acertijo, el planteamiento es diferente y las luces empiezan apagadas 🙂

¡Hasta el próximo!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: