Names In Boxes and Dante in Purgatory

We investigate two puzzles with a "recreational mathematics" flavour.

The first one ("Names In Boxes") originates in joint work with Anna Gal from 2003. The second one ("Dante in Purgatory") originates in very recent joint work with Kristoffer Arnsfelt Hansen and Michal Koucky. We solve the puzzles and explain their connection to deep unresolved problems of mathematical computer science.

Names in Boxes:

The names of one hundred prisoners are placed in one hundred wooden boxes, one name to each box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; they may look into up to fifty of the boxes to try to find their own name but must leave the room exactly as it was. They are permitted no further communication after leaving the room. The prisoners have a chance to plot a strategy in advance and they are going to need it, because unless they all find their own names they will all be executed. There is a strategy that has a probability of success exceeding thirty percent - find it.

Dante in Purgatory:

There are seven terraces in Purgatory, indexed one to seven. Dante enters Purgatory at terrace one.

Each day, if Dante finds himself at some terrace i, he must play a game of matching pennies against Lucifer:

Lucifer hides a penny, and Dante must try to guess if it is heads up or tails up. If Dante guesses correctly, he proceeds to terrace i + 1 the next morning - if i + 1 is eight, he enters Paradise and the game ends. If, on the other hand, Dante guesses incorrectly, there are two cases. If he incorrectly guesses “heads”, he goes back to terrace one the next morning. If he incorrectly guesses “tails” the game ends and Dante forever loses the opportunity of visiting Paradise.

How can Dante ensure ending up in Paradise with probability at least 75 percent? How long should he expect to stay in Purgatory before the game ends in order to achieve this?