Problem 5.

A jailer in a prison with infinitely many cells decides to release some of the prisoners. The jailer first unlocks the doors of all the cells. Next he reverses the locks on the door of every second cell (cell numbers 2, 4, 6,...); so, the even numbered cells are now locked again. Next he reverses the locks on the door of every third cell (cell numbers 3, 6, 9,...). Cell 3 was unlocked and is now reversed back to locked. Cell 6, however, had last been locked; so, it is now reversed back to unlocked. Next the jailer reverses the locks on the doors of every fourth cell, then every fifth cell,.... The process continues without end. Which cells will remain unlocked?

[Problem submitted by Ron Kendis, LACC Professor of Mathematics.]

Solution:

Consider the first few reversals. Initially the door to every cell is locked.
First reversal: The doors of all cells are unlocked.
Second reversal (every second cell reversed): 1, 3, 5, 7, 9, 11, 13, 15, 17, ... are open.
Third reversal (every third reversed): 1, 5, 6, 7, 11, 12, 13, 17, 18, ... are open.
Fourth reversal (every fourth reversed): 1, 4, 5, 6, 7, 8, 11, 13, 16, 17, 18,... are open.
Fifth reversal (every fifth reversed): 1, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 18,... are open.
Sixth reversal (every sixth reversed): 1, 4, 7, 8, 10, 11, 12, 13, 15, 16, 17, ... are open.
Seventh reversal (every seventh reversed): 1, 4, 8, 10, 11, 12, 13, 14, 15, 16, 17, ... are open.
Eighth reversal (every eighth reversed): 1, 4, 10, 11, 12, 13, 14, 15, 17, ... are open.
Ninth reversal (every ninth reversed): 1, 4, 9, 10, 11, 12, 13, 14, 15, 15, 17, 18, ... are open.

Notice in the ninth reversal that the first three terms are perfect squares. The solution to the problem hinges (Dr. Kendis' pun) on the factors of each number. Every number except perfect squares has an even number of factors, and so each of those cells will ultimately remain locked. Only the cell numbers which are perfect squares (1, 4, 9, 16, 25,...) will remain unlocked.


| Problem 1 | Problem 2 | Problem 3 | Problem 4 | Problem 5 |
| Problem 6 | Problem 7 | Problem 8 | Problem 9 | Problem 10 |

RETURN
- Last Updated: 12/10/08