15
$\begingroup$

This question is an exact duplicate of:

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.

$\endgroup$

marked as duplicate by David K, Henry, vrugtehagel, Community Mar 23 '17 at 10:27

This question was marked as an exact duplicate of an existing question.

  • 2
    $\begingroup$ Are you familiar with coding? If so, make a script that will work! $\endgroup$ – VortexYT Mar 22 '17 at 13:18
  • 4
    $\begingroup$ He opened all the cells at the first time. They should all have escaped before the second turn... $\endgroup$ – MARTIN Damien Mar 22 '17 at 15:16
  • 2
    $\begingroup$ Let's assume all the prisoners were asleep. $\endgroup$ – Shaun Mar 22 '17 at 15:18
  • 3
    $\begingroup$ related, duplicate math with a different set up $\endgroup$ – user321537 Mar 22 '17 at 15:38
24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Right, that's about it... $\endgroup$ – Parcly Taxel Mar 22 '17 at 12:36
  • 1
    $\begingroup$ So, which is it, the perfect square numbers or the numbers with an odd number of divisors? $\endgroup$ – Shaun Mar 22 '17 at 12:51
  • 5
    $\begingroup$ 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. $\endgroup$ – vrugtehagel Mar 22 '17 at 12:54
  • 10
    $\begingroup$ 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". $\endgroup$ – shoover Mar 22 '17 at 15:17
  • 1
    $\begingroup$ @Shaun should really clarify what the setting is, if the traditional one or what shoover suggests. $\endgroup$ – Guido Mar 22 '17 at 16:32
3
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.