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 and turning it once.
Following the order, the assistant unlocked all the cells and then came back to report that the job was done. Meanwhile, however, the warden had second thoughts. "Maybe I shouldn't let all the prisoners go 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. 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 alone 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 every sixth, and on and on, until 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?
