Un problema de puerta muy interesante

Question

Mi maestro me hizo una pregunta que es la siguiente:

Hay $1000$ puertas numeradas del $1$ al $1000$, y hay $1000$ hombres numerados del $1$ al $1000$.

En primer lugar, el hombre numerado $1$ va y abre todas las puertas.

En segundo lugar, el hombre numerado $2$ va y cierra las puertas que están numeradas múltiplos de $2$

En tercer lugar, el hombre numerado $3$ va y cambia el estado de las puertas que están numeradas múltiplos de $3$

Por ejemplo, cierra la puerta numerada $3$ y abre la puerta numerada $6$

Entonces, después de que el hombre numerado $1000$ regrese de su trabajo, ¿cuántas y cuáles puertas permanecerían abiertas?

Pensé en eso por una hora, pero no pude llegar a nada.

Mi maestro me dijo que hay una lógica matemática simple y pura detrás de esto

¿Puedes ayudarme con esto??

Answer 1

Una cosa que podemos hacer es dejar que los primeros $10$ estudiantes vayan a hacer su cosa de abrir/cerrar con los casilleros. Los estudiantes que vengan después de ellos no van a tocar los casilleros $1-10$, por lo que podemos ver cuáles en ese primer grupo aún están abiertos e intentar adivinar el patrón.

Cuando hacemos eso, descubrimos que los casilleros $1, 4,$ y $9$ están abiertos y los demás están cerrados. Ahora, eso no es mucho para basarse, así que tal vez podrías dejar que los siguientes $10$ estudiantes vayan a hacer su cosa. Luego los primeros $20$ casilleros ya han sido tocados, y encontramos que los casilleros $1, 4, 9,$ y $16$ son los únicos en los primeros $20$ que aún están abiertos. Entonces, ¿cuál es el patrón?

Tomemos cualquier casillero antiguo, como el $48$ por ejemplo. Su estado se altera una vez por cada estudiante cuyo número en la fila es un divisor exacto de $48$. Aquí hay un cuadro de lo que quiero decir:

 Número del estudiante    deja el casillero 48

      1                abierto
      2                cerrado
      3                abierto
      4                cerrado
      6                abierto
      8                cerrado
     12                abierto
     16                cerrado
     24                abierto
     48                cerrado

Observe que $48$ tiene un número par (diez) de divisores, a saber $1,2,3,4,6,8,12,16,24,48$. Entonces el casillero termina cerrado. Cualquier número de casillero que tenga un número par de divisores terminará cerrado.

¿Qué números tienen un número impar de divisores? Esa es la respuesta a este problema. Solo para ayudarte, aquí están los números de casillero hasta $100$ que quedan abiertos: $$1,4,9,16,25,36,49,64,81,100.$$

Intenta describir estos números de una manera diferente a "tener un número impar de divisores". Piensa en multiplicar números juntos. Cuando entiendas cómo describirlos, verás que $31$ de los $1000$ casilleros aún están abiertos.

Answer 2

Debes notar que las operaciones IMPARES significan que la puerta está abierta y las operaciones PARES significan que la puerta está cerrada. Puedes entenderlo con la ayuda de un ejemplo sencillo.

Por ejemplo: La puerta número $10$ será abierta primero por el primer hombre, luego cerrada por el $2$do hombre, luego abierta por el $5$to hombre y finalmente cerrada por el $10$mo hombre.

Entonces, la lógica matemática que está funcionando aquí es la siguiente:

Si el número de la puerta tiene un número impar de factores, entonces permanecerá abierta y si el número de la puerta tiene un número par de factores, entonces se cerrará al final.

Para calcular el número de factores de un número, utilizamos la fórmula $(a+1)(b+1)(c+1).....$ donde a, b, c son los exponentes de los factores primos del número. Nota que si el número es un cuadrado perfecto, entonces a, b, c... son todos pares, por lo tanto el número de factores ($(a+1)(b+1)(c+1).....$ ) es impar. Y si el número no es un cuadrado perfecto, entonces uno de a, b, c... será impar y por lo tanto el número de factores ($(a+1)(b+1)(c+1).....$ ) será par. Por lo tanto, las puertas con números cuadrados perfectos permanecerán abiertas.

O las puertas número $1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961$ permanecerán abiertas ($31$ en total).

Answer 3

Al final, el estado de una puerta refleja la paridad de su número de divisores.

Por ejemplo, la puerta número $20$ es abierta por $1$, cerrada por $2$, abierta por $4$, cerrada por $5$, abierta por $10$ y cerrada por $20.

El número de divisores de un entero es el producto de las multiplicidades de sus factores primos más uno.

En el caso de $20=2^2\cdot5$, esto es $3\cdot2=6$, un número par.

Entonces una puerta está cerrada al final para todos los números que tienen al menos un factor primo con multiplicidad impar. Por el contrario, está abierta al final si todos los factores tienen multiplicidad par, por lo tanto cuando el número es un cuadrado perfecto.

Answer 4

La lógica más simple que he encontrado es que todo número natural $n$ puede representarse como $n=p\cdot q$ donde $p,q\in\Bbb{N}$ y $p,q\leq n$. Por lo tanto, cuando el hombre numerado con $p$ cierra/abre la puerta numerada con $n$, entonces el hombre numerado con $q$ viene y la vuelve a abrir, y no importa cuántas veces se haya cerrado/abierto la puerta, siempre se cancelan entre sí. Así, al final todas las puertas deben estar cerradas, excepto las puertas cuyo número correspondiente $n$ tenga dos factores $p$ y $q$ idénticos (es decir, cuadrados) para los cuales el hombre numerado con $p$ y el hombre numerado con $q$ eran en realidad la misma persona y por lo tanto no hubo reversión. Dado que solo hay $31$ cuadrados entre $1$ y $1000$ (incluyendo $1$), solo quedarán abiertas $31$ puertas correspondientes a los cuadrados.

Nota: Sin embargo, la representación no es única, es decir, puedes encontrar múltiples representaciones para un dado $n$ (por ejemplo, para $n=6$ hay dos representaciones diferentes $6=1\cdot6=2\cdot3$), pero los factores $p$ y $q$ son únicos entre sí (no se repetirán en otras representaciones).