BrainTeaser BasicCountingPrinciple Difficult

Problem - 4414

$\textbf{Key Set}$

A sensitive location is protected by a door with multiple locks. This place has $11$ workers. The regulation requires that any combination of six workers can open all the locks, but any combination of five cannot. What is the minimal number of locks and how to distribute the keys?


$\textbf{Answer}$

$\binom{11}{5}$

$\textbf{Analysis}$

Because there are $\binom{11}{5}$ distinct combinations of $5$-worker groups and none of them can open the door, therefore there must be at least $\boxed{\binom{11}{5}}$ locks.

Meanwhile, having $\binom{11}{5}$ locks indeed can meet the requirements. To show this, mark these locks as $L{a, b, c, d, e}$, respectively, where $\{a,\ b,\ c,\ d,\ e\}$ is any $5$-element subset of $\{1,\ 2,\ \cdots,\ 11\}$, and distribute the keys to lock $L_{a,b,c,d,e}$ to the $6$ workers other than $a$, $b$, $c$, $d$, $e$. Then, any combination of five workers will have one lock none of them has the key, but all of the remaining workers have the key. This arrangement will satisfy the requirement.

report an error