3
$\begingroup$

A friend of mine heard from a friend of his of the following problem that my friend's friend claims remains open? The game is as follows: There are 100 persons with different names, their names are written on pieces of paper and placed inside 100 boxes(each box with one name and all the boxes with a different name).

The persons go one by one into the room with the boxes and select fifty of them, they look inside these and if they find their name they take out the piece of paper and show it to the "Game Master" which in turn spares their life, if their paper isn't inside they are killed.Notice the other persons cannot know what was inside the boxes he opened or if he died or not.After the person passes all the boxes are closed again, and then the next person goes in and does the same. This goes on until all the persons have passed. Can we find a strategy were there is at least a $20\%$ chance all of them survive?

Since we get no more information as the game goes on we need to plan it from the start, this amounts to telling each person what boxes they have to open.

In graph theory each strategy will be a different bipartite graph $G$ where the two parts $X$ and $Y$ both have $100$ vertices and the vertices of $X$ all have degree $50$. Notice if all the persons survive then the edges between the boxes with the persons names and the persons shall provide a perfect matching, so the number of permutations of the boxes where all people survive is equal to the number of perfect matchings the graph $G$ has.

Notice that for a strategy to have at least a $20\%$ chance that all survive we need its corresponding graph to have at least $99!\cdot20$ perfect matchings, is this possible?

Where can I find information about problems similar to this one, or the theory that is being used to tackle it at the moment?

$\endgroup$
  • $\begingroup$ It is important to notice that a bipartite graph such as you describe does not capture all possible strategies. Suppose prisoner #1 plans to open a certain box, and then make his later choices of which boxes to open depend on the name he finds in the first box. And in general all his choices after the first can depend on the outcomes of the earlier choices. $\endgroup$ – MJD Jun 23 '14 at 3:43
4
$\begingroup$

Oddly, a coworker asked me this one last week. The problem is solved; it is not that hard. (I solved it myself in a couple of days, which I mention only as evidence that it is not as hard as it seems.) While investigating it, I looked up the sequence $1, 10, 276, 14736$ in OEIS, which was a bit of a spoiler, because it mentioned "hundred prisoners problem", so I knew I was on the right track.

One reference is Winkler's paper "Seven Puzzles You Think You Must Not Have Heard Correctly".

Once you have guessed the strategy, it is not hard to show that it succeeds with probability close to $$1-\ln 2 \approx 30.7\%.$$ The paper

Eugene Curtin and Max Warshauer, "The locker puzzle", The Mathematical Intelligencer, Volume 28, Number 1 (March 2006), pages 28–31.

shows that this strategy is in fact optimal. User ShreevatsaR of this site wrote a blog post that sketches a proof of optimality, and this old MO thread also discusses the optimality of the optimal strategy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.