A Drunken Prison Guard.

Question

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.

Are you familiar with coding? If so, make a script that will work! — Xetrov, Mar 22 '17 at 13:18
He opened all the cells at the first time. They should all have escaped before the second turn... — MARTIN Damien, Mar 22 '17 at 15:16

score 24 · Accepted Answer · 2017-03-22T12:37:06.697

24

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.

edited Mar 22 '17 at 12:37

answered Mar 22 '17 at 12:35

Right, that's about it... – Parcly Taxel Mar 22 '17 at 12:36
1

So, which is it, the perfect square numbers or the numbers with an odd number of divisors? – Shaun Mar 22 '17 at 12:51
5

Both. The perfect square numbers are the numbers with an odd number of divisors. In fact, my little explanation in the second part of my post proves (not very formal, but the idea is there) that a number has an odd number of divisors if and only if it is a square. – Mar 22 '17 at 12:54
10

This works in the traditional statement of this puzzle where the cells are all in a line, and the guard returns to the start and begins counting at the 1st cell. How does circular prison affect the answer? Let's try it: 1st pass toggles cells 1-100. 2nd pass starts at 1 and toggles cells 2,4,6,...,100. 3rd pass again starts at 1, and toggles 3,6,9,...,99. But guard hasn't made a full circle, so does 3rd pass also toggle 2? Does 4th pass start where he left off at 100 or at 3, or start over at 1? The problem statement says "every 4th cell", not "every cell whose number is divisible by 4". – shoover Mar 22 '17 at 15:17
1

@Shaun should really clarify what the setting is, if the traditional one or what shoover suggests. – Guido Mar 22 '17 at 16:32
I watch a very good explanation of this puzzle here – Juan Carlos Oropeza Mar 22 '17 at 17:25
@shoover That's a good question, thank you. Let's say the guard starts over again. The third pass doesn't toggle 2. – Shaun Mar 22 '17 at 17:31

score 3 · Answer 2 · edited Mar 23 '17 at 09:35

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.

A Drunken Prison Guard.

Thoughts:

2 Answers2

Linked

Related