Sharing a Secret: Locks and Keys
Five people want to store a secret document in a safe. The rule is simple: any group of 3 or more people should be able to open the safe together, but no group of 2 (or fewer) people should ever be able to open it alone.
To enforce this, they decide to put multiple locks on the safe -- every single lock must be opened to access it. Each lock can have multiple copies of its key distributed to different people, but each physical key only opens one lock.
- What is the minimum number of locks required?
- How many keys will each person carry?
Hints
- Focus on the failure condition: a pair of people fails to open the safe if and only if there is at least one lock for which neither of them has a key.
- For each specific 2-person subset, argue that a dedicated lock is required -- one that blocks exactly that pair and no one else.
- Count the number of 2-person subsets of 5 people using $\binom{5}{2}$, then use symmetry to compute the keys per person from the total key count.
Worked Solution
How to Think About It: A threshold ($3$-of-$5$) secret-sharing puzzle. The pivotal reframing: a group *fails* to open the safe iff there is some lock none of them holds a key to. So the design constraint is dual -- for every forbidden set (each pair) there must exist a dedicated lock that exactly that pair cannot open, while all 3 outsiders can. The heuristic is 'one obstruction per forbidden coalition': count the coalitions you must block, and that lower-bounds the locks. Then verify the natural construction meets it with equality.
Quick Estimate: The maximal groups that must still be *denied* are the 2-person groups (any 3+ must succeed). Each such pair needs its own private lock -- a lock keyed to the *other* 3 people. So locks $=$ number of pairs $=\binom{5}{2}=10$. For keys per person, flip the view: person $P$ holds a key to a lock iff $P$ is one of the 3 outsiders, i.e. iff $P$ is *not* in that lock's blocked pair. The pairs not containing $P$ number $\binom{4}{2}=6$. So each person carries $6$ keys. Sanity by double counting: $10$ locks $\times 3$ keys each $=30$ keys, shared over $5$ people $=6$ each -- consistent.
Approach: One lock per 2-person coalition; key it to the complementary trio.
Formal Solution:
Part 1 -- minimum locks. Label people $1,\dots,5$. Take any pair $\{i,j\}$. For them to be blocked, some lock must be unopenable by both -- so *neither* $i$ nor $j$ holds its key; the 3 remaining people must all hold it (else a valid 3-group containing them could be blocked).
Distinct pairs need distinct locks: suppose one lock blocked both $\{1,2\}$ and $\{1,3\}$. Then person $1$ (in both) holds no key to it, so the legitimate majority $\{1,4,5\}$ could not open that lock -- contradiction. Hence each of the $\binom{5}{2}=10$ pairs demands its own lock, giving $$\boxed{10\text{ locks}}.$$ This is achievable: for pair $\{i,j\}$ create one lock and give its key to the other three people. Any 3-group opens every lock (for each lock, at most 2 of its 3 keyholders can be absent, so at least one is present), while any pair is blocked by its own lock. So $10$ is exactly the minimum.
Part 2 -- keys per person. Each lock is keyed to the 3 people outside its blocked pair, so it distributes $3$ keys; with $10$ locks that is $30$ key-copies. By symmetry each person holds $$\frac{30}{5}=6\text{ keys}.$$ Equivalently, person $P$ holds the key to lock $\{i,j\}$ precisely when $P\notin\{i,j\}$, and the number of pairs avoiding $P$ is $\binom{4}{2}=6$. Both counts agree: $\boxed{6\text{ keys per person}}$.
Answer: Minimum $\boxed{10}$ locks; each person carries $\boxed{6}$ keys.
Intuition
This problem is a clean example of threshold secret sharing -- a fundamental idea in cryptography and distributed systems. The structure forces you to think about what it means for access to be 'just barely blocked': every unauthorized coalition must be missing a key to at least one lock. The insight is that distinct unauthorized coalitions (pairs) must each be handled by a distinct lock, which turns the problem into a counting exercise.
In practice, this construction generalizes to any $(k, n)$ threshold: $n$ people, any $k$ can open the safe, any $k-1$ cannot. The minimum locks required is $\binom{n}{n-k+1}$ -- one for each $(n-k+1)$-person 'blocked' coalition -- and the keys per person is $\binom{n-1}{k-1}$. For $(3,5)$: $\binom{5}{2} = 10$ locks and $\binom{4}{2} = 6$ keys per person, matching our answer. The common mistake is to try to be 'efficient' by sharing a lock between two pairs -- but that always ends up blocking some valid majority group.