One day, the warden of a prison is, like most wardens in puzzles, feeling a little bit capricious and decides that he wants to get rid of his prisoners, one way or another. He gathers all the prisoners in the yard and explains to them - "Tonight, I will go to each of you, hand you a key, and tell you who has your key. Each day after that, while the others are out of the cells and no one is watching, I will allow each of you to place your key in someone else's cell - and each night, you may collect the keys in your own cell. If, at any point, you are certain that everyone has the key to their own cell, you may summon me, at which point each of you will open your own cell and walk free. If anyone has the wrong key, everyone will be executed then and there. You may discuss your strategy before tonight, but afterwards no communication will be allowed regarding my game. - Oh, and by the way, if you are still here seven years from today, I will execute everyone - it'll be a big birthday for me and I want to retire!"
That night, just as promised, the warden went to each cell and gave each prisoner a key. As he handed each prisoner the key, he whispered to them the name of the person possessing the key to their cell. The keys were entirely indistinguishable from one another, but that was okay, because the prisoners had not counted on being able to tell anything about them. Indeed, the prisoners all seemed confident.
Each day for the nearly seven years, the prisoners all anonymously gave the key in their possession to someone else. Then, hardly a month before the deadline, a prisoner shouted to the warden that they were ready. All the prisoners were certain that they would live, and, lo and behold, when they put the keys in the locks to their cells, every cell opened.
What was their strategy? Exactly how many days did it take?
Hint:
The warden had learned this from his own days as a prisoner, when the same challenge was issued to him and just two other prisoners. It took only six days of trading keys before they were released.
Edit: Oops, turns out my prisoners were kind of dumb in their choice of strategy. (If anyone wants to puzzle out what I was thinking of, the information in the post about should be sufficient - but I consider the puzzle, and this question to more about the most efficient way to do it). The prisoners, if wise, can be free in less than a fortnight.
Answer
9 days.
Every day, each prisoner with an unknown key passes it to the next cell to the left (or to the next guy in alphabetic order, sentence length, age... w/e, just agree on the order on that first day).
Since they know where in the order the owner of their own key is (relative to them), they know on which day to expect their key - they get to keep that, and keep passing the unknown keys as usual. (For example, if guy 4 know guy 7 had his key, he should keep the key he gets at day 3.)
After 9 exchanges, technically possible in the afternoon of day 9, they can be sure everyone has their key.
No comments:
Post a Comment