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