DIVISORESHOTELES 2

COSAS DE DIVISORES Y HOTELES

En esta sesión trataremos de resolver el siguiente problema:

Problema: “El hotel de las mil habitaciones”. Cuentan que en cierto país había un gran hotel que tenía 1000 habitaciones y otros tantos empleados. Estos, un día que no tenían mucho trabajo, se dedicaron a jugar abriendo y cerrando las puertas de las mil habitaciones. Al principio todas las puertasestaban cerradas y empezó el primer empleado abriéndolas todas; siguió el segundo cerrando todas las puertas pares y luego el tercero cambiando de posición (abriendo si estaban cerradas y cerrando si estaban abiertas) todas las habitaciones cuyo número era múltiplo de tres. El cuarto hizo lo mismo; es decir: cambiar de posición todas las puertas cuyo número era múltiplo de cuatro y así pasaron todos losempleados, cada uno de ellos cambiando de posición las puertas que le correspondían. El último tuvo poco trabajo, pues sólo abrió o cerró la puerta número mil. ¿Qué hizo, la cerró o la abrió? Más aún: ¿qué habitaciones quedaron abiertas?, ¿cuántas fueron en total?

El problema, a primera vista, parece complicado pues observamos que cada habitación sufre un proceso distinto. Así, por ejemplo, lahabitación número 18 la cambian de posición los empleados 1, 2, 3, 6, 9 y 18, mientras que la siguiente, la 19, solo dos empleados (el 1 y el 19) modifican la posición de la puerta.
De todos modos, a poco que analicemos la situación, llegamos a resultados que abren algunas posibilidades que pueden conducir a la resolución del problema.
a) Las habitaciones marcadas con números primos sufrenúnicamente dos cambios (sólo hay dos divisores) y, por tanto, al final del proceso estarán cerradas.
b) El número de cambios de posición de una habitación depende del número de divisores de su número; luego parece interesante encontrar una fórmula que nos dé el número de divisores de un número.
c) El hecho de que una habitación esté, al final del proceso, abierta o cerrada dependerá del número dedivisores que tenga el número de habitación: si este número es par la habitación, al final, estará cerrada; mientras que si el número es impar la habitación estará abierta.
Así planteado, ya sólo nos falta buscar aquellas habitaciones cuyo número tiene un número impar de divisores. Esa es la pregunta clave “¿Cuántos números del 1 al 1000 tienen un número impar de divisores?”
Para resolver esta cuestión,en primer lugar buscamos la manera de calcular el número de divisores para, a continuación, hallar su paridad.

Problema auxiliar nº 1: Si ¿cuántos divisores tiene? Y si ¿cuántos divisores tiene? En general si ¿cuántos divisores tiene N?
Solución:
Si sus divisores son .En total divisores
Si sus divisores son:

lo que da lugar a un cuadrado de filas y columnas; por tanto divisores.Siguiendo con este proceso si el número de divisores de N será:

Problema auxiliar nº 2: ¿Cómo tiene que ser un número para que tenga un número impar de divisores?
Solución:
Si sabemos, por el problema anterior, que el número de divisores es: Para que este número sea impar es preciso que todos los factores sean impares, lo cual implica que p,q,…,r deben ser pares. Ahora bien, ¿cómo debe ser Npara que p,q,…,r sean pares?. La respuesta es sencilla: “N debe ser cuadrado perfecto”
Por tanto hemos llegado a un resultado clave: “Únicamente los cuadrados perfectos tienen un número impar de divisores; el resto siempre tendrá un número par”

Con este resultado podemos resolver fácilmente el problema inicial.
La habitación número 1000, al no ser cuadrado perfecto, tendrá un número par dedivisores y, por tanto, cambiará de posición un número par de veces. Como al principio estaba cerrada acabará cerrada. Una habitación como la 64, al ser cuadrado perfecto tendrá un número impar de divisores y, como al principio estaba cerrada acabará abierta. Resumiendo:
Cerradas: 2,3,5,6,7,8,10,11,12,…….
Abiertas: 1,4,9,16,25,36,49,………
Para averiguar el número de habitaciones abiertas basta...