Problema del Hotel infinito

Question

P. Bienvenido a la infinity hotel tiene un número infinito de habitaciones $1,2,3,4,...$ El administrador se da cuenta todas las habitaciones tienen luz. Él voltea el interruptor de cada otra. (Salas de $2, 4, 6, …$), y Luego se hace lo mismo con cada tercer cuarto. (Salas de $3, 6, 9, …$), y Luego se hace lo mismo con cada cuarto cuarto. (Salas de $4, 8, 12, …$) Así sucesivamente, y así sucesivamente, el proceso continúa para siempre. De los primeros millones de habitaciones, cuántas luces a la izquierda.

Por lo que sé, por los casos de pruebas de que todo el primer número de habitaciones a la izquierda porque los únicos divisores son 1 y él mismo así que cuando él llega a la prime, él simplemente se apaga y nunca va a ella de nuevo. Luego me enteré por los casos que cada Cuadrado de la habitación (es decir, de la sala de $1, 4, 9, 16, 25, ..., (1000^2$) sigue siendo). Por las pruebas que puedo ver que estas son las únicas habitaciones que quedan, y hay 1000 de ellos, pero no estoy seguro de cómo demostrarlo. Sé que tiene que ver con el Tau(n) y, posiblemente, Sigma(n).

edit: Así que esto es lo que se me ocurrió, siéntase libre de hacer comentarios acerca de él:

Establecemos τ(n) para nuestra pregunta por ver τ(n) puede ser par o impar. En la pregunta 2[Que n sea un entero positivo, demostrar que n es un cuadrado perfecto ⇔ τ(n) es impar.], τ(n) es impar ⇔ n es un cuadrado perfecto, de lo contrario, τ(n) es par. Cuando τ(n) es impar se puede notar que la habitación se alcanza un número par de veces ya que no están teniendo en cuenta 1 como divisor. Es decir, cada uno impar tiempo de una habitación que se alcanza se apaga la luz, y cada vez que la habitación es alcanzado las luces están encendidas. Por otra parte, las únicas habitaciones que se llega a un número par de veces son los cuadrados perfectos y estas son las únicas habitaciones que están a la izquierda. Entonces podemos ver que $1000^2 = 1000000$, e incluimos esta sala en nuestra pregunta. Podemos concluir que las habitaciones $1^2, 2^2, 3^2, … 999^2, 1000^2$ son las únicas habitaciones de la izquierda con las luces encendidas, por lo que hay $1000$ de ellos.

Lo que realmente requiere una gran cantidad de pensamiento, espero que mi lógica es correcta.

Answer 1

No hay necesidad de soluciones innecesariamente complicadas.

Si $d$ es un divisor de $n$, entonces $\frac nd$ también es un divisor de $n$. Si sincronizarlos, vemos que el número de divisores es uniforme, a menos que haya un divisor $d$ tal que $d=\frac nd\Longleftrightarrow d^2=n$, es decir, $n$ es un cuadrado perfecto. En ese caso, el número de divisores es impar.

Answer 2

Copia de seguridad de un paso: asumir la hotel comienza oscuro, y que en la primera pasar cada luz se enciende. Usted puede ver fácilmente que este es el mismo problema. Una luz es cambiada cada vez que uno alcanza uno de sus divisores. Una luz que termina en la posición off iff que número es uniforme, ya que chasquea un interruptor de dos no redes de ningún cambio. ¿Qué números tienen un número impar de divisores? Los cuadrados perfectos.

Answer 3

El estado final en la sala de $n$ depende de cuántos divisores $n$ tiene: si tiene un número impar de divisores, entonces la luz se acaban de comenzar; si tiene un número par de divisores, la luz se terminan fuera.

Así, los números que tienen un número impar de divisores? Si el primer descomposición de $n$ es $$ n=p_1^{a_1}\cdots p_k^{a_k}, $$ a continuación, podemos obtener todos los posibles divisores de $n$ mediante la formación de los números de $p_1^{r_1}\cdots p_k^{r_k}$,$0\leq r_j\leq a_j$. Así que tenemos $a_j+1$ opciones para $r_j$: el número total de divisores es entonces $$ (a_1+1)(a_2+1)\cdots(a_k+1). $$ Para que este número sea impar, todos los de $a_1,\ldots,a_k$ necesidad de ser (de lo contrario, $a_j+1$ sería incluso para algunos $j$, haciendo que el producto aún). Por lo $a_j=2b_j$, dicen, y $$ n=(p_1^{b_1}\cdots p_k^{b_k})^2. $$ Para los enteros positivos con un número impar de divisores son precisamente las plazas.