2017年03月21日
保险箱问题
这个题是 Zhang xp 老师在课上提出来的，比较有意思，随手记录一下.
\(6\) 个人共用一个保险箱，要求任意 \(3\) 人在一起时都可以打开保险箱，并且最少需要 \(3\) 人才能打开. 请问至少需要多少把锁？每个人至少需要多少把钥匙？
解答：先估计一个锁数量的下界. 由题意，每 \(2\) 个人都不能打开该保险箱， 故每 \(2\) 个人都至少有一把不能打开的锁，且对于不同的两人组，不能打开的锁互不相同，故锁的数量不能少于 \(2\) 元子集的个数，即 \(\binom{6}{2}=15\).
再考虑钥匙的数量. 由于任意 \(3\) 个人都能打开保险箱，故每个人都需要有不包括自己的所有二人组所没有的钥匙，即每个人至少要有 \(\binom{5}{2}=10\) 把钥匙.
以上只是对于下界的估计，要证明其最小性还需构造一组情况来证明最小值可以取到. 构造很容易，不多赘述.