A prison warden was feeling capricious and played a game with the prison keys:
- Each prisoner is handed a key to another prisoner’s cell.
- Each prisoner will know which other prisoner was initially given the key to their cell (but does not know whose key they were handed).
- Each day, when all prisoners are out of their cells and no one is watching, each prisoner is allowed to place keys in another prisoner’s cell.
- Each night, each prisoner can collect any keys placed in their cell.
- The prisoners can summon the warden when they’re sure everyone has their own key – but if they are wrong, they’re immediately executed.
- The prisoners can discuss a strategy beforehand but cannot communicate in any way after keys are handed out.
What is the fewest number of days it would take for the prisoners to be sure everyone has their key? What was the strategy to achieve this?
Solution
Just N-1 days, where N is the number of prisoners.
- Each day, prisoners pass the unknown key in their possession to the next cell (in their strategic discussion, they would agree on an order, like always passing to the left or alphabetically). E.g., A > B > C > D > E > A.
- Since each prisoner knows who has the key to their cell, each prisoner knows which day to expect their key to arrive – on that day, they hold onto that key, and all other days they continue passing the unknown keys as usual.
- After the (N-1)th day, everyone can be sure everyone has their own key.