# 密码锁问题

## 题目

一把密码锁需要若干个密码同时输入才能打开。现有 $m$ 个人，每个人只知道其中部分密码。要求当且仅当其中 $n$ 个人同时在场才能打开锁。求密码的设计方案。

显然，$m \ge n$.

方案应包括以下输出：

:$K$: 密码的总个数，当然越少越好
:$P$: 每个人掌握的密码数

以及每个人掌握的密码的组合，每个密码可用 $0$ 到 $K - 1$ 的整数分别代表。

## 方案设计

用 $\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}$ 导出，方法如下：

1. 取 $\Bbb{A}_{m - 1}^{n - 1}$ 时每个人的密码组合作为 $m - 1$ 个人密码组合的一部分
1. 取 $\Bbb{A}_{m - 1}^{n - 1}$ 时每个人的密码组合作为这 $m - 1$ 个人密码组合的另一部分。当然，这里的密码与以上用过的密码不能相同，不妨从 $K_{m - 1}^{n - 1}$ 起编号
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$
1. 将 $\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$ 时：

$$
\begin{split}
P_m^n &= P_{m - 1}^{n - 1} + P_{m - 1}^n \\
      &= P_n^{n - 1} + P\_n^n \\
      &= K_{n - 1}^{n - 1} + 1 \\
      &= n \\
      &= K_{m - 1}^n
\end{split}
$$

> $m > n + 1$ 时：

$$
\begin{split}
P_m^n &= P_{m - 1}^{n - 1} + P_{m - 1}^n \\
      &= K_{m - 2}^{n - 1} + K_{m - 2}^n \\
      &= K_{m - 1}^n
\end{split}
$$

> 成立。

成立。

列一下 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   |

没错，这是一个杨辉三角。因此有：

$$
\begin{split}
                P_m^n &= \frac {(m - 1)!} {(m - n)! (n - 1)!} \\
                K_m^n &= \frac {m!} {(m - n + 1)! (n - 1)!} \\
\frac {P_m^n} {K_m^n} &= \frac {m - n + 1} m
\end{split}
$$

:::{seealso}
[C++ Code](https://github.com/lasyard/coding-cpp-cmake/blob/main/quiz/coded_lock.cpp)
:::