银行保险库的锁与钥匙
Bank Locks
题目详情
某银行有 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 人集合 ,必须存在至少一把锁,使得 中无人持有该锁的钥匙。
为使任意加入第 6 人即可打开,最自然的最小构造是:
- 对每个 5 人集合 配置一把专属锁;
- 该锁的钥匙发给其补集的 6 人(即不在 中的 6 位副总裁)。
这样任意 5 人集合缺少对应那把锁的钥匙而打不开;而任意 6 人集合对任意 5 人集合 至少包含一个不在 的人,因此 6 人集合总能拿到每把锁的钥匙而打开所有锁。
锁的最少数量至少为 5 人集合的数量:
在上述构造中,每把锁需要 6 把钥匙(发给 6 人),所以钥匙总数为
并且每位副总裁拿到的钥匙数量为
英文解析
“Majority” means at least 6 people.
Core constraint: Any number of people less than 6 (that is, any group of 5 people) cannot open the vault, so for each group of 5 people , there must be at least one lock so that no one in holds the key to the lock.
In order to open it by joining any 6th person, the most natural minimal construction is:
- Configure an exclusive lock for each group of 5 ;
- The key to the lock is given to 6 people (i.e. 6 VPs who are not in ).
In this way, any group of 5 people can't open the lock because they lack the key corresponding to that lock; and any group of 6 people contains at least one person who is not in , so the group of 6 people can always get the key of each lock and open all locks.
Minimum number of locks is the number of collections of at least 5 people:
In the above configuration, each lock requires 6 keys (for 6 people), so the total number of keys is
and the number of keys per VP is