Combinatorics Riddle – Keys and a Safe

combinatoricsrecreational-mathematics

There are 8 crew members, The leading member wants that only a crew of 5 people or more could open a safe he bought, To each member he gave equal amount of keys, and locked the safe with several locks.

What's the minimal number of locks he should put:

  1. at least 5 crew members would be required to open the safe?
  2. Any team of 5 crew members could open the safe, but none of the 4 team crew members.

1,2 stands individually of course.

Best Answer

Consider the general case that $n$ people know certain secrets such that no subset of $k$ of them know all secrets, but any subset of $k+1$ of them do know all secrets. (Here $n=8$, $k=4$, secrets are locks, and knowing a secret is having a key.)

This can be done using $\binom nk$ secrets, each labelled by a different subset of $k$ among the $n$ people, which is the set of people that does not get to know that secret (everyone else does). Then for any subset of $k$ people the corresponding secret will not be known by them, but for any set of $k+1$ people and any secret there is at least one of them who knowns the secret.

To show one cannot do with less secrets, consider any solution to this problem, and the relation between on one hand the $\binom nk$ subsets of $k$ people and on the other hand the secrets, defined by none of those people knowing the secret. This relation is "one to at least one": it is required that any set of $k$ people not know at least one secret, and if two different subsets of $k$ people do not know the same secret, then the union of those subsets, which contains at least $k+1$ people would not know that secret, and hence not all secrets, which is against the requirement. The relation is in fact a surjective map from secrets to $k$-subsets, so there are al least $\binom nk$ secrets.

Related Question