7
$\begingroup$

The question is related to the famous locker puzzle:

The director of a prison offers 100 prisoners on death row, which are numbered from 1 to 100, a last chance. In a room there is a cupboard with 100 drawers. The director puts in each drawer the number of exactly one prisoner in random order and closes the drawers afterwards. The prisoners enter the room one after another. Each prisoner may open and look into 50 drawers in any order and the drawers are closed again afterwards. If during this search every prisoner finds his number in one of the drawers, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners have to die. Before the first prisoner enters the room, the prisoners may discuss their strategy, afterwards no communication of any means is possible. What is the best strategy for the prisoners?

I am interested in the modification where the prisoners are only allowed to use a predetermined strategy: each of them must choose the 50 boxes he will open before entering the room.

In this case I believe the optimal strategy is the following one. Divide the prisoners into two groups, say, with numbers 1-50 and 51-100. Each prisoner from the first group should open boxes 1-50, from the second, 51-100.

More generally, if each of $nm$ prisoners is allowed to open $m$ boxes, then the best strategy seems to be the same: divide into groups $1$ to $m$, $m+1$ to $2m$, ... $(n-1)m+1$ to $nm$ and let each prisoner open the boxes with numbers from his group.

This is easily seen to be optimal for $m=2$. Is this so for any $m$? Is there any reference?

$\endgroup$
  • 2
    $\begingroup$ Those poor prisoners are probably going to die then. The probability that they survive would be $\frac{1}{\binom{100}{50}}\approx 9.9\times 10^{-30}$... much worse chances of survival than the original wording of the question, but at least its better than guessing randomly, which is $(\frac{1}{2})^{100}\approx 7.8\times10^{-31}$. $\endgroup$ – JMoravitz Aug 15 '15 at 17:22
  • $\begingroup$ Your intuition seems correct. Intuitively, your strategy is slightly better (but by @JMoravitz comment not much!) than random guessing because random guessing is bound to contain some contradictions e.g. all prisoners might guess only boxes $1-50$, which can clearly never lead to solution. A proof that yours is the best would be nice. Unfortunately I have no reference for you. $\endgroup$ – Colm Bhandal Aug 15 '15 at 17:45
  • $\begingroup$ My intuition is that if prisoner $A$ fails, then prisoner $B$ should want to fail too (or at least have his probability of failing decreased instead of increased), so that the bad outcomes coincide as much as possible. That means the more dependent the probabilities are, the better for the prisoners—dividing them into two groups like you said seems to do exactly that. I wonder if it is possible to formalize the idea, e.g., as some kind of potential function, then a prisoner would change strategy to match a strategy of some other prisoner, perhaps displacing choices of others in the process. $\endgroup$ – dtldarek Aug 16 '15 at 10:21
  • $\begingroup$ I believe that any strategy in which each drawer is looked at the exact same number of times is optimal. Anyone care to prove or disprove ? $\endgroup$ – Manuel Lafond Aug 18 '15 at 1:42
  • $\begingroup$ @Manuel Lafond, no. If all prisoners open boxes 1-50, then the probability is zero. $\endgroup$ – zhoraster Aug 18 '15 at 5:09
4
$\begingroup$

The optimality of the strategy is the consequence of the Bregman-Minc inequality. It says that the permanent of a matrix $A = (a_{i,j})_{i,j=1}^n\in\{0,1\}^{n\times n}$ with $r_i = \sum_{j=1}^n a_{ij}$, $i=1,\dots,n$, satisfies $$ \operatorname{perm} A \le \prod_{i=1}^n (r_i!)^{1/r_i}; $$ the equality holds iff $A$ is, up to permutation of rows and columns, a block diagonal matrix, in which each block is a square all-1 matrix.

Equivalently, the number of perfect matchings in a bipartite graph $G$ on $n$ and $n$ vertices, in which vertices of one part have degrees $r_1, r_2,\dots,r_n$, does not exceed $\prod_{i=1}^n (r_i!)^{1/r_i}$, and the equality holds iff $G$ is a union of complete bipartite graphs.

Now if we draw a bipartite graph of $n$ prisoners and $n$ boxes, vertices connecting prisoners with boxes they open, then the probability to survive is the number of perfect matchings over $n!$. So, in view of the Bregman-Minc inequality, if each prisoner is allowed to open $m$ boxes, then the probability to survive does not exceed $(m!)^{n/m}/n!$, and this bound is attained for the strategy described in the question.

$\endgroup$
  • $\begingroup$ Nice, I didn't suspect it would have such a clean solution $\ddot\smile$ $\endgroup$ – dtldarek Aug 20 '15 at 10:34
  • $\begingroup$ @ dtldarek I didn't suspect either. $\endgroup$ – zhoraster Aug 20 '15 at 16:47

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.