Un carcelero borracho.

Question

Este es un número de la teoría de ejercicio he sido atrapado por un tiempo. Fue durante una conferencia que asistieron a la vez. Es algo como esto . . .

Supongamos que hay una circular de la prisión con 100 células y un guardia de la prisión que odia su trabajo. Se emborracha una noche y decide jugar un juego mientras que los prisioneros estaban dormidos. Él camina en la circular de la prisión y, por primera vez, se abre cada una de las células; la segunda vez, él cierra todos los pares de células; la tercera vez, le toca a cada tercio de la célula, y que si la celda está abierta, se cierra, y se abre otra manera; la cuarta vez, le toca a cada cuarto de la célula, y que si la celda está abierta, se cierra, y se abre otra manera; y así sucesivamente hasta su centésima vez alrededor de la prisión. Entonces él se queda dormido.

Por la mañana, después de que la guardia de la prisión de la enésima vuelta de cada prisionero en una celda abierta escapa.

Que la fuga de los presos?

Pensamientos:

He pensado en probar una modificación de uso de la Criba de Eratóstenes, pero tiene que haber una forma más elegante, menos de fuerza bruta solución.

Answer 1

Así, la celda $n$ se abre y se cierra como muchas veces se ha divisores. Por lo tanto, sólo se abrirá si el número de divisores es impar. Por lo tanto, sólo el cuadrado perfecto numerado las células se abrirá en la final.

---

Una rápida explicación sobre el por qué los cuadrados perfectos son los únicos números con un número impar de divisores; para cada $d\mid n$ existe un $\frac{n}{d}\mid n$, por lo que los divisores que vienen en pares. El único no-pair que puede ocurrir es cuando $d=\frac nd$ o al $n=d^2$. A continuación, $d$ es el único divisor no parte de un par, y por lo tanto hace que el número total de divisores impares.

Answer 2

Interpretación de @shoover del problema donde la circularidad es relevante, aquí es un script de python simple que imprime las celdas abiertas después de cada paso:

doors = [False for n in range(0, 100)]

def print_f():
    print [i + 1 for (i, bool) in enumerate(doors) if bool]
        # code is 0-based, question statement is 1-based

paces = 0
step = 1

while step < 100:
    location = paces % 100
    doors[location] = not doors[location]
    if location + step >= 100:
        step += 1
        print_f()
    paces += step

El resultado final es

[1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 20, 21, 22, 24, 27, 33, 34, 35, 36, 38, 39, 40, 41, 44, 47, 49, 50, 51, 53, 57, 58, 62, 64, 65, 71, 73, 76, 77, 79, 80, 81, 86, 87, 88, 90, 92, 94, 96, 99]

que no se ve como tiene una descripción elegante para mí. Mi conjetura sería que la versión convencional del problema era el previsto.