A kindly prison warden decided to free his 25 prisoners for good behavior. The p

Question

A kindly prison warden decided to free his 25 prisoners for good behavior. The prisoners were locked in separate cells, numbered 1 through 25. Each cell had a lock that opened when the key was turned once and locked when the key was turned again. The next turn would open the lock, the next would close it, and so on. One night, when the prisoners were sleeping, the warden quietly turned each lock once, opening all of the cells. Then he began to worry that he had freed too many prisoners so he went back and turned every other lock beginning with cell 2, thus locking those cells. Thinking that there might be still too many prisoners freed he gave every third lock a turn beginning with cell 3. Then he turned every fourth lock, then every fifth lock, then every sixth lock, and so on all the way to the 25th lock. (Of course he only turned one lock for every 13th lock, one lock for every 14th lock, and so on.)

a.) Which cells ended up unlocked? Explain.
b.) Do the numbers suggest any patterns?
c.) If the prison had 50 cells, which cells would be unlocked?
d.) State a general result if there are n cells. State a theorem about integers that you would need in order to prove this general result and then prove it.

Explanation / Answer

a. Cells 1, 4, 9, 16, and 25 ended up unlocked. Explanation? All the others ended up locked.

b. The pattern is that only cells numbered with squares ended up unlocked.

c. Cells 1, 4, 9, 16, 25, 36, and 49 would end up unlocked.

d. The general result is that cell m will end up unlocked if and only if m = k^2 for any integer k and m ? n.

A number theorist can come up with the theorem. My theorem is that if I'm in jail, I want to get a "perfect square" cell number in the hope that the warden might let me out after he's had one too many glasses of wine.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.