6. Abriendo y cerrando puertas

Enunciado

Las 100 habitaciones de un hotel están cerradas. Hay una fila de 100 personas para ingresar al mismo y hacer el siguiente experimento:

La 1er persona ingresa y abre todas las puertas, luego ingresa la 2da y altera el estado todas las puertas que son múltiplos de 2 (las cierra), luego la 3era altera el estado de las puertas que son múltiplos de 3 (las que están abiertas las cierra y las que están cerradas las abre), la 4ta persona altera el estado de las puertas que son múltiplos de 4, etc.

¿Cuántas puertas quedan abiertas?

Respuesta

Para resolver este problema, analicemos cómo se alteran las puertas a medida que ingresan las personas:

• inicialmente, todas las puertas están cerradas;
• la persona que ocupa el $n$-ésimo lugar en la fila altera el estado de las puertas que son múltiplos de $n$;
• por lo tanto, la $k$-ésima puerta se alterará cada vez que el número de la persona que entra sea un divisor de $k$.

La $k$-ésima puerta quedará abierta si es alterada un número impar de veces, ya que empieza cerrada. Pero como cada persona que está en la fila en una posición que es divisor de $k$ altera su estado, estamos buscando las puertas cuyo número tenga un número impar de divisores. Por ejemplo, la puerta $36$ queda abierta ya que es alterada por las personas $1$, $2$, $3$, $4$, $6$, $9$, $12$, $18$, y $36$ (sus divisores). Un ejemplo diferente sería la puerta $12$, que es alterada por las personas $1$, $2$, $3$, $4$, $6$ y $12$ (número par de divisores) y queda cerrada. Reducimos nuestro problema al de averiguar cuáles son los números con una cantidad impar de divisores

Quienes ya tienen experiencia en la resolución de problemas matemáticos a nivel olímpico, son conocedores de un resultado que nos dice que en general la cantidad de divisores de un número es par, excepto cuando el número es un cuadrado perfecto. Esto se debe a que los divisores generalmente se puede organizar de a pares. Por ejemplo, para $12$ podemos organizarlos en los pares: $(1,12)$,$(2,6)$ y $(3,4)$. Sin embargo, si $k$ es un cuadrado perfecto, para organizarlos de a pares uno de sus divisores debe repetirse. Por ejemplo, para $9$: $(1,9)$ y $(3,3)$, lo que da un número impar de divisores.

Veamos como demostrar lo comentado en el párrafo anterior. Todo número $k$ natural puede factorizarse en términos de sus divisores primos

$$ k = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_j^{e_j}, $$

donde $\lbrace p_1, \cdots, p_j \rbrace$ es un conjunto de números primos diferentes entre sí y $\lbrace e_1, \cdots, e_j \rbrace$ son sus exponentes.

Podemos aprovechar la factorización anterior para averiguar cuántos divisores tiene el número $k$. Para ello, debemos pensar que todo divisor se puede construir con el producto de potencias de los números primos $\lbrace p_i \rbrace_{i \leq j}$. Por ejemplo, podemos construir un divisor con el siguiente criterio de potencias $p_1^{e_1} \times p_2^0 \times p_3^7 \times \cdots p_j^0 = p_1^{e_1}p_3^7$ donde la potencia del primer primo es $e_1$ la del tercero es $7$ y la de todos los restantes son cero. De esta forma, podremos construir los divisores con todas las posibles formas de combinar las potencias de los factores primos¹.

Como cada primo $p_i$ tienen $e_i+1$ potencias (hay que contar a $0$ como potencia también), la cantidad de divisores de $k$ es igual al producto²

$$ d(k) = (e_1+1)(e_2+1) \cdots (e_j+1)= \prod_{i=1}^j (e_i+1). $$

La cantidad de divisores $d(k)$ es impar si y sólo si cada $(e_i+1)$ es impar y por lo tanto, cada $e_i$ debe ser par. En ese caso $e_i= 2 f_i$ para algún natural $f_i$, entonces

$$ \begin{split} k &= p_1^{2f_1} \times p_2^{2f_2} \times \cdots \times p_j^{2f_j} \\ &= \left( p_1^{f_1} \times p_2^{f_2} \times \cdots \times p_j^{f_j} \right)^2, \end{split} $$

es decir, $k$ es un cuadrado perfecto.

Los números que son cuadrados perfectos hasta 100 son

$$ \begin{split} 1^2&=1 \\ 2^2&=4 \\ 3^2&=9 \\ 4^2&=16 \\ 5^2&=25 \\ 6^2&=36 \\ 7^2&=49 \\ 8^2&=64 \\ 9^2&=81 \\ 10^2&=100, \end{split} $$

y por lo tanto, hay 10 puertas que permanecerán abiertas al final del experimento.