8.7　习题Exercises

本页为译文 + 高中讲解合一：黑色正文为忠实翻译的题目；彩色框（目标 / 思路 / 分步推演）与配图为面向高中生的解题提示，逐步推演、举例、画图，不用比喻。本节只给思路与方法，完整最终答案见对应“习题解答”一节。

下面逐题给出中文翻译与解题提示。先回顾几个贯穿全节的核心结论，后面会反复引用：

习题

1. 题 1. 证明：若一个设计是平衡的且均匀的，则它也是正则的。

   思路目标是“由平衡 + 均匀推出每个点出现的区组数 \(r\) 是常数”。核心手法是双重计数（double counting）：固定一个点 \(i\)，去数“含点 \(i\) 的区组中、除 \(i\) 以外的点位”的总数，用两种方式去算同一个量。
   1. 固定点 \(i\)。设它出现在 \(r_i\) 个区组中（这正是要证明与 \(i\) 无关的量）。
   2. 统计“数对”\((j,\,B)\)：其中 \(B\) 是同时含 \(i\) 和另一点 \(j\)（\(j\neq i\)）的区组。
   3. 按点 \(j\) 分类计数：每个 \(j\neq i\) 都与 \(i\) 恰好共处 \(\lambda\) 个区组（平衡），共 \(v-1\) 个 \(j\)，故总数 \(=(v-1)\lambda\)。
   4. 按区组 \(B\) 分类计数：含 \(i\) 的区组有 \(r_i\) 个，每个区组里除 \(i\) 外还有 \(k-1\) 个点（均匀），故总数 \(=r_i(k-1)\)。
   5. 两式相等：\(r_i(k-1)=(v-1)\lambda\)，于是 \(r_i=\dfrac{(v-1)\lambda}{k-1}\)，右端与 \(i\) 无关，所以所有点的 \(r_i\) 相等，即设计正则。

2. 题 2. 是否存在一个平衡均匀设计，使得 \(r\) 整除 \(v\)？

   思路这是一道“构造或否定”的存在性问题。先回忆参数间的恒等式（见题 1）：\(r(k-1)=(v-1)\lambda\)。再去找一个具体的小例子让 \(r\mid v\) 成立——找到一个就证明“存在”。
   小例提示考虑最朴素的设计：把所有点本身各成单点区组，或取 \(k=v\) 让每个区组就是全集这种平凡情形，验证它是否平衡均匀且 \(r\mid v\)。再考虑 Fano 平面以外的具体小设计，逐一核对 \(r\) 能否整除 \(v\)。建议列一张参数表，逐行验证 \(r\mid v\)。

3. 题 3.（较难，标 +） 设 \(M\) 是某平衡均匀设计 \(F\) 的关联矩阵。请用 \(F\) 的参数、\(v\times v\) 单位矩阵 \(I_v\) 以及所有元素都为 \(1\) 的 \(v\times v\) 矩阵 \(J_v\)，把矩阵乘积 \(MM^T\) 表示出来。

   思路关键是逐个理解 \(MM^T\) 的每一个元素的组合意义。\((MM^T)_{is}=\sum_j M_{ij}M_{sj}\)，它在数“同时含点 \(i\) 和点 \(s\) 的区组个数”。
   1. 对角元 \(i=s\)：\((MM^T)_{ii}=\sum_j M_{ij}^2=\) 含点 \(i\) 的区组数 \(=r\)。
   2. 非对角元 \(i\neq s\)：\((MM^T)_{is}=\) 同时含 \(i,s\) 的区组数 \(=\lambda\)（平衡）。
   3. 把“对角全是 \(r\)、非对角全是 \(\lambda\)”翻译成 \(I_v\) 与 \(J_v\)： \[MM^T=(r-\lambda)I_v+\lambda J_v.\]

4. 题 4. 设 \(M\) 是参数为 \((b,v,r,k,\lambda)\) 的 BIBD 的关联矩阵。证明：\(MM^T\) 的特征值（eigenvalue）为 \(r-\lambda\)，重数为 \(v-1\)；以及 \(r+\lambda(v-1)=rk\)，重数为 \(1\)。

   思路直接利用题 3 的结论 \(MM^T=(r-\lambda)I_v+\lambda J_v\)，关键是先求出 \(J_v\) 的特征值，再做线性平移。
   1. 先分析 \(J_v\)（全 \(1\) 矩阵）的特征值：它秩为 \(1\)。全 \(1\) 向量 \(\mathbf 1\) 满足 \(J_v\mathbf 1=v\mathbf 1\)，故 \(v\) 是特征值（重数 \(1\)）；任何与 \(\mathbf 1\) 正交的向量被 \(J_v\) 映为 \(0\)，故 \(0\) 是特征值（重数 \(v-1\)）。
   2. 因为 \(MM^T=(r-\lambda)I_v+\lambda J_v\)，每个特征值都按 \(\mu\mapsto (r-\lambda)+\lambda\mu\) 平移：
      • \(J_v\) 的 \(0\) 特征值（重数 \(v-1\)）\(\Rightarrow\) \(MM^T\) 的 \(r-\lambda\)（重数 \(v-1\)）。
      • \(J_v\) 的 \(v\) 特征值（重数 \(1\)）\(\Rightarrow\) \(MM^T\) 的 \(r-\lambda+\lambda v=r+\lambda(v-1)\)（重数 \(1\)）。
   3. 最后用 BIBD 的参数关系 \(\lambda(v-1)=r(k-1)\)（见题 1），代入得 \(r+\lambda(v-1)=r+r(k-1)=rk\)。

5. 题 5.（较难，标 +） 证明：对称 BIBD 的对偶（dual）仍是 BIBD。

   思路“对偶”就是把点与区组的角色互换——关联矩阵从 \(M\) 换成转置 \(M^T\)。对称（\(v=b\)）保证 \(M\) 是方阵，这是关键。要证对偶仍是 BIBD，即要证 \(M^TM\) 也具有“对角为常数、非对角为常数”的形式。
   1. 对称设计 \(v=b\)，\(M\) 是 \(v\times v\) 方阵。由题 4 知 \(MM^T\) 可逆（特征值 \(r-\lambda>0\) 与 \(rk>0\) 都非零），故 \(M\) 可逆。
   2. 由 \(MM^T=(r-\lambda)I+\lambda J\)，并利用 \(MJ=kJ\)、\(JM=rJ\)（对称时 \(r=k\)）等关系，推出 \(M\) 与 \(J\) 可交换，从而 \(M^TM\) 也化为 \((r-\lambda)I+\lambda J\) 的同型。
   3. 这说明对偶设计中“任意两个区组的公共点数”是常数，参数同样满足 BIBD 定义，得证。

6. 题 6. 设 \(n>1\)。证明：参数为 \((n^2+n+1,\,n^2+n+1,\,n+1,\,n+1,\,1)\) 的设计是一个有限射影平面。

   思路直接核对“有限射影平面”的公理定义即可：（i）任意两点恰好确定一条公共直线；（ii）任意两条直线恰好交于一点；（iii）存在四点两两不共线（非退化）。把“点”看成点、“区组”看成直线，逐条用给定参数验证。
   1. \(\lambda=1\)：任意两点恰好共处 \(1\) 个区组，即恰好一条公共直线——公理 (i) 成立。
   2. \(v=b\)（对称设计），用题 5 的对偶性质，公理 (ii) 化为公理 (i) 在对偶中的版本：任两直线恰交于一点。
   3. 每条直线含 \(k=n+1\) 个点、每点过 \(r=n+1\) 条直线，且 \(n>1\) 保证规模足够，可找出非退化的四点。

7. 题 7. 证明：有限射影平面的对偶设计也是有限射影平面。

   思路射影平面是对称 BIBD（\(v=b\)），由题 5 它的对偶仍是 BIBD，且对偶把题 6 验证的两条对称公理 (i)(ii) 互换，仍然成立。这正是射影几何中著名的对偶原理：点与线在公理体系中地位完全对称。

8. 题 8. 若 \(v=b\)，则称该设计为对称的。设 \(F\) 是一个平衡均匀对称设计，且 \(v\) 为偶数。证明：\(r-\lambda\) 必定是完全平方数（perfect square）。

   思路（按题给提示）盯住关联矩阵的行列式平方 \(\det(MM^T)\)。一方面 \(M\) 为整数方阵，\(\det M\) 是整数，故 \(\det(MM^T)=(\det M)^2\) 是一个完全平方数；另一方面用特征值把它算出来。
   1. 由题 4，\(MM^T\) 的特征值为 \(r-\lambda\)（重数 \(v-1\)）和 \(rk\)（重数 \(1\)），行列式 = 特征值之积： \[\det(MM^T)=rk\,(r-\lambda)^{v-1}.\] 对称设计 \(r=k\)，故 \(rk=r^2\)，于是 \(\det(MM^T)=r^2(r-\lambda)^{v-1}\)。
   2. 它等于 \((\det M)^2\)，是完全平方数。其中 \(r^2\) 已是平方。
   3. 当 \(v\) 为偶数时 \(v-1\) 为奇数，故 \((r-\lambda)^{v-1}=(r-\lambda)^{\text{偶}}\cdot(r-\lambda)\)。要让整体是平方，必须 \(r-\lambda\) 本身是完全平方数，得证。
   注：这是著名的 Bruck–Ryser 定理的简单一半。该定理还指出：若 \(v\) 为奇数，则方程 \[x^2=(r-\lambda)y^2+(-1)^{(v-1)/2}\lambda z^2\tag{8.7}\] 必须有不全为零的整数解 \((x,y,z)\)。

9. 题 9. \(k=1\) 的均匀设计叫做集合，\(k=2\) 的均匀设计叫做图。下一类 \(k=3\) 的均匀设计常称为三元系（triple system），其中 \(\lambda=1\) 的平衡三元系称为Steiner 三元系（Steiner triple system）。例如 Fano 平面就是一个 Steiner 三元系。

   （a）证明：不存在 \(v\) 为偶数的 Steiner 三元系。

   （b）证明：不存在 \(v+1\) 能被 \(6\) 整除的 Steiner 三元系。

   思路Steiner 三元系是 \(k=3,\lambda=1\) 的 BIBD。把这两个值代入基本参数关系，从“\(r\)、\(b\) 必须是整数”这一整除约束出发逼出矛盾。
   1. 由 \(\lambda(v-1)=r(k-1)\)，代入 \(\lambda=1,k=3\)：\(v-1=2r\)，即 \(r=\dfrac{v-1}{2}\)。要 \(r\) 为整数，须 \(v-1\) 为偶数，即 \(v\) 为奇数——这就排除了 \(v\) 偶数，得 (a)。
   2. 再用 \(bk=vr\)（数“点–区组关联对”）：\(3b=v\cdot\dfrac{v-1}{2}\)，即 \(b=\dfrac{v(v-1)}{6}\)。要 \(b\) 为整数，须 \(6\mid v(v-1)\)。
   3. 结合 (a) 已知 \(v\) 为奇数，逐一分析 \(v\bmod 6\)：只有 \(v\equiv1\) 或 \(v\equiv3\pmod 6\) 时 \(b\) 为整数。若 \(6\mid v+1\)，即 \(v\equiv5\pmod6\)，则 \(b\) 不是整数，矛盾，得 (b)。
   数字验证取 \(v=7\)（Fano）：\(r=(7-1)/2=3\)，\(b=7\cdot6/6=7\)，都为整数，确实存在。取 \(v=5\)：\(r=2\) 整数，但 \(b=5\cdot4/6=20/6\) 不是整数，故 \(v=5\) 不存在 Steiner 三元系——正符合 (b)（\(5+1=6\)）。

10. 题 10. 证明引理 8.23。

    思路这是要补全正文中引理 8.23 的证明（该引理是第 8 章关于设计/纠错码的一条结构性引理）。做法：回到正文中引理 8.23 的陈述，弄清其假设与结论，再沿用本章已建立的工具——通常是关联矩阵的代数性质（题 3、题 4 的 \(MM^T\) 公式与特征值）或参数整除关系。先把“要证什么”一字不漏抄下来，再对照最接近的已证定理找突破口。

11. 题 11. 用例 8.25 所述方法、由有限射影平面构造出的纠错码，会不会是完美码（perfect code）？

    思路把问题翻成不等式判定：完美码要满足球覆盖（Hamming bound）取等条件——以各码字为中心、半径 \(m\) 的 Hamming 球恰好不重不漏地铺满整个空间。写出由射影平面参数得到的码长 \(n\)、码字数 \(w\)、最小距离 \(d\)，代入完美码的必要条件（即本节开头列出的等式） \[w\sum_{d=0}^{m}\binom{n}{d}(q-1)^d=q^{\,n},\] 逐项核验左右是否相等即可下结论。

12. 题 12. 证明：若 \(G\) 是一个群，\(H\) 是 \(G\) 的子群，则 \(H\) 在 \(G\) 中的两个陪集（coset）要么不相交、要么相等。换言之，证明 \(H\) 的诸陪集划分（partition）了 \(G\)。（注意这蕴含 \(|H|\) 整除 \(|G|\)，即 Lagrange 定理。）

    思路这是 Lagrange 定理的标准证明骨架。要证“两陪集不相交或相等”，标准技巧是：假设它们有公共元素，证明它们必相等。再说明每个陪集与 \(H\) 一样大，于是 \(G\) 被等大的若干块划分。
    1. 设左陪集 \(aH\) 与 \(bH\) 有公共元素 \(x\)：\(x=ah_1=bh_2\)（\(h_1,h_2\in H\)）。
    2. 则 \(a=bh_2h_1^{-1}\)，而 \(h_2h_1^{-1}\in H\)（子群封闭、含逆），故 \(aH=b(h_2h_1^{-1})H=bH\)（因 \(hH=H\)）。所以一旦相交即相等。
    3. 映射 \(h\mapsto ah\) 是 \(H\to aH\) 的双射，故每个陪集恰有 \(|H|\) 个元素。
    4. 诸陪集互不相交且并起来为 \(G\)，每块大小为 \(|H|\)，于是 \(|G|=(\text{陪集个数})\cdot|H|\)，即 \(|H|\mid|G|\)。

13. 题 13. 利用定理 8.36 证明费马小定理（small Fermat theorem）：若 \(x\) 是正整数、\(p\) 是素数，则 \(x^p-x\) 能被 \(p\) 整除。

    思路这是轨道计数定理（定理 8.36）的漂亮应用。构造一个由 \(p\) 阶循环群作用的染色问题，让“轨道个数为整数”这件事直接逼出整除性。
    1. 考虑用 \(x\) 种颜色给一个 \(p\) 颗珠子的项链（正 \(p\) 边形）染色，染色方案共 \(x^p\) 种。让 \(p\) 阶循环群 \(G=\mathbb Z_p\)（旋转）作用其上。
    2. 计算每个 \(g\) 的固定点 \(|F_g|\)：恒等旋转固定全部 \(x^p\) 种；其余 \(p-1\) 个非平凡旋转（因 \(p\) 素数）只固定“整圈同色”的 \(x\) 种。
    3. 代入定理 8.36：轨道数 \(=\dfrac{1}{p}\big(x^p+(p-1)x\big)\)。这必须是整数。
    4. 整数条件给出 \(p\mid x^p+(p-1)x=x^p-x+px\)，故 \(p\mid x^p-x\)，得证。

14. 题 14. 解释为什么定理 5.7 是引理 8.34 的一个特殊情形。

    思路这是一道“识别包含关系”的题。把定理 5.7 的陈述与引理 8.34 的陈述并排写出，找出引理 8.34 中取什么特殊的群作用或参数后，恰好退化成定理 5.7 的结论。关键是指出二者计数的是同一类对象，只是引理 8.34 更一般。先抄下两条命题的精确陈述，再做一一对应。

15. 题 15. 求给正方形的四条边各染红、蓝、绿之一的染色方案数；若两种染色可经旋转互相得到，则视为等价。

    思路正方形的旋转群是 4 阶循环群 \(C_4=\{e,r,r^2,r^3\}\)（转 \(0^\circ,90^\circ,180^\circ,270^\circ\)）。用定理 8.36 数轨道，对每个旋转数“被它固定的染色数”。一个染色被某旋转固定，当且仅当被该旋转轮换在一起的边必须同色。颜色数 \(q=3\)。
    1. \(e\)（\(0^\circ\)）：每条边独立，固定数 \(=3^4=81\)。
    2. \(r\)（\(90^\circ\)）：四条边构成一个 \(4\)-循环，必须全同色，固定数 \(=3^1=3\)。\(r^3\)（\(270^\circ\)）同理 \(=3\)。
    3. \(r^2\)（\(180^\circ\)）：边被配成两对，每对同色，固定数 \(=3^2=9\)。
    4. 代入：轨道数 \(=\dfrac{1}{4}(81+3+9+3)=\dfrac{96}{4}=24\)。
    提示把每个旋转写成边的置换、数出它的循环个数 \(c(g)\)，固定数就是 \(3^{c(g)}\)，这是用 Burnside 数染色的通用套路。

16. 题 16. 求用 \(k\) 种颜色给正四面体（regular tetrahedron，四个面均为正三角形）的六条棱染色的方案数；若两种染色可经旋转互相得到，则视为相同。

    思路正四面体的旋转群有 \(12\) 个元素（即 \(A_4\)）。对每个旋转，把它作用在 6 条棱上写成置换、数出循环个数 \(c(g)\)，被固定的染色数为 \(k^{c(g)}\)，再代入定理 8.36 求平均。
    1. 恒等元 \(1\) 个：6 条棱各成一循环，\(c=6\)，贡献 \(k^6\)。
    2. 过顶点–对面中心的 \(120^\circ/240^\circ\) 旋转 \(8\) 个：棱被分成两个 \(3\)-循环，\(c=2\)，各贡献 \(k^2\)。
    3. 过两对棱中点连线的 \(180^\circ\) 旋转 \(3\) 个：分析棱的置换得 \(c=4\)（两条棱不动 + 两个对换），各贡献 \(k^4\)。
    4. 代入：方案数 \(=\dfrac{1}{12}\big(k^6+8k^2+3k^4\big)\)。
    注意务必先把每条棱在每个旋转下的去向画清楚（给 6 条棱编号），再数循环，否则容易把 \(c(g)\) 数错。

17. 题 17.（较难，标 +） 求用 \(k\) 种颜色给立方体的 12 条棱染色的方案数；若两种染色可经旋转互相得到，则视为相同。

    思路立方体的旋转群有 \(24\) 个元素。把它们按类型分组，对每类找出它在 12 条棱上的置换、数出循环个数 \(c(g)\)，固定染色数 \(=k^{c(g)}\)，再用定理 8.36 求平均。这题计算量最大，关键是分类不重不漏、循环数不算错。
    1. 恒等元 \(1\) 个：\(c=12\)，贡献 \(k^{12}\)。
    2. 过面心轴 \(90^\circ\)（及 \(270^\circ\)）共 \(6\) 个：棱被分成三个 \(4\)-循环，\(c=3\)，贡献 \(6k^{3}\)。
    3. 过面心轴 \(180^\circ\) 共 \(3\) 个：\(c=6\)，贡献 \(3k^{6}\)。
    4. 过顶点轴 \(120^\circ/240^\circ\) 共 \(8\) 个：棱分成四个 \(3\)-循环，\(c=4\)，贡献 \(8k^{4}\)。
    5. 过棱中点轴 \(180^\circ\) 共 \(6\) 个：\(c=7\)（两条棱不动 + 五个对换），贡献 \(6k^{7}\)。
    6. 核对个数 \(1+6+3+8+6=24\)，无误。代入： \[\#=\frac{1}{24}\big(k^{12}+6k^{3}+3k^{6}+8k^{4}+6k^{7}\big).\]

返回 全书目录