返回题库

银行保险库的锁与钥匙

Bank Locks

专题
Brainteaser / 脑筋急转弯
难度
L4

题目详情

某银行有 11 位副总裁。银行希望用“锁 + 钥匙”系统保护金库，使得只有当多数副总裁到场时（即能把所有锁都打开时）才能进入金库。

问：要实现这一点，最少需要多少把锁和多少把钥匙？

There are 11 vice presidents in a bank. The bank wants to secure its vault with a system of locks and keys such that the only way the vault can be accessed (i.e., all locks opened) is when a majority of the vice presidents are present. What is the minimum number of locks and keys required to achieve this?

解析

“多数”指至少 6 人。

核心约束：任意少于 6 人（即任意 5 人集合）都不能打开金库，因此对每个 5 人集合 SS，必须存在至少一把锁，使得 SS 中无人持有该锁的钥匙。

为使任意加入第 6 人即可打开，最自然的最小构造是：

  • 对每个 5 人集合 SS 配置一把专属锁；
  • 该锁的钥匙发给其补集的 6 人（即不在 SS 中的 6 位副总裁）。

这样任意 5 人集合缺少对应那把锁的钥匙而打不开；而任意 6 人集合对任意 5 人集合 SS 至少包含一个不在 SS 的人，因此 6 人集合总能拿到每把锁的钥匙而打开所有锁。

锁的最少数量至少为 5 人集合的数量：

(115)=462 把锁.\boxed{\binom{11}{5}=462\text{ 把锁}}.

在上述构造中，每把锁需要 6 把钥匙（发给 6 人），所以钥匙总数为

462×6=2772 把钥匙.\boxed{462\times 6=2772\text{ 把钥匙}}.

并且每位副总裁拿到的钥匙数量为

(105)=252.\binom{10}{5}=252.