6.7　习题解答Solutions to exercises

本页为译文 + 高中讲解合一：黑色正文为原书每道解答的忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步把原书省略的步骤补全、举具体数字例子、画图，不用比喻。本节是第 6 章（极值组合学）全部习题的解答。

习题 1

我们对 \(n\) 用归纳法证明，初始情形 \(n=2\) 容易验证。取图 \(G\) 的一条边，端点为 \(A\) 与 \(B\)。若 \(A\) 与 \(B\) 的度数之和至少为 \(2n+1\)，则 \(A\) 与 \(B\) 有一个公共邻居 \(C\)，证毕。否则，删去 \(A\)、\(B\) 以及与它们相邻的所有边。剩下的图有 \(2n-2\) 个顶点，且至少有 \[ n^2+1-(2n-1)=(n-1)^2+1 \] 条边，于是由归纳假设，它含有一个三角形。

1. 归纳的起点 \(n=2\)：此时图有 \(4\) 个顶点、至少 \(n^2+1=5\) 条边。\(4\) 个顶点最多有 \(\binom{4}{2}=6\) 条边，\(5\) 条边只缺一条，很容易看出此时必有三角形。
2. 取一条边 \(AB\)，分两种情况。设当前图有 \(2n\) 个顶点、至少 \(n^2+1\) 条边。
3. 情况一：\(\deg(A)+\deg(B)\ge 2n+1\)。除去 \(A,B\) 自己，其余顶点共 \(2n-2\) 个。\(A\) 的邻居（除 \(B\) 外）和 \(B\) 的邻居（除 \(A\) 外）加起来有 \(\big(\deg(A)-1\big)+\big(\deg(B)-1\big)\ge 2n-1\) 个“邻居名额”，但只能落在 \(2n-2\) 个顶点上。\(2n-1>2n-2\)，由抽屉原理必有一个顶点 \(C\) 同时是 \(A\) 和 \(B\) 的邻居。于是 \(A,B,C\) 两两相邻，得到三角形。
4. 情况二：\(\deg(A)+\deg(B)\le 2n\)。删去 \(A\) 和 \(B\)。被删掉的边是“与 \(A\) 相连的边”加“与 \(B\) 相连的边”，但边 \(AB\) 在两边各算了一次，所以删掉的边数恰为 \(\deg(A)+\deg(B)-1\le 2n-1\) 条。
5. 数剩下的边。剩 \(2n-2=2(n-1)\) 个顶点，边数至少为 \[ (n^2+1)-(2n-1)=n^2-2n+2=(n-1)^2+1. \] 这正好是“\(2(n-1)\) 个顶点、超过 \((n-1)^2\) 条边”的形式，套上归纳假设，剩下的图含三角形，原图当然也含。♦

习题 2

(a)（(c) 部分蕴含本部分，但我们也另给一个证明。）用所有可能的方式取出 \(G\) 的全部二部子图（bipartite subgraph），并统计它们的边。换言之，统计所有的对 \((e,B)\)，其中 \(e\) 是 \(G\) 的二部子图 \(B\) 的一条边。

设 \(n\) 为 \(G\) 的顶点数。一方面，\(G\) 的每条边都出现在 \(2^{n-2}\) 个二部子图中，所以这种对的总数是 \(e(G)\,2^{n-2}\)。（确实如此：固定一条边后，与该边不相干的 \(n-2\) 个顶点要分成有序的两块，方法数是 \(2^{n-2}\)。）另一方面，\(G\) 的至少含一条边的二部子图 \(B\) 共有 \(2^{n-1}-1\) 个。因此由抽屉原理，必有某个 \(B\)，它至少有 \[ \frac{e(G)\,2^{n-2}}{2^{n-1}-1}>\frac{e(G)}{2} \] 条边。

(c)（本部分蕴含 (b)。）把顶点集划分成两块 \(Q\) 与 \(R\)，并丢掉每块内部的边。若得到的二部图 \(B\) 满足 (c) 中的判据，证毕。若不满足，则存在一个顶点 \(x\) 违反该判据，这意味着与 \(x\) 相邻的边中，超过一半落在与 \(x\) 同一块内。于是把 \(x\) 移到另一块，\(B\) 的边数会增加。只要还存在违反判据的顶点，就一直这样做。这个过程最终必定停止，因为 \(B\) 的边数不可能无限增长，而每一步它都严格增加。过程停止时，没有任何顶点 \(x\) 违反判据，命题得证。

1. (a) 把同一个数 \(\sum_{(e,B)}1\) 横竖各数一遍。一个“二部子图”对应一次把 \(n\) 个顶点分成有序两块 \(Q,R\) 的方式，共 \(2^n\) 种。
2. 按边来数（竖着数）。取定 \(G\) 的一条边 \(e=uv\)。\(e\) 出现在子图 \(B\) 里 \(\iff\) \(u,v\) 被分到不同块。固定 \(u,v\) 异块后，剩下 \(n-2\) 个顶点各自任选一块，有 \(2^{n-2}\) 种。所以每条边贡献 \(2^{n-2}\) 个对，总对数 \(=e(G)\cdot 2^{n-2}\)。
3. 按子图来数（横着数）。这些对都属于“至少含一条边”的二部子图。把顶点分成两块时，至少有一条边跨块的分法有 \(2^{n-1}-1\) 种（这是按书中计数；总分法去掉那些一条跨边都没有的）。
4. 抽屉原理收尾。把总对数平均分到这 \(2^{n-1}-1\) 个子图上，必有一个子图的边数不少于平均值： \[ \frac{e(G)2^{n-2}}{2^{n-1}-1}>\frac{e(G)2^{n-2}}{2^{n-1}}=\frac{e(G)}{2}. \]
5. (c) 局部调整法。判据是“每个顶点跨块的边数 \(\ge\) 它同块内的边数”。若某顶点 \(x\) 同块内的边比跨块的多，就把 \(x\) 搬到对面：原来 \(x\) 的“同块边”变跨块、“跨块边”变同块，净增加的跨块边数 \(=\) (同块边 \(-\) 跨块边) \(>0\)，所以总跨块边数严格变大。
6. 为什么一定停？跨块边数是个不超过 \(e(G)\) 的整数，每步严格增大，不能无限增大，故有限步后必停。停时人人满足判据：每个顶点至少一半的边跨块。把所有顶点的“至少一半”加起来，可知整张图至少一半的边跨块，于是又得到 (b)：存在边数 \(\ge e(G)/2\) 的二部子图。♦

习题 3

只需证明：在允许范围内的任一区间 \([a,b]\) 上，函数 \[ g(x)=\binom{x}{r}+\binom{a+b-x}{r} \] 在 \(x=(a+b)/2\) 处有唯一的最小值。为简化记号，令 \(n=a+b\)。我们要证 \(g'(x)\) 的唯一零点在 \(x=n/2\)，且在该零点处 \(g'(x)\) 由负变正。

对 \(r\) 作归纳，\(r=1\) 的情形成立。注意由对称性，可设 \(x\le n/2\)。还注意到 \[ g'(x)=\binom{x}{r-1}\cdot\frac{x-r+1}{r}+\binom{n-x}{r-1}\cdot\frac{n-x-r+1}{r}, \] 此式还可重新分组为“两端对称项之差”加“正项”的形式以判断符号。验证 \(x=n/2\) 确为 \(g'(x)\) 的零点是常规计算。注意 \(\binom{x}{r}\) 当 \(x>r-1\) 时关于 \(x\) 递增。结合归纳假设与上式可得：当 \(x>n/2\) 时 \(g'(x)>0\)，当 \(x

1. 先看最简单的 \(r=2\)。此时 \(\binom{x}{2}=\dfrac{x(x-1)}{2}\)，于是 \[ g(x)=\frac{x(x-1)}{2}+\frac{(n-x)(n-x-1)}{2}. \] 展开整理（利用 \(x+(n-x)=n\)）： \[ g(x)=x^2-nx+\frac{n^2-n}{2}=\Big(x-\frac n2\Big)^2+\Big(\frac{n^2-n}{2}-\frac{n^2}{4}\Big). \] 这是开口向上的抛物线，顶点在 \(x=n/2\)，所以 \(x=n/2\) 处取最小值，离 \(n/2\) 越远值越大。
2. 用离散差分代替导数。对整数 \(x\)，比较相邻两值： \[ g(x+1)-g(x)=\binom{x+1}{r}-\binom{x}{r}-\left[\binom{n-x}{r}-\binom{n-x-1}{r}\right]=\binom{x}{r-1}-\binom{n-x-1}{r-1}. \] （这里用了帕斯卡恒等式 \(\binom{x+1}{r}-\binom{x}{r}=\binom{x}{r-1}\)。）
3. 判断符号。\(\binom{\cdot}{r-1}\) 在自变量增大时递增。当 \(x♦

习题 4

我们断言：若 \(G\) 至少有一条边，则 \(\chi(G')=\chi(G)\)。（否则 \(\chi(G)=1\) 而 \(\chi(G')=2\)。）事实上，若 \(f\) 是 \(G\) 的一个正常染色（proper coloring，相邻顶点异色），则令 \(x'\) 的颜色为 \(f(x)+1\)，其中加法按模 \(\chi(G)\) 进行。也就是说，若 \(f(x)=\chi(G)\) 则 \(f(x')=1\)，同时保持 \(x\) 的颜色不变。这就给出了 \(G'\) 的一个用 \(\chi(G)\) 种颜色的正常染色。

1. 当 \(G\) 无边时。\(G\) 全是孤立点，\(\chi(G)=1\)（一种颜色够）；但 \(G'\) 里出现了相邻的对，需要 \(2\) 种颜色，故 \(\chi(G')=2\)。这是唯一的例外。
2. 当 \(G\) 至少有一条边时 \(\chi(G)\ge 2\)。先把 \(G\) 用 \(\chi(G)\) 种颜色 \(1,2,\dots,\chi(G)\) 正常染好，记为 \(f\)。
3. 给影子定色：\(f(x')\equiv f(x)+1\pmod{\chi(G)}\)（颜色 \(\chi(G)\) 的下一个回到 \(1\)）。
4. 验证没有冲突。原图内部沿用 \(f\)，正常。任意一对相邻的影子 \(x',y'\)：因为 \(x,y\) 在 \(G\) 中相邻所以 \(f(x)\ne f(y)\)，整体加 \(1\) 取模后仍不同，故 \(f(x')\ne f(y')\)。再看 \(x\) 与某个相邻影子 \(y'\)（\(y\) 是 \(x\) 邻居）：\(f(x)\) 与 \(f(y)+1\)，因 \(\chi(G)\ge 2\) 且 \(f(x)\ne f(y)\)，这种“错位加 1”恰好让冲突错开。于是 \(\chi(G)\) 种颜色就够染 \(G'\)，故 \(\chi(G')\le\chi(G)\)。又 \(G\) 是 \(G'\) 的子图，\(\chi(G')\ge\chi(G)\)，两者相等。♦

习题 5

(a) 不妨设 \(k=\chi(G)\le\chi(H)\)。取 \(G\) 的任一 \(k\)-染色 \(f\)。令顶点 \((g,h)\) 的颜色都等于 \(f(g)\)。这给出了 \(G\times H\) 的一个正常 \(k\)-染色，因为该图中两顶点相邻当且仅当它们的 \(G\)-坐标在 \(G\) 中相邻。

(b) 是的。\(G\times G\) 中形如 \((g,g)\) 的顶点所导出的子图同构于 \(G\)，所以为给该子图染色确实需要 \(\chi(G)\) 种颜色。

1. (a) 只看第一坐标染色。给 \((g,h)\) 涂上 \(f(g)\) 这种颜色（完全无视 \(h\)）。
2. 为什么正常？若 \((g_1,h_1)\) 与 \((g_2,h_2)\) 相邻，则按定义 \(g_1,g_2\) 在 \(G\) 中相邻，于是 \(f(g_1)\ne f(g_2)\)，两个顶点颜色不同。用了 \(k=\chi(G)\) 种颜色，故 \(\chi(G\times H)\le\chi(G)\)。对称地也 \(\le\chi(H)\)。
3. (b) 下界。把注意力放在“对角顶点” \((g,g)\)。两个对角顶点 \((g,g),(g',g')\) 相邻 \(\iff\) \(gg'\) 在 \(G\) 中相邻（两个坐标条件同时成立，但两坐标相同）。所以对角顶点导出的子图就是 \(G\) 本身，染它至少要 \(\chi(G)\) 色。结合 (a) 得 \(\chi(G\times G)=\chi(G)\)。♦

习题 6

用如下贪心方式给顶点染 \([4]=\{1,2,3,4\}\) 中的颜色：按顶点度数不增的顺序逐个处理，对每个顶点使用能保持染色正常的最小颜色。设 \(d_1\ge d_2\ge\cdots\ge d_{10}\) 为各度数，则对第 \(i\) 个顶点，被禁用的颜色数为 \(\min(d_i,\,i-1)\)。确实如此：顶点 \(i\) 有 \(d_i\) 个邻居，其中至多 \(i-1\) 个在它之前被染色。在本题的图中，\(\max_{i=1}^{10}\min(d_i,i-1)=3\)，且最大值在第四个顶点处取得。所以禁用颜色从不超过三种，这证明了 \(\chi(G)\le 4\)。

1. 为什么禁用色数是 \(\min(d_i,i-1)\)？染第 \(i\) 个顶点时，会“撞色”的只能是它已经染过的邻居。它的邻居共 \(d_i\) 个，但已染过的顶点总共才 \(i-1\) 个，两者取较小者，就是已染邻居数的上界，也就是被禁颜色数的上界。
2. 按度数从大到小排很关键。度数大的顶点排在前面，那时已染顶点少（\(i-1\) 小），所以即使邻居多也被 \(i-1\) 卡住；度数小的排在后面，又被 \(d_i\) 卡住。两头都被压低。
3. 具体到本图。逐个算 \(\min(d_i,i-1)\)，最大值出现在第四个顶点且等于 \(3\)。所以任何顶点染色时被禁的颜色都 \(\le 3\) 种，\(4\) 种颜色里总有一种可用，贪心永不卡壳，\(\chi(G)\le 4\)。♦

习题 7

为说明 \(\chi(G)=4\) 可能，取三条顶点不相交的边和一个三角形。这个不连通的图因含三角形而色数为三。再把这 \(9\) 个顶点全部连到第十个顶点，便造出一个具有指定度数序列、色数为四的图 \(G\)。

为说明 \(\chi(G)=3\) 可能，取三份顶点不相交的 \(K_{2,1}\)，并把它们的全部 \(9\) 个顶点连到一个新的第十个顶点。

最后，若 \(\chi(G)=2\) 也可能，则会存在具有此度数序列的二部图。这是不可能的，因为度数为九的那个顶点必须与其余所有顶点相连。

1. 造一个 \(\chi=4\) 的图。“三条不相交的边 + 一个三角形”共 \(3\times2+3=9\) 个顶点；三角形要 \(3\) 色，所以这堆零件色数为 \(3\)。再添第十个顶点连向全部 \(9\) 个：它与三角形三色全相邻，必须用第 \(4\) 色。故 \(\chi=4\)。
2. 造一个 \(\chi=3\) 的图。\(K_{2,1}\) 是一条“路径”\(\bullet-\bullet-\bullet\)（二部图，色数 \(2\)）。三份共 \(9\) 个顶点。第十个顶点连全部 \(9\) 个：它要避开邻居颜色，因每份只用 \(2\) 色，整体 \(3\) 色即可。故 \(\chi=3\)。
3. 为何 \(\chi=2\) 不行。\(\chi=2\) 等价于图是二部图。但度数 \(9\) 的顶点在十顶点图中与其余每个顶点都相邻；二部图中它的所有邻居必须同在另一侧，于是另一侧九个顶点之间不能有边——可这与给定度数序列（其它顶点也要有边）矛盾。所以不可能是二部图，\(\chi\ne 2\)。♦

习题 8

图 6.15 表明 \(\binom{n-1}{2}+1\) 条边是可能的。另一方面，更多的边则不可能。事实上，假设 \(G\) 至少有 \(\binom{n-1}{2}+2\) 条边且有一个割点 \(x\)。那么 \(G-x\) 有 \(n-1\) 个顶点、至少 \(\binom{n-2}{2}+1\) 条边，且不连通。这是不可能的，正如补充习题 5 所要求证明的那样。

1. 下界（构造能达到）。\(K_{n-1}\) 有 \(\binom{n-1}{2}\) 条边，再加挂吊点的那 \(1\) 条，共 \(\binom{n-1}{2}+1\) 条。去掉 \(x\) 就把吊点和 \(K_{n-1}\) 其余部分分开，故 \(x\) 是割点，图连通但非 2-连通。
2. 上界（不能更多）。反设有这样的图却有 \(\ge\binom{n-1}{2}+2\) 条边。它非 2-连通，必有割点 \(x\)。
3. 删去割点估算。\(x\) 这一个顶点最多带 \(n-1\) 条边。删 \(x\) 后剩 \(n-1\) 个顶点，边数 \(\ge\big(\binom{n-1}{2}+2\big)-(n-1)\)。利用恒等式 \(\binom{n-1}{2}-(n-1)=\binom{n-2}{2}-1\)，整理得至少 \(\binom{n-2}{2}+1\) 条边，而且 \(G-x\) 不连通（割点的定义）。
4. 导出矛盾。补充习题 5 已证：\(n-1\) 个顶点、有 \(\binom{n-2}{2}+1\) 条边的图必定连通。这与 \(G-x\) 不连通矛盾。故边数不能超过 \(\binom{n-1}{2}+1\)。♦

习题 9

(a) 我们用颜色 \(1,2,\cdots,k+1\)，并按如下贪心方式使用：逐个给 \(G\) 的顶点染色，每一步用能用的最小颜色，即不出现在当前顶点的邻居中的最小颜色。由于 \(G\) 的最大度数为 \(D\)，任何一步被禁用的颜色都不超过 \(D\) 种，所以每个顶点总有至少一种颜色可用。

(b) 完全图 \(K_n\) 与奇圈 \(C_{2m+1}\) 具有这一性质。

1. (a) 贪心永不卡。用 \(D+1\) 种颜色。染某顶点时，它至多 \(D\) 个邻居，最多禁 \(D\) 种颜色，第 \(D+1\) 种必有空位。故 \(\chi(G)\le D+1\)。
2. (b) 完全图取等。\(K_n\) 中每点度数 \(D=n-1\)，两两相邻必须两两异色，需 \(n=D+1\) 色，恰好取等。
3. 奇圈取等。\(C_{2m+1}\)（奇数个顶点的环）每点度数 \(D=2\)。它不能 \(2\) 染（环长奇数，沿环交替 \(1,2,1,2,\dots\) 回到起点会撞色），需 \(3=D+1\) 色，取等。♦

习题 10（Brooks 定理）

(a) 我们断言：若 \(G\) 既不是完全图，也不是奇圈，则 \(\chi(G)\le k\)，其中 \(k=D(G)\) 为最大度数。

为证此，注意若 \(G\) 有一个度数小于 \(k\) 的顶点 \(v\)，则对顶点数作归纳即可：删去 \(v\) 得 \(G-v\)，由归纳假设它可用至多 \(k\) 种颜色正常染色；由于 \(v\) 在 \(G\) 中邻居少于 \(k\) 个，总有一种颜色可给 \(v\)。这就给出 \(G\) 的不超过 \(k\) 色的正常染色。

剩下要处理 \(G\) 所有顶点度数都等于 \(k\) 的情形，即 \(G\) 为 \(k\)-正则。可设 \(k\ge 3\)，否则命题或平凡成立，或 \(G=K_2\)、\(G=C_{2m+1}\)。

此时取 \(G\) 中距离为二的两个顶点 \(b,c\)。这样的两点必存在，否则 \(G\) 要么是完全图、要么非 \(k\)-正则。设 \(a\) 为 \(b,c\) 的公共邻居。由于 \(G\) 是 3-连通的，\(G-b-c\) 连通；既连通，它就有一个生成树（spanning tree）子图 \(T\)。把 \(T\) 的边都定向指向 \(a\)。现按如下方式用 \([k]\) 的颜色染 \(G\)：先染 \(b\)，再染 \(c\)，然后以任意顺序染其余顶点，只要保证“若 \(x\) 到 \(a\)（沿 \(T\) 的有向边）的距离大于 \(y\) 到 \(a\) 的距离，则 \(x\) 先于 \(y\) 被染”。于是 \(a\) 最后被染。（原书图 6.16 给出一个 \(4\)-正则图的具体例子：先染 \(b,c\)，再依次染各类顶点，最后染汇点 \(a\)。）每一步用能保持正常的最小颜色。则 \(b,c\) 都得颜色 \(1\)。除 \(a\) 外的其它顶点被染时，至多有 \(k-1\) 个已染邻居。最后 \(a\) 被染时虽有 \(k\) 个已染邻居，但其中两个 \(b,c\) 同色，故实际占用颜色不超过 \(k-1\) 种，仍有颜色可用。于是全部顶点都能只用 \([k]\) 染色。

(b) 现设 \(G\) 不是 3-连通。若 \(G\) 不是 2-连通，则有割点 \(w\) 使 \(G-w\) 不连通。设 \(A\) 为 \(G-w\) 的一个连通分支，\(B=G-w-A\)。由顶点数归纳，\(A\cup w\) 与 \(B\cup w\) 都有正常 \(k\)-染色。置换颜色使 \(w\) 在两者中同色，便拼成 \(G\) 的正常染色。

剩下 \(G\) 是 2-连通但非 3-连通的情形：存在两个顶点 \(x,y\) 使 \(G-x-y\) 不连通。于是有 \(G\) 的两个导出子图 \(G_1,G_2\)，满足 \(G_1\cup G_2=G\) 且 \(G_1\cap G_2=\{x,y\}\)。注意 \(x,y\) 在每个 \(G_i\) 中都至少有一个邻居，否则 \(G\) 非 2-连通。考虑 \(G_1\cup(x,y)\) 与 \(G_2\cup(x,y)\)（若边 \((x,y)\) 不存在就补上）。由上一句可知这两个图中每个顶点度数都至多 \(k\)，故它们都有正常 \(k\)-染色。两个染色中 \(x,y\) 因相邻而异色；置换颜色使 \(x\) 在两边同色、\(y\) 也在两边同色，即得 \(G\) 的正常染色。

总之，我们证明了：若 \(G\) 既非完全图也非奇圈，则 \(\chi(G)=k\)，\(k\) 为 \(G\) 的最大度数。这是 Brooks 的著名定理 [21]。

1. 有度数 < k 的顶点 \(v\)：归纳。删 \(v\) 把问题变小，归纳染好 \(G-v\)；\(v\) 不到 \(k\) 个邻居，最多禁 \(k-1\) 色，第 \(k\) 色可用。
2. 处处 k-正则：制造“省一色”的机会。取距离 \(2\) 的两点 \(b,c\)（不相邻但有公共邻居 \(a\)）。\(b,c\) 不相邻，可同染颜色 \(1\)。
3. 用生成树排出染色顺序。\(G-b-c\) 连通（靠 3-连通保证），取它的生成树 \(T\)，把所有边指向 \(a\)。按“离 \(a\) 越远越先染、\(a\) 最后染”的顺序贪心。这样除 \(a\) 外每个点被染时，总有至少一个“朝 \(a\) 方向”的邻居还没染，已染邻居 \(\le k-1\)，有色可用。
4. 汇点 \(a\) 的关键。\(a\) 虽有 \(k\) 个已染邻居，但 \(b,c\) 都涂了颜色 \(1\)，邻居实际只占了 \(\le k-1\) 种颜色，所以 \(a\) 也有色可用。全程只用了 \(k\) 色。
5. (b) 连通度不足时拆开拼回。若有割点 \(w\)：把图沿 \(w\) 拆成两块，各自归纳 \(k\)-染色，再旋转颜色让 \(w\) 两边同色，拼起来。若有割对 \(\{x,y\}\)：拆成 \(G_1,G_2\) 只共享 \(x,y\)，各补一条 \(xy\) 边后归纳染色（补边后度数仍 \(\le k\)），再旋转颜色让 \(x,y\) 两边各自对齐。♦

习题 11

设 \(A_i\) 为“技能 \(i\) 只在一个班次可用”的排班集合。则 \[ |A_i|=2\cdot 2^{n-10}=2^{n-9}, \] 其中 \(n\) 是公司的工人数。确实如此：把具有技能 \(i\) 的 \(10\) 名工人安排坏的方式有两种（全排第一班，或全排第二班），其余 \(n-10\) 名工人有 \(2^{n-10}\) 种排法。因此 \[ \Big|\bigcup_i A_i\Big|\le\sum_i|A_i|=500|A_i|=500\cdot 2^{n-9}<2^n, \] 因为 \(2^9=512\)。于是“至少有一项技能在两班次中没有都出现”的排班数，小于全部排班数 \(2^n\)。所以必然存在一个好的排班。

1. 定义坏事件。\(A_i=\{\)技能 \(i\) 没有同时出现在两班\(\}\)，即掌握技能 \(i\) 的 \(10\) 人全在同一班。
2. 数 \(|A_i|\)。这 \(10\) 人“抱团”有 \(2\) 种（全一班 / 全二班）；其余 \(n-10\) 人随便排，\(2^{n-10}\) 种。相乘 \(|A_i|=2^{n-9}\)。
3. 并集上界。“至少一项技能坏掉”\(=\bigcup_iA_i\)。由 \(|\bigcup A_i|\le\sum|A_i|\)（不重复计也只会更小）得 \(\le 500\cdot2^{n-9}\)。
4. 关键不等式。\(500<512=2^9\)，所以 \(500\cdot2^{n-9}<2^9\cdot2^{n-9}=2^n\)。坏排班数 \(<\) 全部排班数，故至少一种排班不属于任何 \(A_i\)——它就是好排班。♦

习题 12

取由 \(F\) 中各边的补集构成的超图 \(F^c\)，可见 \(F^c\) 中任意两条边都不互不相交。因此由定理 6.29 与 6.30，\(|F^c|=|F|\le 2^{n-1}\)。

1. 取补。对 \(F\) 中每个集合 \(X\)，看它的补 \(X^c=[n]\setminus X\)。取补是一一对应，故 \(|F^c|=|F|\)。
2. 条件翻译。“\(X\cup Y\ne[n]\)” \(\iff\) “\(X^c\cap Y^c\ne\varnothing\)”（并不满当且仅当补集有公共元素）。所以 \(F^c\) 是一个相交族：任意两个集合都有公共元素。
3. 套定理。定理 6.29/6.30 给出相交族大小上界 \(\le 2^{n-1}\)（道理是：每对互补集合 \(\{X^c,(X^c)^c\}\) 中至多取一个，否则两者不相交；这样的互补对共 \(2^{n-1}\) 对）。于是 \(|F|=|F^c|\le 2^{n-1}\)。♦

习题 13

若 \(n=2m+1\)，令 \(F\) 由 \([n]\) 的所有至少含 \(m+1\) 个顶点的边组成。其中任意两条边都因太大而不能不相交。若 \(n=2m\)，令 \(F\) 由 \([n]\) 的所有至少含 \(m+1\) 个顶点的边，以及所有含 \(m\) 个顶点且包含顶点 \(n\) 的子集组成。注意，两种情形下，我们都从定理 6.29 证明里造出的每一对中恰好取一个顶点（集合）。

1. \(n=2m+1\)（奇数）：取所有“过半大”的集合。即大小 \(\ge m+1\) 的全部子集。两个大小都 \(\ge m+1\) 的集合放进 \(2m+1\) 个元素里，鸽笼必有重叠（\((m+1)+(m+1)=2m+2>2m+1\)），故相交。这样的子集恰好占全部 \(2^n\) 个子集的一半，共 \(2^{n-1}\) 个。
2. \(n=2m\)（偶数）：边界要小心。大小 \(>m\) 的全取（任两个相交，因 \(2(m+1)>2m\)）；大小恰为 \(m\) 的对半集合，两个可能恰好互补而不相交，故只取其中“包含固定元素 \(n\)”的那一半。
3. 为什么恰好 \(2^{n-1}\)。把所有子集按“与其补集配对”分成 \(2^{n-1}\) 对，每对里我们的规则恰好选了一个：相交族最多每对取一个，这里取满，故 \(|F|=2^{n-1}\)，达到上界。♦

习题 14

不能。假设它能，设 \(X\) 为 \(F\) 中大小最小的边。不妨设 \(X=[k]\)。那么对每个 \(i\in[k]\)，\(F\) 中必有一条边 \(Y_i\) 不含 \(i\)（否则 \(F\) 中所有边的交就含 \(i\)）。然而这意味着 \[ X\cap Y_1\cap Y_2\cdots\cap Y_k=\varnothing, \] 与假设矛盾。注意此结论有一个几何对应物，称为 Helly 定理：若在 \(k+1\) 维欧氏空间中给定 \(n\ge k+1\) 个凸集，且其中任意 \(k+1\) 个都有公共点，则全部都有公共点。

1. 反证 + 取最小边。设全体交为空。取 \(F\) 中最小的边 \(X\)，记 \(X=[k]=\{1,\dots,k\}\)。
2. 每个元素都被某条边“漏掉”。若某元素 \(i\in X\) 被 \(F\) 的每条边包含，则 \(i\) 属于全体的交，矛盾于“交为空”。所以对每个 \(i\in[k]\)，存在边 \(Y_i\) 不含 \(i\)。
3. 凑出空交。看 \(X\cap Y_1\cap\cdots\cap Y_k\)：\(X\) 的元素只有 \(1,\dots,k\)；元素 \(i\) 被 \(Y_i\) 排除。故没有任何元素能活下来，交为空。但这 \(k+1\) 个集合两两相交却交为空，与题设“任意若干个相交”冲突，矛盾。♦

习题 15

把整数 \(n\) 染红，若它恰好被 \(7\) 与 \(17\) 之一整除；否则染蓝。我们证明该染色满足要求。

设我们的染色含有一个长度为 \(18\) 的单色等差数列 \(A\)。先设 \(A\) 的公差 \(d\) 被 \(17\) 整除。那么为使 \(A\) 单色，\(A\) 的项要么全被 \(7\) 整除、要么全不被 \(7\) 整除。前者不可能，因为那要求 \(d\) 至少是 \(7\cdot17=119\)，从而 \(a_{18}=2142\)。同理 \(d\) 不能被 \(7\) 整除，这意味着 \(A\) 的前七项中恰有一项被 \(7\) 整除。这排除了“\(A\) 没有项被 \(7\) 整除”的可能，所以 \(d\) 不能被 \(17\) 整除。

因此，\(A\) 的前 \(17\) 项中恰有一项被 \(17\) 整除。若 \(d\) 被 \(7\) 整除，则证毕，因为 \(A\) 的项要么全被 \(7\) 整除要么全不，于是总存在两项模 \(17\) 不同余、却模 \(7\) 同余（颜色不同）。若 \(d\) 不被 \(7\) 整除，则数列中既有不被 \(7\) 也不被 \(17\) 整除的项，又有只被其中之一整除的项，与 \(A\) 单色的假设矛盾。

1. 颜色只取决于“被 7、被 17 的整除情况”。红 = 恰好被其中一个整除（被 7 不被 17，或被 17 不被 7）；蓝 = 两个都被或两个都不被。
2. 等差数列里“被 7 整除”的项怎么分布。长度 \(18\) 的等差数列，若公差 \(d\) 不被 \(7\) 整除，则每连续 \(7\) 项里被 \(7\) 整除的项数恰为 \(1\)。前 \(18\) 项里就有约 \(2\) 到 \(3\) 项被 \(7\) 整除，必然出现“有的项被 7、有的不被”。
3. 用范围卡住“全被整除”。若想让所有 \(18\) 项都被 \(7\) 整除，公差就得是 \(7\) 的倍数；再要同时控制 \(17\)，公差就大到 \(119\)，使末项 \(a_{18}\) 超出允许范围（达到 \(2142\)），不被允许。
4. 逐情况导出非单色。无论公差与 \(7,17\) 的整除关系如何组合，前 \(7\) 项（或前 \(17\) 项）里“被 7/被 17”的状态都会变化，于是必出现两项颜色不同（一红一蓝），所以这 \(18\) 项不可能单色。矛盾，故该染色合格。♦

习题 16

不妨设顶点 \(A\) 邻接至少三条红边。设这些边的另一端点为 \(B,C,D\)。若这三点中任意两点之间有一条红边，则该边的端点与 \(A\) 构成一个红三角形。否则 \(BCD\) 是一个蓝三角形。

1. 抽屉原理找“三同色边”。顶点 \(A\) 连出 \(5\) 条边，两色分，必有一色 \(\ge\lceil5/2\rceil=3\) 条。不妨是红色，端点 \(B,C,D\)。
2. 看 \(B,C,D\) 之间的三条边。若其中有一条红边，比如 \(BC\) 红，则 \(A,B,C\) 三条边 \(AB,AC,BC\) 全红，得红三角形。
3. 否则全蓝。若 \(BC,BD,CD\) 都不是红，那它们全蓝，\(BCD\) 就是蓝三角形。两种情况必居其一。♦

习题 17

我们对 \(k+l\) 作归纳。若 \(k+l=2\)，即 \(k=l=1\)，则 \(R(k,l)=2\)，命题成立。假设命题对 \(k+l-1\) 成立，即 \(R(k,l-1)\) 与 \(R(k-1,l)\) 都存在，来证 \(k+l\) 的情形。

只需证明存在一个满足要求的整数，因为非空的正整数集中总有最小元。我们断言 \[ n=R(k,l-1)+R(k-1,l)-1 \] 就是这样的整数。设 \(v\) 为 \(K_n\) 的任一顶点，把 \(K_n\) 的每条边染红或蓝。那么 \(v\) 邻接的边中，要么有至少 \(R(k,l-1)\) 条蓝边，要么有至少 \(R(k-1,l)\) 条红边。前一种情形中，设 \(v\) 邻接的蓝边的另一端点构成完全图 \(X\)。则 \(X\) 有 \(R(k,l-1)\) 个顶点，于是它要么含红 \(K_k\)（证毕），要么含蓝 \(K_{l-1}\)（把 \(v\) 加进这份 \(K_{l-1}\) 即得蓝 \(K_l\)，再次证毕）。第二种情形可类似处理。

1. 归纳基底。\(R(1,1)=2\)：在 \(K_2\) 里随便染，红 \(K_1\)（一个点）总在。
2. 取一点 \(v\)，按抽屉分边。令 \(n=R(k,l-1)+R(k-1,l)-1\)。\(v\) 连出 \(n-1=R(k,l-1)+R(k-1,l)-2\) 条边。若蓝边 \(
3. 蓝边多的情形。取这些蓝边的对端构成 \(X\)，\(|X|\ge R(k,l-1)\)。由 \(R\) 的定义，\(X\) 含红 \(K_k\)（直接完成）或蓝 \(K_{l-1}\)；后者加上 \(v\)（\(v\) 到 \(X\) 全是蓝边）成蓝 \(K_l\)。
4. 红边多的情形对称。同理得红 \(K_k\) 或蓝 \(K_l\)。两路都成功，故这样的有限 \(n\) 存在。♦

习题 18

不妨设顶点 \(A\) 邻接至少六条红边。看这些边的另一端点。若它们之间有任意一条红边，则证毕（得红三角形）。若没有，则它们构成一份 \(K_6\)，其中每条边为蓝色或绿色。此时应用上一题的结论即可。

1. 三色抽屉。顶点 \(A\) 连出 \(16\) 条边，三色分，必有一色 \(\ge\lceil16/3\rceil=6\) 条。设红色 \(\ge6\)，端点集 \(S\)，\(|S|\ge6\)。
2. 若 \(S\) 内有红边。设 \(BC\) 红（\(B,C\in S\)），则 \(A,B,C\) 全红 → 红三角形。
3. 若 \(S\) 内无红边。则 \(S\) 上 \(6\) 个点之间只用蓝、绿两色，构成两色染色的 \(K_6\)。由习题 16（\(R(3,3)\le6\)）必含单色（蓝或绿）三角形。两情况都得到单色三角形。♦

习题 19

若编码 \(N\) 是前缀无关的（prefix-free，即没有码字是另一码字的前缀），则解码消息时不会出现这样的时刻：我们可以停下得到码字 \(A\)，也可以继续下去得到码字 \(B\)——因为那意味着 \(A\) 是 \(B\) 的前缀。反过来，若 \(N\) 不是前缀无关的，\(F\) 是 \(G\) 的前缀，我们尝试从以 \(F\) 的各位开头的消息解码时，就无法立刻知道应当停下取 \(F\) 还是继续取 \(G\)。因此 \(N\) 不是即时的（instantaneous）。

1. 前缀无关 ⇒ 即时。若读入恰好拼成码字 \(A\)，则不可能再继续拼成另一码字 \(B\)，否则 \(A\) 是 \(B\) 的前缀，违反前缀无关。故读到 \(A\) 末位即可断定就是 \(A\)，立刻输出。
2. 非前缀无关 ⇒ 非即时。设码字 \(F\) 是码字 \(G\) 的前缀。读完 \(F\) 的位时，无法判断该停（输出 \(F\)）还是继续（可能凑成 \(G\)），必须往后看，所以不即时。两方向都证完，等价成立。♦

习题 20

矩阵的模式回避（pattern avoidance）思想及最早的结果来自 [35]。

(a) 由抽屉原理，若有 \(n+1\) 个元素等于 \(1\)，则其中必有两个在同一行（或同一列，统称同一“线”）。因此 \(f(n,B)=n\)。

(b) 我们证一个更一般的命题。定义 \(f(n,m,B)\) 为：一个 \(n\times m\) 的 \(0\text{-}1\) 矩阵在回避 \(B\) 的前提下最多能含的 \(1\) 的个数。我们断言：若 \(B\) 是 \(2\times2\) 单位矩阵，则 \(f(n,m,B)=n+m-1\)。这么多 \(1\) 是可达的，例如把第一行和第一列全填 \(1\)。为证不能更多，对 \(n+m\) 作归纳。\(n+m=2\) 时命题成立。设命题对 \(n+m-1\) 成立，\(A\) 为回避 \(B\) 的 \(n\times m\) 矩阵，假设 \(A\) 有 \(n+m\) 个 \(1\)。若 \(A\) 有一行或一列至多含一个 \(1\)，删去这条线，由归纳假设证毕。否则每行每列都至少含两个 \(1\)。由于 \(1\) 的总数为 \(n+m\)，这意味着每行每列恰含两个 \(1\)。即 \(1\) 的总数 \(2n=n+m=2m\)，迫使 \(n=m\)。这时 \(A\) 是两个不同置换矩阵之和。（请读者直接证明此事，或许可借助二部图；更一般的命题见引理 10.6。）这两个置换矩阵不可能都对应递减置换，故其中之一对应一个含“非逆序”（non-inversion）的置换。该矩阵就会含 \(B\)。

1. (a) 一行/一列就是 B。这里的 \(B\)（一条线上两个 \(1\)）回避意味着每条线至多一个 \(1\)；\(n\) 行最多 \(n\) 个 \(1\)，多一个就有两个同行，故 \(f(n,B)=n\)。
2. (b) 构造达到 \(n+m-1\)。把第一行 \(m\) 个、第一列 \(n\) 个全填 \(1\)，左上角重复一次，共 \(m+n-1\) 个 \(1\)，且不含“左上右下对角”图案（所有 \(1\) 都靠边）。
3. 归纳证不能更多。若有 \(n+m\) 个 \(1\)：若某行/列只有 \(\le1\) 个 \(1\)，删掉它，规模减一，归纳得矛盾。否则每行每列 \(\ge2\) 个 \(1\)，逐行加起来 \(\ge2n\) 个、逐列 \(\ge2m\) 个；但总数恰 \(n+m\)，于是 \(2n\le n+m\le\) 总数 \(=n+m\)，逼出每行每列恰 \(2\) 个、\(n=m\)。
4. 恰两个 1 ⇒ 必含对角图案。每行每列恰两个 \(1\) 的方阵是两个置换矩阵之和。两个置换不可能都是“完全递减”的（递减置换的矩阵恰好是反对角，且只有一个），故必有一个置换含“升序对” \(i♦

习题 21

(a) 对 \(n\) 作归纳。由于 \(A_n\) 回避 \(B\)，\(A_{n+1}\) 含 \(B\) 的唯一可能就是 \(A_{n+1}\) 中有一份 \(B\) 起始于左上象限而终止于另一象限。容易看出这是不可能的。

(b) 设 \(g(n)\) 为 \(A_n\) 中 \(1\) 的个数。则 \(g(0)=1\)，且当 \(n\ge0\) 时 \(g(n+1)=2g(n)+2^{n-2}\)。解此递推得 \[ 2g(n)=2^n+n\,2^{n-2}. \] 由于 \(A_n\) 的大小为 \(2^n\times2^n\)，令 \(m=2^n\)，便有 \(f(m,B)=\Omega(m\log m)\)。

1. (a) 分块归纳。\(A_{n+1}\) 由 \(A_n\) 拼成四个象限。要含 \(B\) 只能跨象限，但构造方式让跨象限的 \(B\) 无法成形，所以 \(A_{n+1}\) 也回避 \(B\)。
2. (b) 列递推。\(A_{n+1}\) 含 \(A_n\) 的两份（\(2g(n)\)），再加拼接产生的 \(2^{n-2}\) 个 \(1\)，故 \(g(n+1)=2g(n)+2^{n-2}\)。
3. 解出闭式。展开递推得 \(2g(n)=2^n+n2^{n-2}\)，主项是 \(n2^{n-2}\)。
4. 换成边长 \(m\)。\(m=2^n\Rightarrow n=\log_2 m\)，\(g(n)\approx \tfrac{n}{8}\,2^n=\tfrac{m\log_2 m}{8}\)，即 \(\Omega(m\log m)\)，超过线性。♦

习题 22

本题及随后两题的结果出自 Adam Marcus 与 Gábor Tardos 的论文 [56]，并被用来证明一个二十五年之久的猜想。

我们断言答案是 \(f(\lceil n/k^2\rceil,B)\)。称 \(A\) 的一个块为零块，若其元素全为零。构造矩阵 \(A'\)，把 \(A\) 的所有零块换成一个 \(0\)、所有非零块换成一个 \(1\)。若 \(A'\) 含 \(B\)，则 \(A\) 也含 \(B\)，结论随之成立。注意这里确实需要 \(B\) 是置换矩阵这一事实——因此它每行每列只有一个 \(1\)。

1. 压缩。把 \(A\) 划成边长 \(k^2\) 的块，整张图缩成 \(\lceil n/k^2\rceil\times\lceil n/k^2\rceil\) 的 \(A'\)：非零块→\(1\)，零块→\(0\)。
2. 压缩不会“凭空造出 B”。反过来想：若 \(A'\) 出现 \(B\) 的 \(1\)-图案，每个对应位置都是非零块，从每个非零块各取一个真正的 \(1\)，因 \(B\) 是置换矩阵（每行每列一个 \(1\)）这些 \(1\) 的行列互不冲突，就在 \(A\) 里拼出真正的 \(B\)。但 \(A\) 回避 \(B\)，故 \(A'\) 也回避 \(B\)。
3. 结论。因此 \(A'\) 的 \(1\) 数（非零块个数）\(\le f(\lceil n/k^2\rceil,B)\)。♦

习题 23

反设结论不成立。一个块能含有非零元素的行有 \(\binom{k^2}{k}\) 种 \(k\) 元行组，于是由抽屉原理，会存在某一组 \(k\) 行，它在 \(k\) 个不同的块中都含非零元素。然而这意味着 \(A'\) 有一个由非零块构成的 \(k\times k\) 子矩阵 \(M\)。因此 \(A\) 含有所有 \(k\times k\) 矩阵，包括 \(B\)。确实，\(M\) 本质上模拟了一个每个元素都为 \(1\) 的 \(k\times k\) 矩阵，而后者当然包含所有 \(k\times k\) 矩阵。类似地，在任一块列中，至多有 \((k-1)\binom{k^2}{k}\) 个宽块。

1. 一个块里非零行的“指纹”。每个块有 \(k^2\) 行；一个高块在其中占用 \(k\) 行作非零，这组 \(k\) 行是 \(\binom{k^2}{k}\) 种可能之一。
2. 抽屉逼出 k 个块共用指纹。若同一块行里高块超过 \((k-1)\binom{k^2}{k}\) 个，则按指纹分类，必有某个 \(k\)-行指纹被 \(\ge k\) 个块共用——即这组 \(k\) 行在 \(k\) 个不同块里都非零。
3. 拼出全 1 子矩阵。这 \(k\) 行与那 \(k\) 个块的列，交出一个 \(k\times k\) 的“全非零块”子矩阵 \(M\)。从每个非零位取 \(1\)，相当于一个 \(k\times k\) 全 \(1\) 矩阵，它含任意 \(k\times k\) 模式，自然含置换矩阵 \(B\)。
4. 矛盾。这与 \(A\) 回避 \(B\) 冲突。故高块数 \(\le(k-1)\binom{k^2}{k}\)。列方向同理限制宽块。♦

习题 24

首先，若 \(n\) 不被 \(k^2\) 整除，就在 \(A\) 的最后几行与几列填 \(1\)，使 \(A\) 中未被 \(1\) 填满的子矩阵 \(A_s\) 大小为 \(k^2\lfloor n/k^2\rfloor\times k^2\lfloor n/k^2\rfloor\)。这至多增加 \(2k^2n=O(n)\) 个 \(1\)。从此可设 \(n\) 被 \(k^2\) 整除，即 \(A_s=A\)。

前两题表明：若 \(A\) 回避 \(B\)，\(B\) 是 \(k\times k\) 置换矩阵，则非零块至多 \(f(n/k^2)\) 个，且其中每块行至多 \((k-1)\binom{k^2}{k}\) 个高块，每块列至多 \((k-1)\binom{k^2}{k}\) 个宽块。若一个块既不高也不宽，则其 \(1\) 的个数至多 \((k-1)^2\)，因为这种块的 \(1\) 至多落在 \(k-1\) 行、\(k-1\) 列中。我们现可汇总 \(A\) 中 \(1\) 的个数：

• 高块或宽块至多 \(2\cdot\frac{n}{k^2}(k-1)\binom{k^2}{k}\) 个，每个含至多 \(k^4\) 个 \(1\)，合计少于 \(2nk^3\binom{k^2}{k}\) 个 \(1\)；
• 既不高也不宽的非零块至多 \(f(n/k^2,B)\) 个，每个含至多 \((k-1)^2\) 个 \(1\)，合计至多 \((k-1)^2 f(n/k^2,B)\) 个 \(1\)；
• 其余必为不含 \(1\) 的零块。

这导出递推式 \[ f(n,B)\le 2nk^3\binom{k^2}{k}+(k-1)^2 f(n/k^2,B), \] 由此用归纳法即可常规地证明我们的命题（\(f(n,B)=O(n)\)）。

1. 把每类块的贡献分别算上界。非零块按“高/宽/都不是”分三类。高块、宽块虽含 \(1\) 多（\(\le k^4\)），但个数被第 \(23\) 题限死；普通非零块个数被第 \(22\) 题（\(\le f(n/k^2,B)\)）限死，但每个含 \(1\) 少（\(\le(k-1)^2\)）。
2. 求和得递推。三类相加：高/宽块贡献 \(<2nk^3\binom{k^2}{k}\)（这是 \(O(n)\) 常数倍），普通块贡献 \(\le(k-1)^2f(n/k^2,B)\)。于是 \[ f(n,B)\le \underbrace{2nk^3\binom{k^2}{k}}_{=cn}+(k-1)^2 f(n/k^2,B). \]
3. 解递推。每递归一层规模缩 \(k^2\) 倍、系数 \((k-1)^2\)。因为 \((k-1)^2♦

习题 25

本结果最先由 Martin Klazar [49] 证明，后经 Vincent Vatter 与 Doron Zeilberger 略作简化（未正式发表）。我们给出的是后者的证明。

设 \(q\) 为长度 \(k\) 的模式，\(p\) 为回避 \(q\) 的 \(n\)-置换。则 \(p\) 的置换矩阵回避 \(q\) 的置换矩阵 \(B_q\)。令 \(M_n(q)\) 为回避 \(B_q\) 的 \(n\times n\) 的 \(0\text{-}1\) 矩阵个数。则 \(S_n(q)\le M_n(q)\)。下面给 \(M_n(q)\) 找上界。

由上一题结论，存在常数 \(b\) 使 \(f(n,B_q)\le bn\)。设 \(A\) 为回避 \(B_q\) 的 \(n\times n\) 矩阵，把 \(A\) 切成 \(2\times2\) 的块（若 \(n\) 为奇数，末端会有较小的块）。若一块不含 \(1\) 就换成 \(0\)，含至少一个 \(1\) 就换成 \(1\)。这得到一个 \(\lceil n/2\rceil\times\lceil n/2\rceil\) 的矩阵，它同样回避 \(B_q\)，故至多有 \(f(\lceil n/2\rceil,B_q)\le b\lceil n/2\rceil\) 个 \(1\)。而且这每个 \(1\) 都来自 \(A\) 的一个非零 \(2\times2\) 块，每块有 \(2^4-1=15\) 种可能。因此 \(M_n(q)\) 满足 \[ M_n(q)\le 15^{b\lceil n/2\rceil}\cdot M_{\lceil n/2\rceil}(q). \] 反复使用此论证直到右端变为 \(M_1(q)=2\)，便得 \(M_n(q)\le 15^{2bn}\)，从而 \(S_n(q)\le 15^{2bn}\)。

1. 置换 → 矩阵。回避模式 \(q\) 的置换对应回避矩阵 \(B_q\) 的置换矩阵，故 \(S_n(q)\le M_n(q)\)（矩阵更多，覆盖了置换）。
2. 2×2 压缩 + 计数。把回避 \(B_q\) 的 \(A\) 压成一半大小的回避矩阵，新矩阵 \(1\) 数 \(\le b\lceil n/2\rceil\)（用 Marcus–Tardos 的线性界）。每个 \(1\) 由原来一个非零 \(2\times2\) 块还原，块有 \(15\) 种花样。所以 \(M_n\le 15^{b\lceil n/2\rceil}M_{\lceil n/2\rceil}\)。
3. 反复减半累乘。不断对半压缩，指数项 \(15^{b(n/2+n/4+\cdots)}=15^{bn}\) 量级；细化常数后得 \(M_n(q)\le 15^{2bn}\)。
4. 收尾。于是 \(S_n(q)\le 15^{2bn}=(15^{2b})^n\)，是单指数级，Stanley–Wilf 成立。♦

习题 26

统计对 \((p,q')\)，其中 \(p\) 是含模式 \(q\) 的 \(n\)-置换，\(q'\) 是 \(p\) 中 \(q\) 的一份拷贝。\(q'\) 的位置有 \(\binom{n}{k}\) 种选择，\(q'\) 的取值有 \(\binom{n}{k}\) 种选择，\(p\) 的其余部分有 \((n-k)!\) 种选择。所以这种对的数目是 \((n-k)!\cdot\binom{n}{k}^2\)。抽屉原理表明，其中至少 \(1/n!\) 属于同一个置换，即至少 \[ \frac{(n-k)!\cdot\frac{(n!)^2}{(k!(n-k)!)^2}}{n!}=\frac{\binom{n}{k}}{k!} \] 个对属于同一个置换。此外，存在回避 \(q\) 的置换，没有任何 \((p,q)\) 对属于它们。因此，存在某个 \(p\)，它含 \(q\) 的出现次数严格大于 \(\dfrac{\binom{n}{k}}{k!}\)。

1. 数所有 (p, q') 对。位置选 \(\binom nk\)、取值选 \(\binom nk\)、其余 \((n-k)!\) 自由排，共 \((n-k)!\binom nk^2\) 个“出现”实例。
2. 平均到每个置换。置换共 \(n!\) 个。平均每个置换含的拷贝数 \(=\dfrac{(n-k)!\binom nk^2}{n!}\)。代入 \(\binom nk=\dfrac{n!}{k!(n-k)!}\) 化简得 \(\dfrac{\binom nk}{k!}\)。
3. 从平均到“严格超过”。有些置换回避 \(q\)（出现次数为 \(0\)），它们把平均往下拉；既然总平均是 \(\dfrac{\binom nk}{k!}\)，那么在“含 \(q\) 的置换”里必有一个出现次数严格大于这个平均值。♦

习题 27

(a) 用顶点表示职位与候选人，把候选人与他能胜任的职位之间连边，得到一个二部图。若 \(aX\) 是图 \(G\) 的一条边，就在该边上写数 \(t_{aX}\)，其中 \(t_{aX}\) 是候选人 \(a\) 愿意接受职位 \(X\) 的最低薪水。回忆第 5 章补充习题 34 定义的图的完美匹配（perfect matching）。经理的任务就是找出 \(G\) 的一个完美匹配，使边上所写数字之和（匹配的成本）最小。

(b) 不会，这种贪心策略不总能得到最好结果。图 6.17 是一个反例：贪心算法给出成本 \(13\) 的匹配，而存在成本 \(12\) 的匹配。

1. (a) 建图。左边职位、右边候选人，能胜任就连边，边权 = 最低可接受薪水。一个“每人恰好配一职、每职恰好配一人”的方案就是完美匹配，目标是最小化总权。
2. (b) 贪心为何失效。贪心先抢全局最便宜的边，可能逼得后面只能用很贵的边补齐匹配。图 6.17：贪心总价 \(13\)，但换一种配法只要 \(12\)。所以贪心在匹配问题上不保证最优。♦

习题 28

\(A\) 与 \(B\) 都是森林。因为 \(A\) 的边更多，它的连通分支更少。所以 \(A\) 必有一条边，其两端点落在 \(B\) 的不同连通分支中，于是这条边可以加进 \(B\) 而不在其中产生圈。

1. 边多 ⇒ 分支少。\(t\) 个顶点的森林若有 \(e\) 条边，则连通分支数 \(=t-e\)。边越多分支越少。故分支数 \(c_A
2. 找跨分支的边。把 \(B\) 的连通分支看成若干“颜色块”。若 \(A\) 的每条边两端都同色（同在 \(B\) 的某分支内），则 \(A\) 的边都不跨块，\(A\) 的分支数会 \(\ge B\) 的分支数，与 \(c_A
3. 加边不成圈。该边连接 \(B\) 的两个不同分支，加进 \(B\) 只是把两块连起来，绝不会形成圈（圈需要两端本就连通）。♦

习题 29

会，此时贪心算法是有效的。考虑县里所有城镇对，取以城镇为顶点的完全图，把每条道路的修建成本写到对应的边上。用第 5 章注记的术语，我们要在此图中找一棵最小成本生成树（minimum-cost spanning tree），即 \(n\) 个顶点上的一棵树，使其边上所写数字之和最小。

设 \(G_j\) 为贪心算法在 \(j\) 步后构建的图。定义即蕴含 \(G_j\) 是森林，而 \(G_{n-1}\) 是树。我们断言 \(K_n\) 的任何其它生成树都不会比 \(G\) 成本更小。事实上，假设 \(c(T)c(t_i)\)。

然而这是矛盾的。事实上，这将意味着对所有 \(j\le i\) 都有 \(c(g_i)>c(t_j)\)。上一题表明：边 \(t_j\)（\(j\le i\)）中至少有一条可以加进 \(G_{i-1}\) 而不产生圈。因此 \(g_i\) 不可能是贪心算法在第 \(i\) 步所选的边——因为那时存在一条更便宜的、可加入而不成圈的边 \(t_j\)，贪心本应优先选它。这一矛盾说明 \(c(T)

1. 建模。城镇是顶点，可修的路是带成本的边，目标是连通全部 \(n\) 个城镇的最便宜的树，即最小生成树。贪心 \(G\) 逐步加边，每步保持森林，第 \(n-1\) 步成树。
2. 反证。设有更便宜的生成树 \(T\)，\(c(T)
3. 找第一处 G 更贵的位置。既然 \(c(T)c(t_i)\)。由排序，对所有 \(j\le i\) 也有 \(c(t_j)\le c(t_i)
4. 用交换引理找矛盾。森林 \(\{t_1,\dots,t_i\}\)（\(i\) 条边）比 \(G_{i-1}\)（\(i-1\) 条边）边多，由第 \(28\) 题，某条 \(t_j\)（\(j\le i\)）能加进 \(G_{i-1}\) 不成圈。这条 \(t_j\) 比 \(g_i\) 便宜，贪心在第 \(i\) 步本应选它而非更贵的 \(g_i\)。与“贪心总选最便宜可行边”矛盾。故不存在更便宜的 \(T\)，贪心最优。♦

返回 全书目录