并/交可数性、无限图、可数性证明、不动点、Kolmogorov 复杂性、计数、Fermat 手链

(a) Always countable（总是可数）。\(X \cap Y\) 是 \(X\) 的子集，而 \(X\) 是可数集，因此 \(X \cap Y\) 也是可数集。

(b) Always uncountable（总是不可数）。\(X \cup Y\) 是 \(Y\) 的母集，而 \(Y\) 是不可数集，因此 \(X \cup Y\) 也是不可数集。

(c) Always uncountable（总是不可数）。任取 \(X\) 中的一个元素 \(x\)。\(A_x\) 是不可数集。因此 \(\bigcup_{i\in X} A_i\)（\(A_x\) 的母集）也是不可数集。

(d) Sometimes countable, sometimes uncountable（有时可数，有时不可数）。

• 可数情形：当 \(A_i\) 两两不相交时，交集为空集，从而是可数的。例如，令 \(X = \mathbb{N}\)，\(A_i = \{i\} \times \mathbb{R} = \{(i, x) \mid x \in \mathbb{R}\}\)。此时 \(\bigcap_{i\in X} A_i = \emptyset\)。

• 不可数情形：当所有 \(A_i\) 都相同时，交集是不可数的。例如，令 \(X = \mathbb{N}\)，对所有 \(i\) 令 \(A_i = \mathbb{R}\)。此时 \(\bigcap_{i\in X} A_i = \mathbb{R}\)，是不可数集。

(e) Sometimes countable, sometimes uncountable（有时可数，有时不可数）。

• 可数情形：令所有 \(B_i\) 相同。例如，令 \(Y = \mathbb{R}\)，\(B_i = \mathbb{N}\)。此时 \(\bigcup_{i\in Y} B_i = \mathbb{N}\)，是可数集。

• 不可数情形：令 \(Y = \mathbb{R}\)，\(B_i = \{i\}\)。此时 \(\bigcup_{i\in Y} B_i = \mathbb{R}\)，是不可数集。

(f) Always countable（总是可数）。任取 \(Y\) 中的一个元素 \(y\)。\(B_y\) 是可数集。因此 \(\bigcap_{i\in Y} B_i\)（\(B_y\) 的子集）也是可数集。

(a) 可数（Countable）。令 \(A\) 为我们计数的图集合。令 \(A_k\) 为所有满足 \(V \subseteq \{1, 2, \ldots, k\}\) 的图 \(G = (V, E)\) 构成的集合。注意 \(A = A_1 \cup A_2 \cup A_3 \cup \cdots\)。

每个特定的 \(A_k\) 是有限集，因为在具有 \(k\) 个顶点的图中，只有有限多条可能的边可以被包含。这意味着我们可以通过枚举每个 \(A_k\) 来枚举 \(A\)；因此 \(A\) 是可数集。

(b) 不可数（Uncountable）。

回顾课堂知识：无限长的二进制串集合是不可数无限的。我们将从该集合向给定的图集合构造一个单射。

首先注意到，由于顶点集是可数的，我们可以用正整数标记它们：\(V = \{v_i \mid i \in \{1, 2, 3, \ldots\}\}\)。现在考虑一个无限二进制串 \(s = b_1 b_2 b_3 \cdots \in \{0,1\}^\infty\)，其中 \(b_i \in \{0,1\}\) 是串的第 \(i\) 位。我们可以用如下方式编码第一位：用顶点 \(v_1, v_2, \ldots, v_{b_1+2}\) 构造一个长度为 \(b_1 + 3\) 的简单环（即构造链 \(v_1 \to v_2 \to \cdots \to v_{b_1+2} \to v_1\)）。类似地，用顶点 \(v_{b_1+3}, v_{b_1+4}, \ldots, v_{b_1+b_2+5}\) 构造一个长度为 \(b_2 + 3\) 的简单环来编码 \(b_2\)。以此类推，我们通过用顶点 \(v_{f_s(i)}\) 到 \(v_{f_s(i)+b_i+1}\) 构造一个长度为 \(b_i + 3\) 的简单环来编码第 \(i\) 位，其中 \(f_s(i) = 3(i-1) + \sum_{j=1}^{i-1} b_j\)。\(V\) 中的每个顶点恰好属于这样一个环，因此每个顶点的度都恰好为 2。

为了说明这是一个单射，考虑两个不同的串 \(s = b_1 b_2 b_3 \cdots\) 和 \(s' = b'_1 b'_2 b'_3 \cdots\)，它们在第 \(i\) 位首次不同。根据构造，前 \(f_s(i-1)\) 个顶点形成的子图在两个图中是相同的。然而，接下来的 \(b_i + 3\) 个顶点在 \(s\) 对应的图中属于一个长度为 \(b_i + 3\) 的简单环，而在 \(s'\) 对应的图中接下来的 \(b'_i + 3\) 个顶点属于一个长度为 \(b'_i + 3\) 的简单环，其中 \(b'_i + 3 \neq b_i + 3\)。这对所有 \(s, s' \in \{0,1\}^\infty\) 成立，因此我们得到了一个单射。

(c) 不可数（Uncountable）。首先证明：若 \(f\) 是图同构，则 \(v\) 与 \(f(v)\) 的度相同。假设它们度不同。那么要么存在 \(v\) 的某个邻居 \(w\) 使得 \((f(v), f(w)) \notin E'\)，要么存在 \(f(v)\) 的某个邻居 \(w'\) 使得 \((v, f^{-1}(w')) \notin E\)。无论哪种情况，\(f\) 都不是同构。

我们将从无限比特串集合向无限树集合构造一个单射。具体来说，我们通过在无限线图 \(G = (V, E)\) 上添加叶子来构造这些树，其中 \(V = \{v_0, v_1, v_2, \ldots\}\)，\(E = \{(v_i, v_{i+1}) \mid i \in \mathbb{N}\}\)。

对每个比特串 \(b\)，其中 \(b(i)\) 是 \(b\) 的第 \(i\) 位，如下构造无限树 \(G_b\)。首先给 \(v_0\) 添加 10 个叶子。然后对每个 \(i\)，若 \(b(i) = 1\)，则给 \(v_i\) 添加一个叶子。我们将 \(G_b\) 中的每个 \(v_i\) 记为 \(v^b_i\)。

显然，所得的图是一棵树，因为添加叶子永远不会使图断开或产生环。该图也有可数个顶点，因为我们只添加了可数个顶点。

为了说明这个构造是从无限比特串集合到无限树集合的单射，我们首先注意到任何图同构必须将顶点映射到相同度的顶点。现在假设矛盾地，\(b \neq b'\) 但存在一个同构 \(f\) 从 \(G_b\) 到 \(G_{b'}\)。根据构造，每个 \(G_b\) 恰好有一个度 \(\geq 10\) 的顶点。因此，从 \(G_b\) 的顶点到 \(G_{b'}\) 的顶点的任何同构必须将 \(v^b_0\) 映射到 \(v^{b'}_0\)。因此，对每个 \(i\)，它必须将 \(v^b_i\) 映射到 \(v^{b'}_i\)。然而，由于存在某个 \(i\) 使得 \(b(i) \neq b'(i)\)，因此存在某个 \(i\) 使得 \(f(v^b_i)\) 与 \(v^{b'}_i\) 的度不同。

(a) 可数（Countable）。每个圆盘内部必须至少包含一个有理点（即横纵坐标都属于 \(\mathbb{Q}\) 的 \((x, y)\) 坐标点）。由于任意两个圆盘都不重叠，圆盘集合的基数不会超过 \(\mathbb{Q} \times \mathbb{Q}\) 的基数，而 \(\mathbb{Q} \times \mathbb{Q}\) 是可数集。

(b) 可能不可数（Possibly uncountable）。考虑圆 \(C_r = \{(x, y) \in \mathbb{R}^2 : x^2 + y^2 = r\}\)，其中 \(r \in \mathbb{R}\)。当 \(r_1 \neq r_2\) 时，\(C_{r_1}\) 与 \(C_{r_2}\) 不重叠，而这样的圆有不可数个（每个实数对应一个）。

(c) 不可数（Uncountable）。假设存在一个双射，将 \(\mathbb{N}\) 映到所有增函数 \(\mathbb{N} \to \mathbb{N}\) 的集合： \[0 \mapsto (f_0(0), f_0(1), f_0(2), \ldots)\] \[1 \mapsto (f_1(0), f_1(1), f_1(2), \ldots)\] \[2 \mapsto (f_2(0), f_2(1), f_2(2), \ldots)\] \[\vdots\]

我们将用对角线论证法证明存在一个不在上述列表中的函数 \(f\)。定义 \[f(n) = 1 + \sum_{i=0}^{n} f_i(n).\]

首先证明 \(f\) 是增函数。事实上，若 \(m \leq n\)，则 \[f(m) = 1 + \sum_{i=0}^{m} f_i(m) \leq 1 + \sum_{i=0}^{n} f_i(m) \leq 1 + \sum_{i=0}^{n} f_i(n) = f(n).\] 第一个不等式是因为每个函数值非负；第二个不等式是因为 \(f_i\) 都是增函数。

为证明 \(f\) 不在列表中，注意 \[f(n) = 1 + \sum_{i=0}^{n} f_i(n) \geq 1 + f_n(n) > f_n(n).\] 由于对每个 \(n \in \mathbb{N}\) 都有 \(f(n) > f_n(n)\)，\(f\) 不可能是列表中的任何一个函数。因此，增函数 \(f : \mathbb{N} \to \mathbb{N}\) 的集合是不可数的。

(d) 可数（Countable）。对任意满足 \(f(0) = n\) 的函数，考虑函数值下降的下标个数：即满足 \(f(i) < f(i-1)\) 的 \(i\) 构成的集合。\(f\) 的值域是 \(\mathbb{N}\) 的子集，因此由良序原理（well-ordering principle）可知必存在最小元，记为 \(a\)。那么至多有 \(n - a\) 个转换点（transition points）。我们可以将任意满足 \(f(0) = n\) 的函数与一个记录函数值下降位置的「字」（word）建立双射。因此，减函数 \(\mathbb{N} \to \mathbb{N}\) 的集合与可数字母表上的有限比特串集合具有相同的基数，而后者是可数的。因此，所有减函数的集合是可数的。

(a) 我们可以通过从停机问题归约来证明这一点。假设存在某个程序 FixedPoint(F) 能解决不动点问题。我们可以如下定义 TestHalt(F, x)：

def TestHalt(F, x):
  def F'(y):
    F(x)
    return y
  return FixedPoint(F')

如果 \(F(x)\) 停机，则 \(F'(y)\) 总是返回 \(y\)，因此每个输入都是不动点。另一方面，如果 \(F(x)\) 不停机，则 \(F'\) 对任何输入 \(y\) 都不会返回任何值，因此不可能有不动点。因此，我们对 TestHalt 的定义必须总是有效，这是一个矛盾；这告诉我们 FixedPoint 不可能存在。

(b) 如果这个问题可解，则 (a) 中的问题可解：如果 (b) 中的程序返回 "Null"，我们就输出「否」（\(F\) 没有不动点），否则输出「是」。

(c) 直觉是所有输入的集合与 \(\mathbb{N}\) 之间存在双射，因此我们可以将 (b) 中的问题归约到这个问题。具体来说，由于所有输入的集合是可数无限的，存在一个双射函数 \(g\)，将自然数 \(n\) 映射到唯一的输入字符串 \(g(n)\)。此外，我们可以稍微扩展 \(g\) 的定义，使得 \(g(\text{"Null"}) = \text{"Null"}\)，从而它仍然是双射。

考虑以下程序：

def FindFixedPoint(F):
  def F'(n):
    if n not in N:
      error
    x = g(n)
    if F(x) == x:
      return n
    else:
      return n + 1
  return g(FindFixedPointInN(F'))

由于 \(g\) 是双射，\(g^{-1}\) 存在，且若 \(g(n) = x\)，则 \(n = g^{-1}(x)\)。如果存在某个 \(x\) 使得 \(F(x) = x\)，则 \(n = g^{-1}(x)\) 将是 \(F'\) 的一个不动点。因此，如果 \(F\) 有不动点，FindFixedPointInN(F') 将返回某个 \(n\)，其中 \(g(n)\) 是 \(F\) 的不动点。

另一方面，如果对所有输入 \(x\) 都有 \(F(x) \neq x\)，则对所有 \(n\) 都有 \(F'(n) = n + 1 \neq n\)，这意味着 \(F'\) 也没有不动点。因此，我们的程序解决了 (b) 中的问题，而 (b) 已被证明是不可计算的。这意味着这个问题也是不可计算的。

(a) 由于字符数量有限，因此在 280 个字符以内可定义的正整数只有有限个。因此，必然存在不能在 280 个字符内定义的正整数，而由良序原理可知，该集合中存在最小元。然而，语句「不能在 280 个字符以内定义的最小正整数」仅用 67 个字符（含空格）就定义了这个最小整数。因此，我们得到了一个悖论（称为 Berry 悖论，Berry Paradox）。

(b) 长度为 \(n\) 的串的数量是 \(2^n\)。长度小于 \(n\) 的串的数量是 \(\sum_{i=0}^{n-1} 2^i\)。我们知道这个和等于 \(2^n - 1\)（回忆二进制的原理）。因此，长度小于 \(n\) 的串集合的基数小于长度为 \(n\) 的串集合的基数。因此，必然存在长度为 \(n\) 且不能被压缩到更短串的串。

(c) 我们将这样的程序编写如下：

def P(n):
  complex_string = "0" * n
  for j in range(1, 2 ** n):
    # 将 j 转换为二进制的 Python 代码
    bit_string = "{0:b}".format(j)
    # 长度现在应为 n 个字符
    bit_string = (n - len(bit_string)) * "0" + bit_string
    if K(bit_string) > K(complex_string):
      complex_string = bit_string
  return complex_string

这个程序本质上是遍历所有长度为 \(n\) 的比特串，跟踪复杂度最高的串。

(d) 我们知道，对每个 \(n\) 的值，必然存在一个不可压缩的串。这样的不可压缩串的柯尔莫哥洛夫复杂度大于或等于其实际长度。因此，我们的程序 \(P\) 必须返回一个不可压缩的串。然而，假设我们选择大小 \(n_k\) 使得 \(n_k \gg m\)。我们的程序 \(P(n_k)\) 将输出一个长度为 \(n_k\) 的串 \(x\)，该串不可压缩，即 \(K(x) \geq n_k\)。然而，我们设计了一个用少于 \(n_k\) 比特就能输出 \(x\) 的程序。这是一个矛盾。因此，\(K\) 不可能存在。

(a) \(\displaystyle\binom{n+k}{k}\)

(b) 首位有 3 种选择。对之后的每位，由于不能等于前一位，只有 2 种选择。因此为 \(3 \cdot 2^{18}\)。

(c) i. 从 52 张牌中选 13 张，即 \(\displaystyle\binom{52}{13}\)。 ii. 从 48 张非 A 牌中选 13 张，即 \(\displaystyle\binom{48}{13}\)。 iii. 必须包含四张 A，因此从 48 张非 A 牌中选剩下的 9 张，即 \(\displaystyle\binom{48}{9}\)。 iv. 手牌需包含 13 张黑桃中的 4 张，以及 39 张非黑桃中的 9 张，这两个选择相互独立。因此有 \(\displaystyle\binom{13}{4}\binom{39}{9}\) 种方式。

(d) 若考虑 104! 种重排，由于每张牌出现两次，每种不同的重排被重复计数。考虑两副相同牌组的任意一种不同重排，看看它在 104 张牌各不相同的重排中出现多少次。对每一对相同的牌（如两张黑桃 A），它们之间有 2 种互换方式（因为 \(2! = 2\)）。这对 52 对相同牌都成立。因此 104! 将两副相同牌组的实际重排数多计了 \(2^{52}\) 倍。因此，两副相同牌组的实际重排数为 \(\dfrac{104!}{2^{52}}\)。

(e) 解法一：包含 \(k\) 个 1 和 \(99-k\) 个 0 的 99 位比特串有 \(\displaystyle\binom{99}{k}\) 个。我们需要 \(k > 99 - k\)，即 \(k \geq 50\)。因此所求总数为 \(\displaystyle\sum_{k=50}^{99}\binom{99}{k}\)。

该表达式可以进一步简化。由于 \(\displaystyle\binom{99}{k} = \binom{99}{99-k}\)，我们有 \[\sum_{k=50}^{99}\binom{99}{k} = \sum_{k=50}^{99}\binom{99}{99-k} = \sum_{l=0}^{49}\binom{99}{l}\] （代换 \(l = 99 - k\)）。

现在 \(\displaystyle\sum_{k=50}^{99}\binom{99}{k} + \sum_{l=0}^{49}\binom{99}{l} = \sum_{m=0}^{99}\binom{99}{m} = 2^{99}\)。因此 \(\displaystyle\sum_{k=50}^{99}\binom{99}{k} = \frac{1}{2} \cdot 2^{99} = 2^{98}\)。

解法二（对称性）：由于上面的答案如此简洁，必然存在更优雅的方法。因为 99 是奇数，没有哪个 99 位比特串的 0 和 1 数量相等。令 \(A\) 为 1 比 0 多的 99 位比特串集合，\(B\) 为 0 比 1 多的 99 位比特串集合。对任意 \(x \in A\)（1 比 0 多），将 \(x\) 的所有位翻转，得到串 \(y\)（0 比 1 多），即 \(y \in B\)。这个位翻转操作建立了 \(A\) 与 \(B\) 之间的一一对应（双射）。因此 \(|A| = |B|\)。每个 99 位比特串要么在 \(A\) 中，要么在 \(B\) 中，而 99 位比特串共有 \(2^{99}\) 个，因此 \(|A| = |B| = \frac{1}{2} \cdot 2^{99}\)。所求即为 \(|A| = 2^{98}\)。

(f) i. ALABAMA：7 个不同字母的重排数为 \(7!\)。在这个 7 字母单词中，字母 A 重复了 4 次，其他字母各出现一次。因此 \(7!\) 将不同异位词的数量多计了 \(4!\) 倍（即 4 个 A 之间互换的方式数）。因此有 \(\dfrac{7!}{4!}\) 个异位词。 ii. MONTANA：在这个 7 字母单词中，字母 A 和 N 各重复了 2 次，其他字母各出现一次。因此 \(7!\) 将不同异位词的数量多计了 \(2! \times 2!\) 倍（一个 \(2!\) 来自 2 个 A 之间的互换，另一个 \(2!\) 来自 2 个 N 之间的互换）。因此有 \(\dfrac{7!}{(2!)^2}\) 个不同的异位词。

(g) i. 将 CE 视为一个新字母 X，问题转化为 5 个不同字母的重排，即 \(5!\)。 ii. 对称性：令 \(A\) 为所有 C 在 E 左侧的 ABCDEF 重排集合，\(B\) 为所有 C 在 E 右侧的 ABCDEF 重排集合。\(|A \cup B| = 6!\)，\(|A \cap B| = 0\)。通过交换 C 和 E 的位置可建立 \(A\) 与 \(B\) 之间的双射。因此 \(|A| = |B| = \dfrac{6!}{2}\)。

(h) 每个球都有选择去哪个格子的自由。因此每个球有 25 种选择，8 个球可以独立做出选择。因此有 \(25^8\) 种方式。

(i) 由于对每个格子能放多少球没有限制，这就是将 \(k\) 个相同球放入 \(n\) 个可区分格子的经典问题，有 \(\displaystyle\binom{n+k-1}{k}\) 种方式。这里 \(k = 8\)，\(n = 25\)，因此有 \(\displaystyle\binom{32}{8}\) 种方式。

(j) 解法一：由于每个格子必须非空，先往每个格子各放一个球。此时还剩 2 个相同的球要放入 6 个可区分的格子。有两种情况：

• 情况 1：2 个球落入同一格子。有 6 种方式。

• 情况 2：2 个球落入不同格子。有 \(\displaystyle\binom{6}{2}\) 种方式选择哪两个格子。注意不是 \(6 \times 5\)，因为球是相同的，没有顺序。

将两种情况的方式数相加，得到 \(\displaystyle 6 + \binom{6}{2}\) 种方式。

解法二：由于每个格子必须非空，先往每个格子各放一个球。此时还剩 2 个相同的球要放入 6 个可区分的格子。根据课堂知识（参见 Note 10），将 \(k\) 个相同球放入 \(n\) 个可区分格子的方式数为 \(\displaystyle\binom{n+k-1}{k}\)。取 \(k = 2\)，\(n = 6\)，得到 \(\displaystyle\binom{7}{2}\) 种方式。

练习：你能给出将 \(k\) 个相同球放入 \(n\) 个可区分格子且每个格子非空的方式数的表达式吗？

(k) 解法一：将学生从 1 到 20 编号。学生 1 有 19 种选择来确定她的搭档。令 \(i\) 为尚未被分配搭档的学生中编号最小者。那么无论 \(i\) 取何值（特别地，\(i\) 可以是 2 或 3），学生 \(i\) 有 17 种选择来确定她的搭档。下一个尚无搭档的最小编号学生有 15 种选择。以此类推，配对方式数为 \(19 \times 17 \times 15 \times \cdots \times 1 = \prod_{i=1}^{10}(2i - 1)\)。

解法二：将编号 1 到 20 的学生排成一行。共有 \(20!\) 种排列。我们将位置 \(2i-1\) 和 \(2i\) 上的学生配对，\(i\) 从 1 到 10。你应该能看到，\(20!\) 种排列没有遗漏任何可能的配对。然而，它对每种不同的配对重复计数了多次。固定任意一种特定的配对。在这种配对中，第一对在生成它的任何排列中有 10 个位置的自由，第二对有 9 个位置的自由，依此类推。此外，每对内部也有自由度：即在学生配对 \((x, y)\) 中，学生 \(x\) 可以出现在位置 \(2i-1\) 且学生 \(y\) 出现在位置 \(2i\)，反之亦然。这给每对提供了 2 种方式。因此，总共这些自由度导致 \(10! \times 2^{10}\) 个 \(20!\) 中的排列产生这种特定的配对。这对每种不同的配对都成立。因此，\(20!\) 将不同配对数多计了 \(10! \times 2^{10}\) 倍。因此有 \(\dfrac{20!}{10! \cdot 2^{10}}\) 种配对。

解法三：第一步，从 20 名学生中选出一对。有 \(\displaystyle\binom{20}{2}\) 种方式。第二步，从剩下的 18 名学生中选出一对。有 \(\displaystyle\binom{18}{2}\) 种方式。继续这样选对，直到第十步，从剩下的 2 名学生中选出一对。有 \(\displaystyle\binom{2}{2}\) 种方式。将这些相乘，得到 \(\displaystyle\binom{20}{2}\binom{18}{2}\cdots\binom{2}{2}\)。然而，在 20 名学生的任意一种特定配对中，该配对可以通过上述程序以 \(10!\) 种方式生成，具体取决于哪些对在第一、第二、……、第十步被选中。因此，我们必须将上述数字除以 \(10!\) 以得到不同的配对数。因此有 \(\displaystyle\binom{20}{2}\binom{18}{2}\cdots\binom{2}{2}/10!\) 种不同的 20 名学生配对方式。

你可能想自己验证一下，这三种方法产生的整数相同，尽管它们的表达式看起来非常不同。

(l) \(\displaystyle\binom{n+k}{k}\)。这就是将 \(n\) 个不可区分的球放入 \(k+1\) 个可区分格子的问题（星与条）。方程的解与由 \(n\) 个 1 和 \(k\) 个加号组成的序列之间存在双射：\(x_0\) 是第一个加号之前的 1 的个数，\(x_1\) 是第一个和第二个加号之间的 1 的个数，依此类推。关键思想是：如果两个集合之间存在双射，它们的大小必须相同，因此计数其中一个的元素个数就能告诉我们另一个有多少个。注意这与 (a) 的答案完全相同——确保你理解为什么！

(m) \(n - 1\)。这里最容易直接列举解。\(x_0\) 可以取值 \(1, 2, \ldots, n-1\)，这唯一确定了 \(x_1\) 的值。因此有 \(n - 1\) 种方式。但这只是下面更一般问题的一个特例。

(n) \(\displaystyle\binom{(n-(k+1))+k}{k} = \binom{n-1}{k}\)。这就是将 \(n-(k+1)\) 个不可区分的球放入 \(k+1\) 个可区分格子的问题。通过从所有 \(k+1\) 个变量中减去 1，并从所需总数中减去 \(k+1\)，我们将其转化为与前一个问题同形式的问题。一旦得到该问题的解，逆向操作，给所有非负变量加 1，就得到了正变量。

(a) \(n^p\)。对每个珠子，其颜色有 \(n\) 种可能。因此，由第一计数原理，有 \(n^p\) 个不同的序列。

(b) \(n^p - n\)。单色序列有 \(n\) 个。

(c) 由于 \(p\) 是素数，将任何序列旋转少于 \(p\) 位都会产生一个新序列。也就是说，不存在小于 \(p\) 的数 \(x\)，使得将珠子旋转 \(x\) 位后图案看起来相同。因此，每个具有多于一种颜色的图案都可以旋转形成 \(p-1\) 个其他图案。因此，与某个珠序列等价的模式总数为 \(p\)。因此，不等价模式的总数为 \((n^p - n)/p\)。

(d) \((n^p - n)/p\) 必须是整数，因为根据前一部分，它是某个计数对象的数量。因此 \(n^p - n\) 必须能被 \(p\) 整除，即 \(n^p \equiv n \pmod{p}\)，这就是费马小定理。