A Drunken Prison Guard. [duplicate]
This is a number theory exercise I've been stuck on for a while. It was set during a lecture I attended once. It goes something like this . . .
Suppose there's a full circular prison with 100 cells and one prison guard who hates his job. He gets drunk one night and decides to play a game while the prisoners were asleep. He walks the circular prison and, the first time, he opens every cell; the second time, he closes every even numbered cell; the third time, he touches every third cell, and if that cell is open, he closes it, and he opens it otherwise; the fourth time, he touches every fourth cell, and if that cell is open, he closes it, and he opens it otherwise; and so on until his hundredth time around the prison. He then falls asleep.
By the morning, after the prison guard's hundredth lap, every prisoner in an open cell escapes.
Which prisoners escape?
Thoughts:
I've thought of trying a modified use of the Sieve of Eratosthenes but there's got to be a more elegant, less brute-force solution.
Well, cell $n$ is being opened and closed as many times as it has divisors. Thus, it will only end up open if the number of divisors is odd. Therefore, only the perfect square numbered cells will be open in the end.
A quick explanation on why perfect squares are the only numbers with an odd number of divisors; for every $d\mid n$ there exists a $\frac{n}{d}\mid n$, so divisors come in pairs. The only non-pair that can occur is when $d=\frac nd$, or when $n=d^2$. Then $d$ is the only divisor not part of a pair, and thus makes the total number of divisors odd.
Under @shoover's interpretation of the problem where the circularity is relevant, here's a simple python script that prints the open cells after each pass:
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
The final result is
[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]
which doesn't look like it has an elegant description to me. My guess would therefore be that the conventional version of the problem was the intended one.