6. 密码锁问题
6.1. 题目
一把密码锁需要若干个密码同时输入才能打开。现有 \(m\) 个人，每个人只知道其中部分密码。要求当且仅当其中 \(n\) 个人同时在场才能打开锁。求密码的设计方案。
显然，\(m \ge n\).
方案应包括以下输出：
- \(K\):
密码的总个数，当然越少越好
- \(P\):
每个人掌握的密码数
以及每个人掌握的密码的组合，每个密码可用 \(0\) 到 \(K - 1\) 的整数分别代表。
6.2. 方案设计
用 \(\Bbb{A}_m^n\) 表示方案，\(K_m^n\) 表示此方案中密码的总个数。直觉告诉我们，方案中每个人掌握的密码数是相同的，用 \(P_m^n\) 表示。
采用数学归纳法。
\(n = 1\) 时，显然 \(K_m^1 = 1\), \(P_m^1 = 1\).
\(n = m\) 时，显然 \(K_m^m = m\), \(P_m^m = 1\).
任意 \(\Bbb{A}_m^n\) 将由 \(\Bbb{A}_{m - 1}^{n - 1}\) 和 \(\Bbb{A}_{m - 1}^{n}\) 导出，方法如下：
取 \(\Bbb{A}_{m - 1}^{n - 1}\) 时每个人的密码组合作为 \(m - 1\) 个人密码组合的一部分
取 \(\Bbb{A}_{m - 1}^{n - 1}\) 时每个人的密码组合作为这 \(m - 1\) 个人密码组合的另一部分。当然，这里的密码与以上用过的密码不能相同，不妨从 \(K_{m - 1}^{n - 1}\) 起编号
此时可得 \(K_m^n = K_{m - 1}^{n - 1} + K_{m - 1}^n\), \(P_m^n = P_{m - 1}^{n - 1} + P_{m - 1}^n\)
将 \(\Bbb{A}_{m - 1}^n\) 的所有密码作为第 \(m\) 个人的密码组合
这个编码方案将满足要求，证明如下：
任取 \(n\) 个人，如果全部在前 \(m - 1\) 个人里，那么他们将掌握 \(\Bbb{A}_{m - 1}^{n - 1}\) 和 \(\Bbb{A}_{m - 1}^n\) 的所有密码，也就是 \(\Bbb{A}_m^n\) 的所有密码；如果有 \(n - 1\) 个人在前 \(m - 1\) 里，另一个人是第 \(m\) 个人，他们也能掌握所有密码。
任取 \(n - 1\) 个人，如果全部在前 \(m - 1\) 个人里，那么他们不能掌握 \(\Bbb{A}_{m - 1}^n\) 的全部密码，如果有一个人是第 \(m\) 个人，那么剩下的 \(n - 2\) 个人不能掌握 \(\Bbb{A}_{m - 1}^{n - 1}\) 的全部密码。
当 \(m - 1 \ge n\) 时，似乎应该有 \(P_m^n = K_{m - 1}^n\)，这样才能保证每个人掌握的密码数相同，是这样的吗？
对 \(n\) 应用数学归纳法：
\(n = 1\) 时显然成立。
\(n > 1\) 时，对 \(m\) 应用数学归纳法：
\(m = n + 1\) 时：
\(m > n + 1\) 时：
成立。
成立。
列一下 P 的值：
m |
1 |
2 |
3 |
4 |
5 |
|---|---|---|---|---|---|
1 |
1 |
||||
2 |
1 |
1 |
|||
3 |
1 |
2 |
1 |
||
4 |
1 |
3 |
3 |
1 |
|
5 |
1 |
4 |
6 |
4 |
1 |
没错，这是一个杨辉三角。因此有：
See also