Here’s a fun riddle posed by a student in the recent Algorithms: Design and Analysis course from Stanford University I participated in on the Coursera platform. I’m recording it here for posterity so I won’t forget. It’s fun to collect such riddles. That might make for cool party tricks. Note that I no longer have access to the original post so all this is paraphrasing from memory.

Riddle:

There is a sadistic warden in charge of a prison with 100 prisoners. He wants to execute these prisoners, but after much persuasion on your part, condescends to play a game with them that could result in some of them from spared. Each of the prisoners is numbered from 1 to 100. A room is set up with 100 drawers, all also numbered 1 to 100. Inside each drawer is a slip of paper, again numbered 1 to 100. However, the placement of each slip of paper in the drawers is randomized.

The game is that each prisoner is allowed to visit this room, one at a time. He is allowed to open the drawers one at a time and may open no more than 50 drawers. If he finds his own number on a slip of paper after having opened 50 or fewer drawers, he is saved. He must return each slip of paper into the drawer he found it in and is not allowed to exchange the positions of the slips of paper.

As an additional concession, you are allowed to visit the room before any of the prisoners may do so and examine the contents of all of the drawers. Furthermore, you may perform one and only one exchange before the game starts. That is after having viewed the contents of all 100 drawers, you may choose any two drawers and exchange the slips of paper inside them. You may not make any other changes and you may not communicate anything about the contents of the drawers to the prisoners.

The riddle is thus: what is the optimal strategy for the prisoners and how many the prisoners may be saved from execution using this strategy? The solution is after the break.

Solution:

Each prisoner should begin by opening the drawer corresponding to his own number. If he finds his own number, then he is saved and may stop. If not he should open the drawer shown on the slip of paper he has just seen and so on. This constitutes a closed cycle. By opening the drawer corresponding to his own number, he enters into a cycle that is guaranteed to contain his own number. However it is possible that the length of this cycle exceeds 50 and may even be 100. For example, if the drawer numbered 1 contains the number 2, and drawer number 2 contains the 3 and so on, the cycle length is 100.

But note this observation: if there is a cycle exceeding a length of 50 in the system, then all other cycles must each be less than length 50. Therefore you must use your special power to examine the contents of all drawers and determine if there is such a cycle. If so, you may use your one single allowed exchange to break that cycle in half. This solution guarantees that all 100 prisoners will be able to find their own number without having to open more than 50 drawers and therefore all will be saved.