Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a problem called "The Prison Problem" that I need to explain to my 9-year-old cousin. I would think that he has just started learning about divisors and perfect squares, and as such, I have a proposed solution. Any input from you guys would be welcome, as to what is the best way to go about this.

Problem:

There was a jail with 100 cells in it, all in a long row. The warden was feeling very jolly one night and told his assistant that he wanted to give all the prisoners a wonderful surprise. While they were sleeping, he wanted the assistant to unlock all the cells. This should be done, he told the assistant, by putting the key in each lock, turning it once. The assistant did this, then came back to report that the job was done. Meanwhile, however, the warden has second thoughts. "Maybe I shouldn't let all the prisoners free," he said. "Go back and leave the first cell open, but lock the second one (by putting the key in and turning it once). Then leave the third open, but lock the fourth, and continue in this way for the entire row." The assistant wasn't very surprised at this request as the warden often changed his mind. After finishing this task, the assistant returned, and again the warden had other thoughts. "Here's what I really want you to do," he said. "Go back down the row. Leave the first two cells as they are, and put your key in the third cell and turn it once. Then leave the fourth and fifth cells and turn the key in the sixth. Continue down the row this way." The assistant again did as instructed. Fortunately, the prisoners were still asleep. As a matter of fact, the assistant was getting pretty sleepy, but there was no chance for rest yet. The warden changed his mind again, and the assistant had to go back again and turn the lock in the fourth cell and in every fourth cell down the row. This continued all through the night, next turning the lock in every fifth cell, and then in every sixth, and on and on, until on the last trip, the assistant just had to turn the key in the hundredth cell. When the prisoners finally woke up, which ones could walk out of their cells?

Proposed solution:

Ten cells are left open after this process. Every cell that is a perfect square will remain open (1, 4, 9, 16, 25, 36, 49, 64, 81, and 100). If a number is not a perfect square, then it has an even number of divisors, therefore it will be "toggled" an even number of times and end up where it started (closed). Perfect squares have an odd number of divisors, so they will end up the opposite of where they started (open).

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

This video provides a really wonderful visual explanation for the exact problem you are describing. The video only goes up to 90, but provides all the information you need to generalise it to 100.

http://www.youtube.com/watch?v=LejoPGtliTs

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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