El problema de las taquillas: ¿por qué las plazas?

Question

Hay 1000 taquillas en un instituto con 1000 alumnos. El problema problema comienza con el primer alumno que abre las 1000 taquillas. el segundo alumno cierra las taquillas 2,4,6,8,10 y así sucesivamente hasta la taquilla 1000; el tercer alumno cambia el estado (abre taquillas cerradas, cierra taquillas abiertas) en las taquillas 3,6,9,12,15 y así sucesivamente; el cuarto estudiante cambia el estado de las taquillas 4,8,12,16 y así sucesivamente. Así sucesivamente hasta que hasta que todos los alumnos hayan tenido su turno.

¿Cuántas taquillas quedarán abiertas al final?

Resolví este problema haciéndolo para 10 taquillas. El patrón era obvio (1,4,9 permanecían abiertas). Es fácil decir entonces que 31 taquillas permanecen abiertas al final. No entiendo por qué sólo los números cuadrados permanecen abiertos al final. ¿Hay alguna razón más profunda?

Answer 1

Los cuadrados son los únicos números enteros que tienen un número impar de divisores.

Todos los demás números enteros (no cuadrados) tienen un número par de divisores.

---

Una visión más profunda:

Dado un número entero $n$ para cada número entero $d$ que divide $n$ el número entero $n/d$ también divide $n$ .

Si $n$ no es cuadrado, entonces para cada número entero $d$ que divide $n$ el número entero $n/d \neq d$ .

Así que podemos dividir los divisores de $n$ en pares, por lo que $n$ tiene un número par de divisores.

Si $n$ es cuadrado, entonces para cada número entero $d\neq\sqrt{n}$ que divide $n$ el número entero $n/d \neq d$ .

Así que podemos dividir los divisores de $n$ excepto $\sqrt{n}$ en pares, por lo que $n$ tiene un número impar de divisores.

Answer 2

Si un número de casillero tiene un número par de factores, se abrirá y cerrará alternativamente y un número par de veces, terminando en la misma configuración en la que empezó.

Los números cuadrados tienen un número impar de factores.

Answer 3

La idea es que es fácil identificar los pares de alumnos que abrirán y cerrarán una taquilla (¡tan fácil como cualquier problema matemático interesante!). Si un alumno abre o cierra una taquilla, significa que su número es divisor del número de la taquilla.

Consideremos la taquilla X. Supongamos que hay un alumno Y que activa la taquilla. Esto significa que sabemos que X/Y es un número entero. Esto también significa que el estudiante X/Y también activará la taquilla.

Tomemos el casillero 12, con los factores 1, 2, 3, 4, 6 y 12. Si los reordeno en pares, (1, 12) (2, 6) (3, 4) podemos ver que por cada alumno que abra una taquilla, habrá uno que la cierre.

Ahora, veamos un cuadrado. Tomemos 16, con los factores 1, 2, 4, 8, 16. Si los reordeno en pares obtengo (1, 16) (2, 8) (4, 4)... pero espera... Tuve que usar 4 dos veces. Tuve que hacerlo porque era un cuadrado. Sin embargo, el estudiante 4 sólo va a alternar el casillero 16 una vez. Por lo tanto, ¡la taquilla quedará abierta al final del día!

Answer 4

Número de taquilla $n$ se activa una vez por cada divisor de $n$ . Si $n$ no es un cuadrado, entonces el mapa $d \to n/d$ es un mapa biyectivo sobre el conjunto de divisores $S_n$ de $n$ . Así $S_n$ tiene un número par de elementos; es la unión disjunta de los conjuntos de la forma $\{d, n/d\}$ cada uno de los cuales contiene $2$ elementos. Si $n$ es un cuadrado, entonces $S_n$ es la unión de los conjuntos $\{d, n/d\}$ para $d^2\not = n$ y un conjunto único $\{\sqrt{n}, \sqrt{n}\}$ . Por lo tanto, el tamaño de $S_n$ es impar. Conmutar un cerrado $n$ veces la deja cerrada si $n$ es par y abierto si $n$ es impar.