Lock Me Out

Solution

Let \(n=11\) people, and let the threshold be \(6\). So we want: \[ \text{any }6\text{ or more people can open the box,} \] but \[ \text{no }5\text{ or fewer people can open it.} \] The standard way to think about this is to assign locks to the forbidden groups. A group of fewer than \(6\) people is blocked if there is at least one lock for which none of them has a key. Since any smaller group is contained in some \(5\)-person group, it is enough to make sure that every \(5\)-person group is blocked. If every \(5\)-person group fails, then every group of size \(<5\) also fails automatically. So the real problem is: \[ \text{for every }5\text{-person subset, there must be some lock that those }5\text{ cannot open.} \] Now take any lock. Suppose the people who do not have its key form a set \(S\). If \(|S| \ge 6\), then those \(6\) people could not open the box, which is forbidden. Therefore every lock can be missing from at most \(5\) people. That observation is the whole lower bound: - every forbidden \(5\)-person group must be excluded from some lock; - a lock can exclude at most one \(5\)-person group, because it can be missing from at most \(5\) people. Hence we need at least as many locks as there are \(5\)-person groups: \[ \binom{11}{5} = 462. \] This lower bound is achievable: For each \(5\)-person subset \(S\), create one lock that is keyed to exactly the other \(6\) people, and not keyed to the people in \(S\). Then: - that particular \(5\)-person group \(S\) cannot open that lock; - any \(6\)-person group can open every lock, because no \(6\)-person group is contained in a \(5\)-person set, so for every lock at least one of the \(6\) has a key. So the minimum number of locks is \[ \binom{11}{5}=462. \] Now count how many keys each person must hold. Fix one person \(P\). They receive a key for every lock whose forbidden \(5\)-set does not contain \(P\). So we count the \(5\)-subsets chosen from the other \(10\) people: \[ \binom{10}{5}=252. \] Thus each person must hold \[ 252 \] keys. You can also check this by averaging total keys: each of the \(462\) locks is opened by exactly \(6\) people, so the total number of keys is \[ 462 \cdot 6 = 2772. \] Dividing equally among \(11\) people gives \[ \frac{2772}{11}=252. \] Therefore the answers are \[ \text{minimum number of locks} = 462, \] and \[ \text{minimum number of keys per person} = 252. \]