8.8　习题解答Solutions to exercises

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

习题 1

证明与命题 8.3 的证明类似。固定一个落在 \(r_a\) 个区组里的点 \(a\)，并清点所有形如 \((B,c)\) 的有序对，其中 \(a\) 与 \(c\) 是区组 \(B\) 的两个点。于是，用与上述证明相同的论证，得到 \(\lambda(v-1)=r_a(k-1)\)，因此 \(r_a=\lambda(v-1)/k\)，它与 \(a\) 的选取无关。

1. 固定一个点 \(a\)，设它落在 \(r_a\) 个区组中。我们清点这样的有序对 \((B,c)\)：区组 \(B\) 同时含有 \(a\) 和另一个点 \(c\)（\(c\neq a\)）。
2. 第一种数法（按点 \(c\) 分类）。除 \(a\) 之外共有 \(v-1\) 个点。对每一个这样的 \(c\)，由“平衡”，\(a\) 与 \(c\) 恰好同时出现在 \(\lambda\) 个区组里，于是与 \(c\) 配对的有序对有 \(\lambda\) 个。合计 \[\#\{(B,c)\}=\lambda(v-1).\]
3. 第二种数法（按区组 \(B\) 分类）。含 \(a\) 的区组共有 \(r_a\) 个。每个这样的区组里除 \(a\) 外还有 \(k-1\) 个点，每个都能充当 \(c\)。于是 \[\#\{(B,c)\}=r_a(k-1).\]
4. 同一堆对子的两种数法必相等： \[\lambda(v-1)=r_a(k-1)\ \Longrightarrow\ r_a=\frac{\lambda(v-1)}{k-1}.\] （注意原书印作 \(\lambda(v-1)/k\) 是笔误，正确的分母是 \(k-1\)。）等式右边完全不含 \(a\)，所以无论取哪个点，落在的区组数都一样，记为 \(r\)。这就证明了设计是正则的。♦

习题 2

不能。由上一题的结果，这样的设计也会是正则的，因而 \(\lambda(v-1)=r(k-1)\) 成立。由于 \(r\) 整除 \(v\)，所以 \(r\) 与 \(v-1\) 互素，于是 \(\lambda\) 必须是 \(r\) 的倍数。这是不可能的，因为 \(\lambda

1. 由习题 1，设计是正则的，故 \(\lambda(v-1)=r(k-1)\)。
2. 题设 \(r\mid v\)，即 \(v=r\cdot m\)。于是 \(v-1=rm-1\)，它除以 \(r\) 余 \(-1\)，即 \(\gcd(r,\,v-1)=\gcd(r,-1)=1\)。所以 \(r\) 与 \(v-1\) 互素。
3. 把这条用到等式上：\(r\mid \lambda(v-1)\)（因为右边 \(r(k-1)\) 是 \(r\) 的倍数，左边也得是）。但 \(r\) 与 \(v-1\) 互素，所以 \(r\) 必须整除另一因子 \(\lambda\)，即 \(\lambda\) 是 \(r\) 的倍数。
4. 最小的正倍数已经是 \(r\) 本身，故 \(\lambda\ge r\)。这与题设 \(\lambda♦

习题 3

矩阵 \(MM^{T}\) 的 \((i,j)\) 元是 \(M\) 的第 \(i\) 行与第 \(j\) 行的点积（dot product）。因此当 \(i\neq j\) 时，这个元素等于 \(\lambda\)，因为这正是同时包含 \(a_i\) 与 \(a_j\) 的区组个数；当 \(i=j\) 时，该元素就是包含 \(a_i\) 的区组个数，即 \(r\)。事实上，习题 1 的解答表明 \(F\) 是正则的。于是我们得到

1. 关联矩阵 \(M\) 的第 \(i\) 行是点 \(a_i\) 的“出席表”：第 \(t\) 个分量为 \(1\) 表示 \(a_i\) 在第 \(t\) 个区组里，否则为 \(0\)。
2. \(MM^{T}\) 的 \((i,j)\) 元 \(=\sum_t M_{it}M_{jt}\)。乘积 \(M_{it}M_{jt}=1\) 当且仅当第 \(t\) 个区组同时含 \(a_i\) 与 \(a_j\)，否则为 \(0\)。所以这个和就是“同时含 \(a_i,a_j\) 的区组数”。
3. 对角元（\(i=j\)）：条件变成“含 \(a_i\) 的区组数”\(=r\)（由习题 1，正则）。
4. 非对角元（\(i\neq j\)）：就是“同时含 \(a_i,a_j\) 的区组数”\(=\lambda\)（平衡）。
5. 把对角全填 \(r\)、非对角全填 \(\lambda\)：可写成“全部填 \(\lambda\)（即 \(\lambda J_v\)），再把对角各补上 \(r-\lambda\)（即 \((r-\lambda)I_v\)）”，得到 (8.8)。♦

习题 4

这可由上一题末尾得到的 (8.8) 推出。事实上，\(J_v\) 有 \(v-1\) 个等于 \(0\) 的特征值（eigenvalue），因为它的秩（rank，线性无关行的个数）为 \(1\)。它最后一个特征值是 \(\lambda v\)，这是因为一个矩阵全部特征值之和等于它的迹（trace），本例中迹为 \(\lambda v\)。另一方面，\((r-\lambda)I_v\) 是单位矩阵的常数倍，所以它所有特征值都等于 \(r-\lambda\)。最后，若向量 \(x\) 是 \(J_v\) 的特征向量、特征值为 \(a\)，则 \(x\) 也是 \(\lambda J_v+(r-\lambda)I_v\) 的特征向量，特征值为 \(a+r-\lambda\)。令 \(a=0\)（共 \(v-1\) 次）与 \(a=\lambda v\)（一次），即得本题之结论。

1. 先看全 \(1\) 矩阵 \(J_v\)。它每行都相同，所以秩为 \(1\)，于是有 \(v-1\) 个零特征值。把全 \(1\) 向量 \(\mathbf 1=(1,\dots,1)^T\) 代入：\(J_v\mathbf 1=(v,v,\dots,v)^T=v\,\mathbf 1\)，所以 \(\mathbf 1\) 对应特征值 \(v\)。（也可用“特征值之和 = 迹 = \(v\)”验证：\(0\cdot(v-1)+v=v\)。）
2. 缩放：\(\lambda J_v\) 的特征值就是 \(J_v\) 的特征值乘以 \(\lambda\)，即 \(0\)（\(v-1\) 个）与 \(\lambda v\)（\(1\) 个）。
3. 加单位阵的倍数：对任意向量 \(x\)，若 \(\lambda J_v\,x=a\,x\)，则 \[(\lambda J_v+(r-\lambda)I_v)x=a\,x+(r-\lambda)x=(a+r-\lambda)x.\] 所以同一批特征向量保持不变，每个特征值统一加上 \(r-\lambda\)。
4. 代入：\(a=0\) 给出 \(r-\lambda\)（共 \(v-1\) 个）；\(a=\lambda v\) 给出 \(\lambda v+r-\lambda=r+(v-1)\lambda\)（共 \(1\) 个）。这正是 \(MM^{T}\) 的全部特征值。♦

习题 5

一个正则、一致设计的对偶（dual）显然也是正则且一致的，即使原设计不是对称的也如此。剩下要证：若 \(F\) 是对称的，则它是连通的（linked），因为这正是对偶 \(F^d\) 平衡所需的充要条件。为证 \(F\) 连通，只需证 \(M^{T}M=MM^{T}\)（其中 \(M\) 是 \(F\) 的关联矩阵）。事实上，\(MM^{T}\) 的所有非对角元都相同。

注意，在上一题的解答里，我们算出了任意 BIBD 的关联矩阵的特征值，发现它们都不为 \(0\)。所以若 \(M\) 是方阵，则 \(\det M\neq 0\)，从而 \(M^{-1}\) 存在。把 (8.8) 两边左乘 \(M^{-1}\)、右乘 \(M\)，得到

另一方面，(8.8) 表明 \(MM^{T}=\lambda J_v+(r-\lambda)I_v\)，于是结论得证。

1. 为什么 \(M\) 可逆。对称设计中 \(b=v\)，故 \(M\) 是 \(v\times v\) 方阵。由习题 4，\(MM^{T}\) 的特征值是 \(r+(v-1)\lambda>0\) 与 \(r-\lambda>0\)，全都非零，所以 \(\det(MM^{T})\neq 0\)。而 \(\det(MM^{T})=(\det M)^2\)，故 \(\det M\neq 0\)，\(M^{-1}\) 存在。
2. 关键技巧：相似变换。把 (8.8) 即 \(MM^{T}=\lambda J_v+(r-\lambda)I_v\) 两边左乘 \(M^{-1}\)、右乘 \(M\)： \[M^{-1}(MM^{T})M=M^{-1}\bigl(\lambda J_v+(r-\lambda)I_v\bigr)M.\] 左边 \(M^{-1}M\,M^{T}M=M^{T}M\)。
3. 右边为何不变。对称设计里每个点在 \(r=k\) 个区组，每行每列和都是 \(r\)，于是 \(M\mathbf1=r\mathbf1\) 且 \(\mathbf1^T M=r\mathbf1^T\)，从而 \(J_vM=MJ_v=rJ_v\)，可推出 \(M^{-1}J_vM=J_v\)；而 \(M^{-1}I_vM=I_v\)。所以右边 \(=\lambda J_v+(r-\lambda)I_v\) 原样不动。
4. 于是 \(M^{T}M=\lambda J_v+(r-\lambda)I_v=MM^{T}\)。\(M^{T}M\) 的非对角元（=对偶里两区组的公共点数）也全部相等，即对偶平衡。结论成立。♦

习题 6

因为这样的设计 \(F\) 是平衡的且 \(\lambda=1\)，所以第一条公理（axiom）满足。若区组 \(A\) 与 \(B\) 在至少两个点（设为 \(a\) 与 \(b\)）相交，则 \(a\) 与 \(b\) 就会同时落在至少两个公共区组里，这是不可能的。所以 \(|A\cap B|\le 1\)。

现在假设 \(A\) 与 \(B\) 不相交。取一个既不在 \(A\) 也不在 \(B\) 中的点 \(x\)。这样的点存在，因为当 \(n>1\) 时 \(2(n+1)

最后，第三条公理也满足，因为我们可以取两个区组 \(C\) 与 \(D\)，去掉它们的公共点 \(y\)，便剩下 \(2n\ge 4\) 个点（每个区组里 \(n\) 个）。从每个区组各选一对点，所得的四个点便具有这样的性质：其中没有三个点落在同一区组里（否则就会有一对点同时落在至少两个区组里）。这表明第三条公理也满足。

1. 公理 1（任两点恰一线）：这正是“平衡且 \(\lambda=1\)”的字面意思——任两个不同点恰好同在 \(1\) 个区组里。直接满足。
2. 任两线至多交一点：反设线 \(A,B\) 含有两个公共点 \(a,b\)。那么 \(a,b\) 这一对就同时落在 \(A,B\) 两条线里，即 \(\lambda\ge 2\)，与 \(\lambda=1\) 矛盾。故 \(|A\cap B|\le 1\)。
3. 任两线至少交一点（用反证 + 计数）：反设 \(A,B\) 不相交。它们合起来有 \(2(n+1)\) 个点。先确认存在一个圈外点 \(x\)：总点数 \(v=n^2+n+1\)，而当 \(n>1\) 时 \[n^2+n+1-2(n+1)=n^2-n-1=n(n-1)-1>0,\] 所以确有点 \(x\notin A\cup B\)。再由 \(\lambda=1\)：\(x\) 与 \(A\cup B\) 中每一个点都恰有一条线相连，共 \(2(n+1)\) 条。
   （“为什么这些线两两不同？”）若其中两条线相同，这一条线就会经过 \(x\) 以及 \(A\cup B\) 里两个点，那两个点便与 \(x\) 之外还彼此共线——但若这两点同属 \(A\)（或同属 \(B\)），它们已经在 \(A\)（或 \(B\)）上共线，加上这条新线就共两线，又与 \(\lambda=1\) 矛盾；若分属 \(A,B\)，类似地也会和已有的线冲突。故 \(2(n+1)\) 条线互不相同。
   但过 \(x\) 的线最多只有 \(n+1\) 条（每点在 \(n+1\) 条线上）。而 \(2(n+1)>n+1\)，矛盾。所以 \(A,B\) 必相交，结合上一步得 \(|A\cap B|=1\)。公理 2 成立。
4. 公理 3（找四点无三共线）：取两条线 \(C,D\)，由公理 2 它们恰交于一点 \(y\)。去掉 \(y\)，\(C\) 上还剩 \(n\) 个点、\(D\) 上还剩 \(n\) 个点，共 \(2n\ge 4\)（\(n>1\)）。从 \(C\) 选两点、从 \(D\) 选两点，得四点。若其中三点共线，则必有两点来自同一条 \(C\) 或 \(D\)，这两点便同时在那条原线和新线上，\(\lambda\ge 2\)，矛盾。故无三点共线。公理 3 成立。♦

习题 7

唯一不平凡的部分是第三条公理的成立。这等价于：在原来的有限射影平面 \(H\) 中，存在四条线，其中任三条都不交于一点。我们现在来证明这一点为真。

设 \(a,b\) 是 \(H\) 的两个点，\(L\) 是连接它们的唯一直线。我们知道 \(a\) 与 \(b\) 各自都属于 \(n+1\) 条线，其中 \(n>1\)。因此我们可以选取异于 \(L\) 的两条含 \(a\)（且不含 \(b\)）的线 \(A_1,A_2\)，以及异于 \(L\) 的两条含 \(b\)（且不含 \(a\)）的线 \(B_1,B_2\)。我们断言这四条线具有“任三条不交于一点”的性质。若不然，不妨设 \(A_1,A_2,B_1\) 交于一点。然而 \(A_1\) 与 \(A_2\) 已经交于 \(a\)，所以这个交点必为 \(a\)，从而 \(a\in B_1\)，矛盾。

1. 为什么是“四条线，任三条不共点”。对偶把点换成线、线换成点。原公理 3“存在四点无三共线”对偶后就是“存在四线无三共点”。这就是要证的目标。
2. 构造这四条线。任取两点 \(a,b\)，设 \(L\) 是过 \(a,b\) 的唯一直线。每点在 \(n+1\ge 3\) 条线上，所以过 \(a\) 除 \(L\) 外至少还有两条线 \(A_1,A_2\)（它们不含 \(b\)，否则会与 \(L\) 重合）；同理过 \(b\) 取 \(B_1,B_2\)（不含 \(a\)）。
3. 验证任三条不共点（反证）。四条线里任取三条，必含两条“同族”的（都过 \(a\) 的 \(A_1,A_2\)，或都过 \(b\) 的 \(B_1,B_2\)）。不妨设这三条是 \(A_1,A_2,B_1\)。\(A_1,A_2\) 已交于 \(a\)（两线恰一交点），若三线共点则该点只能是 \(a\)，于是 \(a\in B_1\)。但 \(B_1\) 是“过 \(b\) 而不过 \(a\)”的线，矛盾。其余取法对称同理。
4. 故四条线任三不共点，对偶的公理 3 成立，对偶平面是射影平面。♦

习题 8（Bruck–Ryser–Chowla 的整除部分）

一方面，

所以 \(\det(MM^{T})\) 是一个完全平方数（perfect square）。

另一方面，我们在定理 8.12 的证明中算出

注意，由于我们的设计 \(F\) 平衡且一致，所以它正则，使用 \(r\) 是有依据的。由命题 8.3 知 \((v-1)\lambda=r(k-1)\)；因此上式右端的第一个因子等于 \(r+r(k-1)=rk=r^2\)。事实上，因为 \(F\) 对称，由命题 8.2 有 \(r=k\)。于是得到

这说明 \((r-\lambda)^{\,v-1}\) 是一个完全平方数。然而 \(v-1\) 是奇数，所以 \(r-\lambda\) 必须是完全平方数。

1. 左路：行列式是平方。因为 \(\det(M^T)=\det(M)\)，所以 \(\det(MM^T)=\det M\cdot\det M^T=(\det M)^2\)。又因为 \(M\) 是整数矩阵，\(\det M\) 是整数，故 \(\det(MM^T)\) 是一个整数的平方。
2. 右路：用定理 8.12 把行列式算出来。\(\det(MM^T)=(r+(v-1)\lambda)(r-\lambda)^{v-1}\)。
3. 化简第一个因子。由命题 8.3，\((v-1)\lambda=r(k-1)\)，所以 \[r+(v-1)\lambda=r+r(k-1)=rk.\] 对称设计中 \(r=k\)（命题 8.2），故 \(rk=r^2\)。于是 \(\det(MM^T)=r^2(r-\lambda)^{v-1}\)。
4. 比对两路。\((\det M)^2=r^2(r-\lambda)^{v-1}\)，两边除以 \(r^2\)： \[\left(\frac{\det M}{r}\right)^2=(r-\lambda)^{v-1}.\] 左边是平方，所以 \((r-\lambda)^{v-1}\) 是完全平方数。
5. 奇指数 ⇒ 底数也是平方。题设阶为偶，即 \(v\) 偶，故 \(v-1\) 奇。若 \((r-\lambda)^{\text{奇数}}\) 是完全平方，把它做素因子分解：每个素因子的指数 = (奇数) × (该素因子在 \(r-\lambda\) 中的指数)。要让总指数全为偶，必须 \(r-\lambda\) 里每个素因子指数本身就是偶数，即 \(r-\lambda\) 本身是完全平方数。♦

习题 9（Steiner 三元系的存在条件）

(a) 因为 Steiner 三元系（Steiner triple system）平衡且一致，故正则，于是 \(\lambda(v-1)=r(k-1)\) 成立。但在我们的特殊情形中，\(k=3\) 且 \(\lambda=1\)，从而 \(v=2r+1\)。

(b) 对 Steiner 三元系，恒等式 \(bk=vr\) 变为 \(3b=vr\)。把它与 (a) 中的 \(v=2r+1\) 比较，得到

所以，要么 \(r\) 被 \(3\) 整除，此时 \(2r+1=v\) 形如 \(6t+1\)；要么 \(2r+1=v\) 本身被 \(3\) 整除，此时由于 \(v\) 为奇数，\(v\) 必形如 \(6t+3\)。值得一提的是，Kirkman 于 1847 年证明：若 \(v\) 是这两种形式之一，则在 \(v\) 个点上的 Steiner 三元系确实存在。

1. (a) 求 \(v\) 与 \(r\) 的关系。把 \(k=3,\lambda=1\) 代入 \(\lambda(v-1)=r(k-1)\)： \[1\cdot(v-1)=r\cdot 2\ \Longrightarrow\ v=2r+1.\] （顺带：\(v\) 必为奇数。）
2. (b) 引入区组数 \(b\)。恒等式 \(bk=vr\)（双重计数“(点,含它的区组)”对）在此为 \(3b=vr=(2r+1)r\)，即 \(r(2r+1)=3b\)。这说明 \(3\mid r(2r+1)\)。
3. 分两种情形。因 \(3\) 是素数，必整除 \(r\) 或整除 \(2r+1\)。
   情形一：\(3\mid r\)，设 \(r=3t\)。则 \(v=2r+1=6t+1\)。
   情形二：\(3\mid(2r+1)=v\)。又 \(v\) 为奇数，被 \(3\) 整除且为奇数的数形如 \(6t+3\)（即 \(3,9,15,\dots\)）。
4. 合起来：\(v\equiv 1\) 或 \(3\pmod 6\)。这是必要条件；Kirkman(1847) 证明它也充分。♦

习题 10（汉明距离的三角不等式）

我们可以这样从 \(x\) 到达 \(y\)：先改变 \(d(x,z)\) 位（digit），把 \(x\) 变成 \(z\)，再改变 \(d(z,y)\) 位，把 \(z\) 变成 \(y\)。在这一过程中，至多有 \(d(x,z)+d(z,y)\) 位发生了改变，所以 \(x\) 与 \(y\) 不同的位数至多就是这么多。

1. “改位”视角。从 \(x\) 改到 \(z\)，要动的位恰是 \(x,z\) 不同的那些位，共 \(d(x,z)\) 位；再从 \(z\) 改到 \(y\)，动 \(d(z,y)\) 位。两段合起来动的位数至多 \(d(x,z)+d(z,y)\)（同一位可能被动两次，反而抵消）。
2. 结果界住目标。这一整套操作把 \(x\) 变成了 \(y\)，所以 \(x,y\) 真正不同的位数 \(d(x,y)\) 不会超过我们动过的位数总和：\(d(x,y)\le d(x,z)+d(z,y)\)。♦

习题 11

不能。要让那种码是完美的（perfect），我们需要 \(v(1+v)=2^{v}\)。这是不可能的，因为 \(v\) 与 \(1+v\) 中必有一个是奇数（且至少为 \(7\)），而 \(2\) 的幂不可能有一个真奇因子（proper odd divisor）。

1. 列出完美性方程。“球数 × 球大小 = 全空间大小”：\(v\cdot(1+v)=2^{v}\)。
2. 奇偶分析。相邻整数 \(v\) 与 \(v+1\) 中必有一个是奇数。题设范围使这个奇数 \(\ge 7>1\)，即它是一个大于 1 的真奇因子。
3. 矛盾。等式右边 \(2^{v}\) 只有素因子 \(2\)，它的因子全是 \(2\) 的幂，绝不会有大于 1 的奇因子。而左边却有一个 \(\ge 7\) 的奇因子。矛盾，故方程无解，这种完美码不存在。♦

习题 12（陪集要么相等要么不交）

设 \(aH\) 与 \(bH\) 是 \(H\) 在 \(G\) 中的两个陪集（coset）。先假设 \(a\in bH\)。这意味着存在 \(h\in H\) 使 \(a=bh\)。于是 \(aH=bhH=bH\)。事实上，\(hH=H\)，因为 \(hH\subseteq H\)（\(H\) 对乘法封闭）且 \(|hH|=|H|\)。

再假设 \(a\notin bH\)。我们断言此时 \(aH\cap bH=\varnothing\)。若不然，设 \(c\in aH\cap bH\)。这表示 \(c=ah_1=bh_2\)，其中 \(h_1,h_2\in H\)。但这推出 \(a=bh_2h_1^{-1}\)，与 \(a\notin bH\) 矛盾。

1. 记号回顾。\(aH=\{ah:h\in H\}\)。它是 \(H\) 用 \(a\) “平移”得到的子集。
2. 情形一：\(a\in bH\)，证 \(aH=bH\)。由 \(a\in bH\) 得 \(a=bh\)（某 \(h\in H\)）。于是 \[aH=(bh)H=b(hH).\] 而 \(hH=H\)：因 \(H\) 对乘法封闭故 \(hH\subseteq H\)，又左乘 \(h\) 是单射（可乘 \(h^{-1}\) 还原）故 \(|hH|=|H|\)，有限集合中“子集且同样大”就相等。所以 \(aH=bH\)。
3. 情形二：\(a\notin bH\)，证 \(aH\cap bH=\varnothing\)（反证）。设有公共元 \(c=ah_1=bh_2\)。两边右乘 \(h_1^{-1}\)： \[a=bh_2h_1^{-1}.\] 因 \(h_2h_1^{-1}\in H\)（子群对乘法和逆封闭），故 \(a\in bH\)，与假设矛盾。所以两陪集不交。
4. 综合：两陪集“相等”或“不交”，没有第三种情况。♦

习题 13（素数边正多边形的着色，且至少用两色）

我们用集合 \([x]\) 中的颜色给一个正 \(p\) 边形的各边着色，使得至少用到两种颜色。若两种着色互为某个旋转的像，则称它们等价。如果各边是可区分的，由于至少要用两种颜色，着色总数应为 \(x^p-x\)。

共有 \(p\) 个旋转：\(r,r^2,\dots,r^p=\mathrm{id}\)。非恒等旋转不会固定任何允许的着色。事实上，若 \(r^i\) 固定某着色 \(C\)，则多边形第一条边必与它的第 \(i+1\) 条边同色，后者又必与第 \(2i+1\) 条边同色，依此类推。由于 \(p\) 是素数，\(p\) 与 \(i\) 互素，这就推出多边形所有边同色，矛盾。

因此，由定理 8.36，不等价着色的个数为

因为这是某类着色的个数，它必为整数，从而证明了我们的结论（即 \(p\mid x^p-x\)，费马小定理）。

1. 固定（带标号）的着色总数。每条边 \(x\) 种选择，共 \(x^p\) 种；减去“全同色”的 \(x\) 种（这些只用一色，不合“至少两色”），得 \(x^p-x\) 种合法着色。
2. 旋转群。群为循环群 \(\{\mathrm{id},r,r^2,\dots,r^{p-1}\}\)，共 \(p\) 个元素。
3. 各旋转的不动点。恒等 \(\mathrm{id}\) 固定全部 \(x^p-x\) 个合法着色。非恒等 \(r^i\)（\(1\le i\le p-1\)）固定的着色须满足“边 \(1\) 与边 \(1+i\) 同色、边 \(1+i\) 与边 \(1+2i\) 同色……”。因 \(p\) 素且 \(i\) 与 \(p\) 互素，下标 \(1,1+i,1+2i,\dots\)（模 \(p\)）会跑遍所有边，强制全部同色——但全同色不在合法集合内，故 \(r^i\) 的不动点数为 \(0\)。
4. Burnside 求平均。 \[\#\text{轨道}=\frac1p\Bigl(\underbrace{(x^p-x)}_{\mathrm{id}}+\underbrace{(p-1)\cdot 0}_{\text{其余}}\Bigr)=\frac{x^p-x}{p}.\]
5. 整数性 ⇒ 费马小定理。轨道数是计数，必为非负整数，所以 \(p\mid x^p-x\)。♦

习题 14（图的自同构群大小）

设 \(G\) 是作用在图的顶点集 \([n]\) 上的对称群（symmetric group）。那么 \(G\) 也作用在所有标号方式（labeling）的集合上。在后一个作用中，\(\bigl|i^{G}\bigr|\) 恰是图的所有标号方式的个数，而 \(|\mathrm{Aut}(H)|\) 是该作用的轨道个数。

1. 群与作用。对称群 \(G=S_n\)（\(n\) 个顶点的全体置换）作用在“给这张图贴 \(1\sim n\) 标号”的所有方式上。一个标号 \(i\) 经置换 \(g\) 变为另一个标号 \(g\cdot i\)。
2. 轨道 = 长得一样的标号。两种标号若能通过某个置换互相得到，就属于同一轨道；轨道数就是“本质不同的标号数”。题中 \(|\mathrm{Aut}(H)|\) 即此轨道数。
3. 轨道–稳定子。对任一标号 \(i\)，其轨道大小 \(|i^G|=\dfrac{|G|}{|\mathrm{Stab}(i)|}\)。稳定子 \(\mathrm{Stab}(i)\) 是“贴好标号后仍保持图不变的置换”，正是自同构群 \(\mathrm{Aut}(H)\)。又 \(S_n\) 在标号上是传递的，轨道就是全体 \(n!\) 种标号，即 \(|i^G|=n!\)。
4. 于是 \(n!=|i^G|=\dfrac{n!}{|\mathrm{Aut}(H)|}\cdot|\mathrm{Aut}(H)|\)，整理得本质不同标号数 \(=\dfrac{n!}{|\mathrm{Aut}(H)|}\)。♦

习题 15（正方形四边、三色着色）

在四个旋转 \(r,r^2,r^3,\mathrm{id}\) 中，有两个——即 \(r\) 与 \(r^3\)——只保持那些四边全同色的着色。恒等保持全部 \(81\) 个着色。最后，\(r^2\) 保持那些对边同色的着色，这有九种情形。由定理 8.36，可知不等价着色共有

1. 旋转群。四个元素：\(\mathrm{id}\)（转 \(0^\circ\)）、\(r\)（\(90^\circ\)）、\(r^2\)（\(180^\circ\)）、\(r^3\)（\(270^\circ\)）。
2. \(\mathrm{id}\) 的不动点。不动任何边，全部 \(3^4=81\) 个着色都被固定。
3. \(r\) 与 \(r^3\)（转 \(90^\circ,270^\circ\)）。它们把四条边整体循环 \(1\to2\to3\to4\to1\)，要被固定就得四边全同色：\(3\) 种。各贡献 \(3\)。
4. \(r^2\)（转 \(180^\circ\)）。把对边两两交换（边1↔边3，边2↔边4）。被固定的着色须“对边同色”：两组对边各自独立选色，\(3\times 3=9\) 种。
5. Burnside 平均。 \[\frac14\bigl(\underbrace{81}_{\mathrm{id}}+\underbrace{3}_{r}+\underbrace{9}_{r^2}+\underbrace{3}_{r^3}\bigr)=\frac{96}{4}=24.\] （原书把 \(r,r^3\) 合并写成 \(2\cdot 3\)，把 \(r^2\) 写成 \(1\cdot 9\)，等价。）♦

习题 16（四面体六条棱、k 色着色）

四面体（tetrahedron）有 \(12\) 个可由一连串旋转实现的对称，正如我们在第 4 章习题 36 中所证。最简单的是恒等，它固定全部 \(k^6\) 个着色。然后有八个绕轴的旋转，该轴垂直于四面体某个面 \(F\) 并通过第四个顶点 \(D\)；这些旋转只固定那些“\(F\) 的三条棱同色、与 \(D\) 相邻的三条棱同色”的着色，共有 \(k^2\) 个。最后，有三个把两对顶点互换的变换。不失一般性，考虑同时交换 \(A,B\) 与 \(C,D\) 的那个变换。它固定棱 \(AB\) 与 \(CD\)，互换棱 \(BC\) 与 \(AD\)，互换棱 \(AC\) 与 \(BD\)。因此该变换保持那些“\(BC\) 与 \(AD\) 同色、\(AC\) 与 \(BD\) 同色”的着色，共有 \(k^4\) 个。

由定理 8.36，不等价着色的个数为

请读者自行找出 \(k=2\) 时的 \(12\) 个不等价着色。

1. 旋转群有 12 个元素，分三类。恒等 \(1\) 个；绕“顶点–对面中心”轴的 \(\pm120^\circ\) 旋转 \(8\) 个（四个顶点各两个方向）；绕“对棱中点连线”轴的 \(180^\circ\) 旋转 \(3\) 个（三对对棱）。
2. 恒等：固定全部 \(k^6\)（每条棱独立 \(k\) 色）。
3. 顶点轴 \(120^\circ\)（\(8\) 个）。这种旋转把含某顶点的三条棱循环、把对面三条棱循环，形成两个长度为 3 的循环。被固定须每个循环内同色，即两组各 \(1\) 色，共 \(k^2\) 个。八个旋转各贡献 \(k^2\)。
4. 对棱轴 \(180^\circ\)（\(3\) 个）。以交换 \(A\leftrightarrow B,\ C\leftrightarrow D\) 为例：棱 \(AB,CD\) 各自不动（\(2\) 个固定棱），\(BC\leftrightarrow AD\)、\(AC\leftrightarrow BD\)（\(2\) 个对换）。循环结构为“\(2\) 个长度 1 + \(2\) 个长度 2”，共 \(4\) 个独立色块，故固定 \(k^4\) 个。三个旋转各贡献 \(k^4\)。
5. Burnside 平均。 \[\frac1{12}\bigl(1\cdot k^6+8\cdot k^2+3\cdot k^4\bigr)=\frac{k^6+3k^4+8k^2}{12}.\]♦

返回 全书目录