6
$\begingroup$

Eleven scientists want to have a cabinet built where they will keep some top secret work. They want multiple locks installed, with keys distributed in such a way that if any six scientists are present then they can open all the locks, but if only five are present then they cannot open all the locks. What is the minimum number of locks on the cabinet that would satisfy these conditions?

$\endgroup$
2
$\begingroup$

Let me show it in the general case as the numbers do not matter much.

We have a safe and $S$ scientists, we want $M$ scientists to not be able to open the safe but more then $M$ scientists to be able to open it. How many locks do we need to put on the safe?

Given a set of $M$ scientists out of the $S$ scientists (we call it an $M$-subset), they are missing a key for some lock.

Moreover two such distinct subsets have a scientist not common to both and thus their union has more then $M$ scientists. If two such $M$-subsets are missing the same key then they're union is missing that key, the union has more then $M$ scientists and thus we have a contradiction.

We define a multimap as follows, for each lock we define its preimage to be the $M$-subset which is missing a key for that lock, as described above there cannot be more then one M-subset missing that key (A priori we may have locks which no $M$-subset is missing a key for, so nothing will map to them). Now if some M-subset maps to more then one lock then we can throw away all but one lock, the M-subset will still not be able to open the safe because he is missing a lock. So we end up with an injection from the collection of $M$-subsets to the set of locks. Thus we have at least $N=\binom{S}{M}$ locks.

Now we ask if we need more locks then this. Suppose there are more then $N$ locks. WLOG assume our injection from above maps to the first $N$ locks labeled $1$ to $N$. So each $M$-subset is missing a key for one of the first $N$ locks. Now consider the $(N+1)$-th lock which we call $L$, consider the collection $\mathcal{C}$ of $M$-subsets not having the key for $L$.

Imagine we throw away lock $L$ and all its keys. Any subset of the scientists which could open the safe before can still open it as we just removed a lock. The $M$-subsets still cannot open the safe because they are missing some key from the first N keys. Thus the $(N+1)$-th key is redundant, By a similar argument any lock labeled with a number > $N$ is redundant.

Thus $\binom{S}{M}$ is the minimum sufficient number of locks.

In the case you mentioned we have $S=11$ and $M=5$.
Thus number of locks we need is $\binom{11}{5} = \frac{11!}{5!6!}=462$

$\endgroup$
  • 1
    $\begingroup$ Hi, I wrote how you would construct the injection. This gives you a map from the M-subsets to which key they do not have, to see which keys each scientist has, you need to look at all M-subsets which include this scientist and each of these gives you a key the scientist does not have. So you could in fact construct from this how the sets of keys for each scientist looks. In general for a scientist you have $\binom{S-1}{M-1}$ M-subsets which include him, this gives you the number of keys he does not have. Subtract this from the total number of keys to see how many keys he has. $\endgroup$ – fiftyeight Nov 26 '13 at 8:21
4
$\begingroup$

I thought fiftyeight has a great and rigorous answer.

However, I think there is a shorter explanation/proof:

Given S #scientists and M size of subset - Since each subset of size M can't open all the locks, there should be just one lock (to impose minimality) that each such subset can't open. So we have a one-to-one / invertible mapping between subsets of size M and the locks. Number of subsets of size M is ${S \choose M}$. So the cardinality of set of locks is also ${S \choose M}$.

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