# Is this perfect matching probability game really open?

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?

• 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.
– MJD
Commented Jun 23, 2014 at 3:43

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.
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