返回题库

11 人多数开锁

Screwy Pirates

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

题目详情

有 11 名海盗把宝藏放在一个带多把锁的保险箱里。

他们希望：

  • 任意多数（至少 6 人）都能打开所有锁；
  • 任意 5 人或更少都至少打不开一把锁。

每把锁可配多把钥匙，每人可持多把钥匙，每把钥匙只能开一把锁。

问：最少需要多少把锁？每个海盗需要带多少把钥匙？

There are now 11 pirates. They put all treasure into a single safe with multiple locks. They want any majority (at least 6 pirates) to be able to open all the locks, but any group of 5 or fewer pirates to fail to open at least one lock. Each lock can have multiple keys, but each pirate can hold multiple keys, and each key opens exactly one lock. What is the smallest number of locks needed, and how many keys does each pirate carry?

解析

对任意一个 5 人子集，都必须存在一把锁不给这 5 人钥匙，而给剩余 6 人钥匙。

5 人子集数量为 (115)=462\binom{11}{5}=462，因此至少需要 462 把锁。

每把锁给 6 把钥匙，总钥匙数为 462⋅6462\cdot 6，平均到 11 人，每人钥匙数为

462⋅611=252.\frac{462\cdot 6}{11}=252.

Original Explanation

For each subset of 5 pirates, there must exist a lock to which none of those 5 pirates has a key, while the other 6 pirates do. The number of 5-pirate subsets is

(115)  =  462.\binom{11}{5} \;=\; 462.

Hence, we need at least 462 locks. Each such lock is assigned to exactly those 6 pirates not in the chosen subset. Therefore, each pirate receives

462×611  =  252\frac{462 \times 6}{11} \;=\; 252

keys in total.