Combinatorics riddle: keys and a safe
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:
- at least 5 crew members would be required to open the safe?
- Any team of 5 crew members could open the safe, but none of the 4 team crew members.
1,2 stands individually of course.
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.
This can easily be generalized, replacing 8 and 4 with a variable each.
Let the set of keys (and locks) be denoted by $K$. Let the set of keys that crew member $i$ doesn't receive be $K_i$.
For distinct indices, Condition 1 states that $K_{ijkl} = K_i \cap K_j \cap K_k \cap K_l \neq \emptyset$ (no 4 crew can open the safe), and condition 2 states that $K_i \cap K_j \cap K_k \cap K_l \cap K_m = \emptyset$ (any 5 crew can open the safe).
Claim: $ K_{ijkl} \cap K_{i'j'k'l'} = \emptyset$ for distinct quadruple sets.
Proof: Suppose not. Then $\{i, j, k, l, i', j', k', l'\}$ is a set with at least 5 distinct elements, contradicting condition 2. $_\square$
Hence, there must be at least $8 \choose 4$ locks.
Claim. $8 \choose 4$ is sufficient.
Proof: Label each of the locks with a distinct quadruple from 1 to 8. To each crew member, give him the key to the lock, if it doesn't have his number on it. Then, any 4 crew members $i, j, k, l$ will not be able to open lock $\{i, j, k, l\}$. Any 5 crew members will be able to open all locks.