Appearance
组合数学题目集
概述
本题目集涵盖计数原理、组合恒等式、图论染色、组合极值、高级图论与网络流、拉姆齐与极图、组合几何、概率方法、Pólya 计数、组合数论与加法组合、设计与编码等主题，共 65 题，按基础→进阶→竞赛三级难度编排。
一、容斥原理
题1 [难度：基础]
题目：$1$到$100$中，既不是$2$的倍数也不是$3$ 的倍数的数有多少个？
分析：容斥原理 $|A^c\cap B^c|=N-|A|-|B|+|A\cap B|$。
解答： 设 $A$为$2$ 的倍数，$B$为$3$ 的倍数。 $|A|=\lfloor100/2\rfloor=50$，$|B|=\lfloor100/3\rfloor=33$，$|A\cap B|=\lfloor100/6\rfloor=16$。
所求 $=100-50-33+16=33$。
题2 [难度：进阶]
题目（错排问题）：$n$封信装入$n$个信封，全部装错的方案数$D_n$（错排数）。求 $D_1,D_2,D_3,D_4,D_5$ 及通项公式。
分析：容斥原理推导错排公式。
解答： 容斥原理： $$ D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}. $$
计算： $D_1=1!\cdot(1/0!-1/1!)=1-1=0$。 $D_2=2!\cdot(1-1+1/2)=2\cdot\frac{1}{2}=1$。 $D_3=6\cdot(1-1+1/2-1/6)=6\cdot\frac{1}{3}=2$。 $D_4=24\cdot(1-1+1/2-1/6+1/24)=24\cdot\frac{9}{24}=9$。 $D_5=120\cdot(1-1+1/2-1/6+1/24-1/120)=120\cdot\frac{44}{120}=44$。
递推公式
$D_n=(n-1)(D_{n-1}+D_{n-2})$，$D_1=0,D_2=1$。
题3 [难度：进阶]
题目：$6$ 个人坐圆桌，甲和乙不相邻的坐法有多少种？
分析：圆排列总数减去相邻情况。
解答： $6$ 人圆排列：$(6-1)!=120$ 种。
甲和乙相邻：将甲乙捆绑，视为 $5$个对象圆排列$(5-1)!$。甲乙内部 $2!$种顺序。共$4!\times2!=48$ 种。
不相邻：$120-48=72$ 种。
二、排列组合计数
题4 [难度：基础]
题目：从 $n$个不同元素中取$r$ 个排成一圈（圆排列），有多少种方法？
分析：圆排列（循环排列）公式。
解答： 先取 $r$ 个：$C_n^r$ 种。$r$个元素的圆排列有$(r-1)!$ 种。
总数：$C_n^r\cdot(r-1)!=\dfrac{n!}{r!(n-r)!}\cdot(r-1)!=\dfrac{n!}{r(n-r)!}=P_n^r/r$。
题5 [难度：进阶]
题目：从 $n$种不同物品中允许重复地选取$r$ 个（可重组合），有多少种方法？
分析：可重组合 $H_n^r=C_{n+r-1}^r$（星棒模型）。
解答： 等价于将 $r$个相同的球放入$n$ 个不同的盒子（允许空盒）。
星棒法：$r$个星（球）和$n-1$根棒（隔板），共$r+n-1$个位置选$r$个放星（或选$n-1$ 个放棒）。
$$ H_n^r=\binom{r+n-1}{r}=\binom{r+n-1}{n-1}. $$
示例：$3$种口味选$5$杯奶茶（可重复），有$\binom{5+3-1}{5}=\binom{7}{5}=21$ 种选法。
题6 [难度：进阶]
题目：单词 "MISSISSIPPI" 的字母重排有多少种不同的排列？
分析：多重集排列：$n!/(n_1!n_2!\cdots n_k!)$。
解答： 字母频数：M=1, I=4, S=4, P=2。总数 $n=11$。
排列数 $=\dfrac{11!}{1!\thinspace4!\thinspace4!\thinspace2!}=\dfrac{39916800}{1\cdot24\cdot24\cdot2}=34650$。
题7 [难度：基础]
题目：证明 $C_n^0+C_n^1+C_n^2+\cdots+C_n^n=2^n$。
分析：二项式定理 $(1+1)^n$ 展开即得。
解答： 由二项式定理 $(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k$。
令 $x=1$：$(1+1)^n=2^n=\sum_{k=0}^n\binom{n}{k}$。证毕。
三、鸽巢原理与拉姆齐
题8 [难度：基础]
题目：任意 $5$个整数中，必有两个数模$4$ 同余。说明理由。
分析：鸽巢原理，$5$个元素放入$4$ 个余数类别。
解答： 模 $4$的余数有$4$ 种：$0,1,2,3$。
$5$个整数按余数分为$4$类，由鸽巢原理，至少有一类含$\lceil5/4\rceil=2$ 个元素。
即至少有两个数同余，它们的差被 $4$ 整除。
题9 [难度：进阶]
题目：在边长为 $1$的正方形内任取$5$个点，证明必有两点的距离不超过$\sqrt{2}/2$。
分析：将正方形四等分，鸽巢原理。
解答： 将正方形分成 $4$个相等小正方形（边长为$1/2$）。
$5$个点放入$4$个小正方形，由鸽巢原理至少有一个小正方形含$2$ 个点。
小正方形的对角线长为 $\sqrt{(1/2)^2+(1/2)^2}=\sqrt{2}/2$。
故该两点距离 $\leq\sqrt{2}/2$。证毕。
题10 [难度：竞赛]
题目（拉姆齐 $R(3,3)$）：证明 $6$个人中，必有$3$ 个人互相认识或互相不认识。
分析：图论语言：$K_6$的边染两色，必存在单色$K_3$。
解答： 任选一人 $A$。$A$与其余$5$人之间，由鸽巢原理，至少$3$人（设为$B,C,D$）与 $A$ 的关系同色（同为"认识"或同为"不认识"）。
不妨设 $A$与$B,C,D$均认识。若$B,C,D$中有两人相互认识，则这二人与$A$ 构成互相认识的三人组。
若 $B,C,D$两两互不认识，则$B,C,D$ 构成互相不认识的三人组。
综上，必存在同色 $K_3$。
题11 [难度：竞赛]
题目：从 $1,2,\ldots,2n$中任取$n+1$ 个数，证明必有两个数互素。
分析：相邻整数互素，鸽巢原理配合配对。
解答： 将 $1,2,\ldots,2n$配对为$(1,2),(3,4),\ldots,(2n-1,2n)$，共 $n$ 对。
每对内的两个数互素（$\gcd(k,k+1)=1$）。
取出 $n+1$ 个数，由鸽巢原理至少有一对的两个数都取出，它们互素。证毕。
四、生成函数
题12 [难度：进阶]
题目：利用生成函数求斐波那契数列 $F_0=0,F_1=1,\ F_{n}=F_{n-1}+F_{n-2}$ 的通项。
分析：设生成函数 $G(x)=\sum F_nx^n$，由递推导出方程求解。
解答： 设 $G(x)=\sum_{n=0}^\infty F_nx^n$。
由递推（对 $n\geq2$）：$F_n-F_{n-1}-F_{n-2}=0$。
乘以 $x^n$ 并求和（$n\geq2$）： $$ \sum_{n=2}^\infty F_nx^n-x\sum_{n=2}^\infty F_{n-1}x^{n-1}-x^2\sum_{n=2}^\infty F_{n-2}x^{n-2}=0. $$ 即 $(G-F_0-F_1x)-x(G-F_0)-x^2G=0$。
代入 $F_0=0,F_1=1$：$G-x-xG-x^2G=0$。
$G(1-x-x^2)=x$，故 $G(x)=\dfrac{x}{1-x-x^2}$。
分母因式分解：$1-x-x^2=(1-\alpha x)(1-\beta x)$，其中 $\alpha=\dfrac{1+\sqrt{5}}{2},\ \beta=\dfrac{1-\sqrt{5}}{2}$。
部分分式分解得 $F_n=\dfrac{1}{\sqrt{5}}(\alpha^n-\beta^n)$（Binet 公式）。
题13 [难度：竞赛]
题目：利用生成函数求 $\displaystyle\sum_{k=0}^n k\binom{n}{k}$ 的值。
分析：对 $(1+x)^n=\sum\binom{n}{k}x^k$ 求导再赋值。
解答： $$ (1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k. $$ 两边求导： $$ n(1+x)^{n-1}=\sum_{k=1}^n k\binom{n}{k}x^{k-1}. $$ 令 $x=1$：$n\cdot2^{n-1}=\sum_{k=1}^n k\binom{n}{k}$。
故 $\displaystyle\sum_{k=0}^n k\binom{n}{k}=n\cdot2^{n-1}$。
五、二项式恒等式
题14 [难度：基础]
题目：证明 $\displaystyle\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}$。
分析：比较 $(1+x)^n(1+x)^n=(1+x)^{2n}$中$x^n$ 的系数。
解答： 左边 $(1+x)^n(1+x)^n$中$x^n$的系数为$\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}=\sum_{k=0}^n\binom{n}{k}^2$。
右边 $(1+x)^{2n}$中$x^n$的系数为$\binom{2n}{n}$。
故等式成立。
题15 [难度：进阶]
题目：证明范德蒙德恒等式 $\displaystyle\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}$。
分析：从 $m+n$个元素中选$r$个，按「前$m$个中选$k$ 个」分类。
解答： 组合证法：从 $m$个男生和$n$个女生中选$r$ 人。
按选出的男生数 $k$分类：选$k$ 个男生（$\binom{m}{k}$）和 $r-k$ 个女生（$\binom{n}{r-k}$）。对所有 $k$求和等于直接选$\binom{m+n}{r}$。
代数证法：$(1+x)^m(1+x)^n=(1+x)^{m+n}$，比较 $x^r$ 系数即得。
题16 [难度：进阶]
题目：求 $\displaystyle\sum_{k=0}^n(-1)^k\binom{n}{k}$ 的值，并解释其组合意义。
分析：$(1-1)^n$，即二项式定理 $x=-1$。组合意义：偶数元子集与奇数元子集个数相等。
解答： $\displaystyle\sum_{k=0}^n(-1)^k\binom{n}{k}=(1-1)^n=0^n=\begin{cases}1,&n=0\newline0,&n\geq1\end{cases}$。
当 $n\geq1$ 时，$\sum_{k\text{ even}}\binom{n}{k}=\sum_{k\text{ odd}}\binom{n}{k}=2^{n-1}$。
即 $n$ 元集的偶数元子集与奇数元子集个数相等。
六、图论基础
题17 [难度：基础]
题目（握手定理）：某聚会上 $n$ 个人握手，证明握手次数为奇数的人数为偶数。
分析：图论中 $\sum\deg(v)=2|E|$，故奇度点个数为偶数。
解答： 以人为顶点，握手为边，度数 $\deg(v)$ 为握手次数。
由握手定理 $\sum\deg(v)=2|E|$ 为偶数。
将顶点按度数的奇偶分两类，奇度点度数之和 $+$偶度点度数之和$=$ 偶数。
偶度点度数之和为偶数，故奇度点度数之和也为偶数。奇数个奇数的和为奇数（矛盾），所以奇度点个数必为偶数。
题18 [难度：进阶]
题目：判断下列图是否存在欧拉回路/欧拉路径：(1) $K_5$；(2) $K_4$。
分析：欧拉回路 $\iff$所有点度数为偶数。欧拉路径$\iff$ 恰有两个奇度点。
解答： (1) $K_5$：每个顶点度数为 $4$（偶数），存在欧拉回路。
(2) $K_4$：每个顶点度数为 $3$（奇数），共 $4$个奇度点。欧拉回路不存在，欧拉路径（恰$2$个奇度点）也不存在。故$K_4$ 无欧拉回路也无欧拉路径。
题19 [难度：竞赛]
题目：一棵树有 $n$个顶点，证明其边数为$n-1$。
分析：归纳法或利用连通且无圈的性质。
解答： 对 $n$ 归纳。$n=1$时边数$0=1-1$，成立。
设 $n\geq2$。树必有叶子节点（度数为 $1$），否则每个点度 $\geq2$，沿边走必成圈，矛盾。
去掉一个叶子及其连边，得到 $n-1$个顶点的树，由归纳假设有$n-2$ 条边。
恢复叶子后边数 $=(n-2)+1=n-1$。证毕。
七、染色问题
题20 [难度：进阶]
题目：证明：平面图的顶点可由 $4$ 种颜色染色使相邻顶点异色（四色定理，这里改用五色定理证的思路）。
分析：五色定理的归纳证明（四色定理已知成立，但证法复杂）。用五色定理归纳。
解答： 五色定理证法：对顶点数 $V$ 归纳。$V\leq5$ 显然。
任意平面图存在度数 $\leq5$的顶点$v$。
- 若 $\deg(v)\leq4$：去掉 $v$染色（归纳），最多$4$种颜色在邻居中，有空余颜色给$v$。
- 若 $\deg(v)=5$：$v$有$5$个邻居$v_1,\ldots,v_5$。其中必有两点不相邻（否则产生 $K_5$子图，与平面性矛盾）。设$v_1,v_3$不相邻，收缩$v,v_1,v_3$ 合并…归纳可得五色染色。
故任何平面图可 $5$ 染色（四色定理更强，但证明极复杂）。
题21 [难度：基础]
题目：$2\times n$ 棋盘用黑白两色染色，每格一色，要求相邻格不同色，有多少种染色方法？
分析：棋盘染色递推，每列有两种选择（黑在上白在下，或反之）。
解答： 每列有两种染色方式（不可旋转，固定方向）。相邻列之间要求同行不同色，即每列选定后下一列必须翻转。
第一列 $2$ 种选择，之后每列唯一确定（翻转前一列）。
故共 $2$ 种染色方法。
八、组合极值与构造
题22 [难度：进阶]
题目：在 $n\times n$ 棋盘上最多能放多少个互不攻击的车（rook）？最多互不攻击的后（queen）？
分析：车：每行每列至多一个；后：每行每列每对角至多一个。
解答： 车：每行至多一个，故最多 $n$个（主对角线放置$n$ 个即可达上界）。
后（$n$后问题）：同样最多$n$个（每行至多一个）。当$n\geq4$时可达到$n$ 个（经典八后问题）。$n=1,2,3$ 时：$n=1$放$1$ 个，$n=2$最多$1$ 个，$n=3$最多$2$ 个。
题23 [难度：竞赛]
题目（Turán 定理特例）：$n$ 个顶点的图若不包含三角形（$K_3$），最多有多少条边？
分析：Turán 定理 $n=2$ 时结论。不含三角形的极值图为完全二部图。
解答： 将顶点分为两部 $A,B$，$|A|=a,\ |B|=b=n-a$。完全二部图 $K_{a,b}$不含三角形，边数$ab$。
由均值不等式 $a(n-a)\leq\left(\dfrac{n}{2}\right)^2=\dfrac{n^2}{4}$。
故最多边数为 $\lfloor n^2/4\rfloor$，取等当 $a=\lfloor n/2\rfloor,b=\lceil n/2\rceil$。
注
Mantel 定理（1907）是 Turán 定理的特殊情况。
题24 [难度：进阶]
题目（极值构造）：$n$ 个人相互写贺卡，每人写一张给除自己外的某人，要求没有人收到自己写的卡且没人收到超过一张卡。最多有多少种分配方案？（即错排的另一种形式——乱序映射）
分析：对应 $n$元集到自身的排列，且排列无不动点。这就是错排数$D_n$。
解答： "每人送出正好一张卡、每人收到正好一张卡"对应排列。
"没人收到自己写的卡"即无不动点的排列 = 错排。
方案数为 $D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$。
题25 [难度：竞赛]
题目：给定正整数 $n$，求最大的 $m$使得$1,2,\ldots,m$可以划分为$n$ 个子集，每个子集的和相等。
分析：需满足 $\sum_{i=1}^m i=m(m+1)/2$可被$n$整除，即$n\mid m(m+1)/2$。
解答： 要求和条件：$S_m=\dfrac{m(m+1)}{2}$需被$n$整除，即$2n\mid m(m+1)$。
此外还需要能实际分割（存在性）。对足够大的 $m$满足整除条件，一定存在分割方案（充要条件是$m$足够大且满足整除条件，但对特定小$n$ 有例外）。
对于给定的 $n$，找到最大的 $m$需同时考虑整除条件与构造可行性。一般结论：当$m\geq 2n-1$且$2n\mid m(m+1)$ 时存在分割。
九、双计数法
题26 [难度：进阶]
题目：某班 $30$名学生参加$5$个社团，每个社团有$12$人，每人参加恰好$2$ 个社团。用双计数法验证数据是否自洽。
分析：按「人-社团」关联计数，一种按人算，一种按社团算。
解答： 按社团算：$5$个社团$\times12$人 =$60$ 人次。
按人算：$30$人$\times2$个社团 =$60$ 人次。
两者一致，数据自洽。
题27 [难度：竞赛]
题目：$n$个点，任两点之间有恰好一条路径（形成一个竞赛图的方向）。用双计数法证明「出度之和 = 入度之和 =$\binom{n}{2}$」。
分析：每条有向边贡献 $1$出度和$1$ 入度。两种计数方式验证。
解答： 方式一：总边数 $=\binom{n}{2}$。每条边贡献 $1$出度，所以所有顶点出度之和 = 边数 =$\binom{n}{2}$。
方式二：直接对所有顶点的出度求和（定义），同样得 $\binom{n}{2}$。
双计数验证了恒等式 $\sum_{v}\deg^+(v)=\binom{n}{2}$。
十、卡特兰数
题28 [难度：进阶]
题目：$n$对括号的合法匹配序列有多少种？即卡特兰数$C_n$。求 $C_0$到$C_5$ 并给出通项公式。
分析：卡特兰数 $C_n=\dfrac{1}{n+1}\dbinom{2n}{n}$。
解答： 递推公式：$C_0=1$，$C_{n+1}=\sum_{k=0}^n C_kC_{n-k}$。
计算： $C_0=1$ $C_1=C_0C_0=1$ $C_2=C_0C_1+C_1C_0=1+1=2$（()()、(())） $C_3=C_0C_2+C_1C_1+C_2C_0=2+1+2=5$ $C_4=C_0C_3+C_1C_2+C_2C_1+C_3C_0=5+2+2+5=14$ $C_5=C_0C_4+C_1C_3+C_2C_2+C_3C_1+C_4C_0=14+5+4+5+14=42$
通项公式： $$ C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{(n+1)!\thinspace{}n!}. $$
卡特兰数常见应用
括号匹配、二叉树计数、凸多边形三角剖分、Dyck 路径、出栈序列等均对应卡特兰数。
十一、Hall 婚姻定理与匹配
题29 [难度：进阶]
题目：证明 $k$-正则二部图 $G = (X, Y, E)$（$|X| = |Y| = n$，每个顶点度数恰为 $k$）必有完美匹配。
分析：用 Hall 婚姻定理，验证 Hall 条件 $|N(S)| \ge |S|$。
解答： 取任意 $S \subseteq X$。从 $S$出发的边数为$k|S|$。这些边全部进入 $N(S)$中，每个$N(S)$中顶点的度数恰为$k$，故 $N(S)$接收的边数$\le k|N(S)|$。故 $k|S| \le k|N(S)|$，即 $|N(S)| \ge |S|$。由 Hall 定理，存在覆盖 $X$ 的匹配；$|X| = |Y|$ 故为完美匹配。$\square$
关键
正则性 + 二部性使双计数自动给出 Hall 条件。这是 Hall 定理最经典应用之一。
题30 [难度：竞赛]
题目：用 Hall 定理证明 König 定理：二部图最大匹配数 = 最小点覆盖数。
分析：构造性证明，对最大匹配 $M$ 构造等大小的点覆盖。
解答： 设 $G = (X, Y, E)$，最大匹配 $M$。令 $U$为$X$中未被$M$覆盖的顶点集。从$U$出发沿「非匹配边—匹配边」交替路（增广路）搜索可达点集$Z$（含 $U$ 及其所有可达点）。
设 $Z_X = Z \cap X$，$Z_Y = Z \cap Y$。由 $M$ 的最大性，$Z_Y$中每个点都在$M$中匹配（否则存在增广路，与$M$最大矛盾），且$N(Z_X) \subseteq Z_Y$。事实上 $N(Z_X) = Z_Y$（否则增广路可扩展）。
构造点覆盖 $C = (X \setminus Z_X) \cup Z_Y$。每条边 $xy$必被覆盖：若$x \in Z_X$则$y \in Z_Y$（被覆盖）；若 $x \notin Z_X$则$x \in C$。$|C| = (|X| - |Z_X|) + |Z_Y| = |M|$（由 $Z_Y$中点都匹配且与$Z_X \setminus U$一一对应）。故最小点覆盖$\le |M|$。又匹配数 $\le$ 点覆盖数（每条匹配边需不同覆盖点），故等号成立。$\square$
题31 [难度：进阶]
题目：$8\times 8$棋盘去掉对角两格，能否用$2\times 1$ 多米诺骨牌完全覆盖？用 Hall 定理解释。
分析：将棋盘黑白染色，转化为二部图匹配问题。
解答： 黑白相间染色后，$8\times 8$ 棋盘有 32 黑 32 白。去掉的两对角格同色（设为黑），剩余 30 黑 32 白。
构造二部图 $G$：黑格为 $X$，白格为 $Y$，相邻格连边。每个 $2\times 1$骨牌必覆盖一黑一白，对应$G$的一条匹配边。完全覆盖需$G$有大小为 30 的匹配覆盖$X$（所有黑格）。
但 $|X| = 30 < 32 = |Y|$，Hall 条件需对所有 $S \subseteq X$有$|N(S)| \ge |S|$。考虑 Hall 条件被破坏的情形：实际上 $X$中存在子集$S$（如某些黑格的邻居数少于自身）使 $|N(S)| < |S|$，故无完美匹配覆盖 $X$。直观上 32 白多 2 个，必有 2 白无法配对。$\square$
更简洁论证
直接用染色：30 黑 32 白，每个骨牌覆盖一黑一白，至多覆盖 30 黑 30 白，剩 2 白无法覆盖。
题32 [难度：竞赛]
题目：构造一个无完美匹配的图，使其不满足 Tutte 1-因子定理条件中的某个关键不等式。
分析：Tutte 定理：$G$有完美匹配$\iff$对任意$S \subseteq V$，$o(G - S) \le |S|$，其中 $o(H)$为$H$ 的奇连通分量数。
解答： 取「三个三角形 + 一个中心点连向每个三角形一个顶点」的图 $G$：7 个顶点，三个 $K_3$（顶点 $a_i b_i c_i$，$i=1,2,3$），中心点 $v$与$a_1, a_2, a_3$ 相连。
取 $S = \lbrace v\rbrace $，$|S| = 1$。$G - S$为三个$K_3$，每个为奇连通分量（3 个顶点），故 $o(G - S) = 3 > 1 = |S|$。Tutte 条件破坏，故 $G$ 无完美匹配（顶点数 7 为奇，本就不可能有完美匹配，本例体现 Tutte 条件的判定力）。
更一般地，取 $S = \lbrace v, a_1, a_2, a_3\rbrace $，$|S| = 4$，$G - S$有 3 个孤立点$b_i c_i$配对剩$b_2, c_2, b_3, c_3$... 严格构造需谨慎，但核心思路是用 $o(G-S) > |S|$ 判定。详见 高级图论与网络流。
十二、网络流与最小割
题33 [难度：竞赛]
题目：用最大流最小割定理证明 Menger 定理（边版本）：图中两顶点 $s, t$间边不交路径的最大数等于分离$s, t$ 所需删除的最少边数。
分析：将图转化为流网络，应用最大流最小割。
解答： 将 $G$视为流网络：源$s$、汇 $t$，每条边容量为 1。最大流值 = $s$到$t$ 边不交路径数（容量 1 保证每条边至多用一次，整数流保证是路径集合）。
最小割 = 分离 $s, t$ 的最少边数（容量即边数）。由最大流最小割定理，二者相等。$\square$
题34 [难度：进阶]
题目：$n$ 个工人、$m$个任务，工人$i$能做任务$j$当且仅当$a_{ij} = 1$，每个工人最多做 $c_i$ 个任务，每个任务只需 1 人。求最大可分配任务数。
分析：二部图最大流模型。
解答： 构造流网络：源 $s \to$工人$i$（容量 $c_i$）；工人 $i \to$任务$j$（容量 1，当 $a_{ij} = 1$）；任务 $j \to$汇$t$（容量 1）。
最大流值即最大分配任务数。Ford-Fulkerson 算法可在多项式时间求解。详见 高级图论与网络流。
题35 [难度：进阶]
题目：证明二部图 $G = (X, Y, E)$的最大独立集大小$= |V| - $ 最大匹配数。
分析：用 König 定理（最大匹配 = 最小点覆盖）。
解答： 点覆盖 $C$与独立集$I$ 互补：$I = V \setminus C$为独立集$\iff C$为点覆盖（任一边至少一端在$C$）。
故最大独立集 = $|V| - $最小点覆盖 =$|V| - $ 最大匹配（由 König 定理）。$\square$
十三、平面图与 Euler 公式
题36 [难度：进阶]
题目：用 Euler 公式证明 $K_5$ 非平面。
分析：假设 $K_5$ 平面，用 Euler 公式和边数上界推出矛盾。
解答： $K_5$有$V = 5$ 顶点，$E = 10$边。若$K_5$平面，由 Euler 公式$V - E + F = 2$得$F = 7$。
每个面至少由 3 条边围成，每条边至多属于 2 个面，故 $3F \le 2E$，即 $21 \le 20$，矛盾。故 $K_5$ 非平面。$\square$
题37 [难度：进阶]
题目：证明连通平面图（$V \ge 3$）满足 $E \le 3V - 6$。
分析：用 Euler 公式和面的边数下界。
解答： 由 Euler 公式 $F = 2 - V + E$。每个面至少 3 条边，每边至多 2 面，故 $3F \le 2E$，即 $3(2 - V + E) \le 2E$，化简得 $E \le 3V - 6$。$\square$
加强版
若图无三角形（每个面至少 4 边），则 $E \le 2V - 4$。
题38 [难度：基础]
题目：证明任意平面图必有度数 $\le 5$ 的顶点。
分析：反证法 + 边数上界。
解答： 假设所有顶点度数 $\ge 6$。由握手定理 $2E = \sum \deg(v) \ge 6V$，即 $E \ge 3V$。但平面图 $E \le 3V - 6 < 3V$，矛盾。故存在度 $\le 5$ 的顶点。$\square$
应用
此结论是五色定理归纳证明的基础：删去度 $\le 5$ 的顶点，归纳染色后补回。
十四、Ramsey 数与极图
题39 [难度：进阶]
题目：证明 $R(3, 4) \le 9$。
分析：取顶点 $v$，按红蓝邻居分类，结合 $R(2, 4) = 4$和$R(3, 3) = 6$。
解答： $K_9$任一顶点$v$有 8 条边。若$v$至少 4 条红边，红邻居集$R$大小$\ge 4$。$R$中若有红边则与$v$成红$K_3$；否则 $R$ 全蓝，$|R| \ge 4 = R(2, 4)$故$R$中有蓝$K_4$（含 2 顶点的蓝边即蓝 $K_2$，但需 $K_4$... 正确推导：$R$全蓝且$|R| \ge 4$，则 $R$本身是蓝$K_4$）。
若 $v$至少 6 条蓝边，蓝邻居集$B$大小$\ge 6 = R(3, 3)$，故 $B$中有红$K_3$或蓝$K_3$。红 $K_3$完成；蓝$K_3$加$v$成蓝$K_4$。
8 条边中红 $\ge 4$或蓝$\ge 6$（若红 $\le 3$且蓝$\le 5$则总数$\le 8$，恰等时蓝 $= 5 < 6$；需更细：若红 $\le 3$蓝$\ge 5$，但 $R(3, 3) = 6$需 6 条蓝边。修正：用$R(3, 3) = 6$和$R(2, 4) = 4$，8 条边必红 $\ge 4$或蓝$\ge 5$。若蓝 $\ge 6$用$R(3,3)$；若蓝 $= 5$、红 $= 3$，红邻居 3 个点：若红边存在成红 $K_3$，否则 3 点全蓝加 $v$ 的 5 蓝邻居中取 3... 需要更精细论证。
标准证：$R(3,4) \le R(2,4) + R(3,3) = 4 + 6 = 10$，更精细给出 $R(3,4) = 9$。完整证明见 拉姆齐理论与极图理论。
题40 [难度：竞赛]
题目：用 Erdős–Szekeres 归纳证明 $R(s, t) \le \binom{s+t-2}{s-1}$。
分析：用递推 $R(s, t) \le R(s-1, t) + R(s, t-1)$ 和 Pascal 恒等式。
解答： 对 $s + t$ 归纳。基础：$R(1, t) = 1$, $R(s, 1) = 1$。
对 $K_n$（$n = R(s-1, t) + R(s, t-1)$）任一顶点 $v$有$n - 1$条边。红边$\ge R(s-1, t)$或蓝边$\ge R(s, t-1)$（鸽巢）。若红边 $\ge R(s-1, t)$，红邻居中含红 $K_{s-1}$（加 $v$成红$K_s$）或蓝 $K_t$。若蓝边 $\ge R(s, t-1)$，蓝邻居中含红 $K_s$或蓝$K_{t-1}$（加 $v$成蓝$K_t$）。
故 $R(s, t) \le R(s-1, t) + R(s, t-1) \le \binom{s+t-3}{s-2} + \binom{s+t-3}{s-1} = \binom{s+t-2}{s-1}$。$\square$
题41 [难度：竞赛]
题目：证明 $R(k, k) > \lfloor \frac{k}{e\sqrt{2}} \cdot 2^{k/2} \rfloor$。
分析：Erdős 概率方法。
解答： 对 $K_n$边随机染红/蓝（各$1/2$）。同色 $K_k$ 期望数为 $$E[X] = \binom{n}{k} \cdot 2 \cdot 2^{-\binom{k}{2}} \le \frac{n^k}{k!} \cdot 2^{1 - k(k-1)/2}$$ 当 $n < \frac{k}{e\sqrt{2}} 2^{k/2}$时，用$k! \ge (k/e)^k$和 Stirling 估计可得$E[X] < 1$。故存在染色无同色 $K_k$，即 $R(k, k) > n$。$\square$
详见 概率方法与随机结构 与 拉姆齐理论与极图理论。
题42 [难度：竞赛]
题目：证明 Turán 定理：不含 $K_{r+1}$的$n$顶点图至多有$\text{ex}(n, K_{r+1}) = (1 - 1/r) n^2/2$ 条边（精确到整除）。
分析：归纳法或权转移法。
解答（归纳要点）： 对 $n$ 归纳。$n \le r$时$K_n$即最大（无$K_{r+1}$），边数 $\binom{n}{2} \le (1-1/r)n^2/2$。
$n > r$：取最大团 $K_r = \lbrace v_1, \ldots, v_r\rbrace $。每个其他顶点至多与 $K_r$中$r-1$个相邻（否则成$K_{r+1}$）。设 $G' = G - v_r$，$G'$不含$K_{r+1}$，由归纳 $|E(G')| \le \text{ex}(n-1, K_{r+1})$。$v_r$的度数$\le n - 1$（但更精细地 $\le$ Turán 图中对应度数）。
完整证明给出极值图 $T(n, r)$：$r$部分尽可能等分，部分内无边，部分间全连。边数$= \sum_{i < j} n_i n_j = (n^2 - \sum n_i^2)/2$，在 $n_i$ 尽量等分时最大。$\square$
详见 拉姆齐理论与极图理论 和 组合极值与构造。
题43 [难度：竞赛]
题目（IMO 1964 题4）：17 人中任两人恰通信一次（信或电话）。证明必有 3 人两两以同种方式通信。
分析：三色 Ramsey $R(3, 3, 3) \le 17$。
解答： 将 17 人视为完全图 $K_{17}$顶点，每种通信方式对应一种颜色（3 色）。需证$K_{17}$边 3-染色必有同色$K_3$。
取顶点 $v$，16 条边由鸽巢原理至少 $\lceil 16/3 \rceil = 6$条同色（设红色），红邻居集$R$大小$\ge 6$。$R$的边仍 3-染色，由$R(3, 3) = 6$，$R$中必有同色$K_3$（在某两色合并的视角下）。
严格地：$R(3,3,3) \le 1 + 3(R(3,3) - 1) + 1 = 17$。$v$的 16 条边分 3 类，至少 6 条同色。该色邻居 6 点中，由$R(3,3) = 6$，任 2-染色必有同色 $K_3$（视为剩余两色），完成。$\square$
十五、组合几何
题44 [难度：进阶]
题目：证明 $\mathbb{R}^2$中 Helly 定理：若三个凸集$C_1, C_2, C_3$ 两两相交，则三向交非空。
分析：取点构造三角形，利用凸性。
解答： 取 $p_1 \in C_2 \cap C_3$, $p_2 \in C_1 \cap C_3$, $p_3 \in C_1 \cap C_2$。三点形成的三角形 $\triangle p_1 p_2 p_3$ 中：
- $p_2, p_3 \in C_1$，故 $\triangle \subseteq C_1$（凸性）
- $p_1, p_3 \in C_2$，故 $\triangle \subseteq C_2$
- $p_1, p_2 \in C_3$，故 $\triangle \subseteq C_3$
故 $\triangle \subseteq C_1 \cap C_2 \cap C_3$，三向交非空。$\square$
详见 组合几何。
题45 [难度：进阶]
题目：证明 $(r-1)(s-1) + 1$个互异实数必有长$r$递增或长$s$ 递减子序列。
分析：鸽巢原理，对每个元素记录 LIS 长度和 LDS 长度。
解答： 对第 $i$个数$a_i$，记 $f(i)$为以$a_i$ 结尾的最长递增子序列长度，$g(i)$ 为最长递减子序列长度。
对任意 $i \ne j$，$(f(i), g(i)) \ne (f(j), g(j))$：若 $a_i < a_j$（$i < j$），则 $f(j) \ge f(i) + 1$；若 $a_i > a_j$，则 $g(j) \ge g(i) + 1$。故所有 $(f(i), g(i))$ 互异。
若所有 $f(i) \le r - 1$且$g(i) \le s - 1$，则 $(f, g)$至多$(r-1)(s-1)$种，但元素数$(r-1)(s-1) + 1$，鸽巢矛盾。故 $f(i) \ge r$或$g(i) \ge s$对某$i$ 成立。$\square$
题46 [难度：进阶]
题目：证明任意 5 个一般位置（无三点共线）的平面点集必含 4 个点构成凸四边形。
分析：按凸包分类讨论。
解答： 5 点凸包的可能：
- 凸包为五边形：任取 4 点构成凸四边形。
- 凸包为四边形：该四边形即凸四边形。
- 凸包为三角形：两点 $P, Q$在三角形$ABC$内部。直线$PQ$与三角形两边相交（不在顶点），故$PQ$将三角形分为两部分，某部分含三角形一个顶点$A$。$A, P, Q$与另一侧三角形的某顶点（或$PQ$ 延长线交点另一侧）构成凸四边形。更精确地：$PQ$必与$\triangle ABC$两边相交，设交$AB$于$X$、$AC$于$Y$，则 $A$与$P, Q$及$B$或$C$ 构成凸四边形。
详见 组合几何。
题47 [难度：竞赛]
题目（Sylvester–Gallai）：证明有限非共线点集 $S$ 必存在「普通线」（恰过两点）。
分析：极端原理 + 距离最小化。
解答： 设 $S$中所有点对的连线都过至少 3 点（反证）。对所有点对$(A, B)$和第三点$C \notin AB$，考虑 $C$到$AB$的距离。取距离最小的三元组$(A, B, C)$，$C$到$AB$距离$d > 0$ 最小。
$AB$上有第三点$D$。设 $D$位于$A$和$B$之间或外侧。不妨$D$与$A$ 同侧（$D$在$A$和$C$在$AB$投影同侧）。则$C$到$AD$的距离$< d$（因 $AD \subset AB$但$D$更近$A$），与最小性矛盾。严格论证需考虑 $D$ 的位置分类。$\square$
详见 组合几何。
十六、概率方法
题48 [难度：进阶]
题目：用 Markov 不等式证明：存在 $n$顶点图其独立数$\ge n / (2\log_2 n)$。
分析：随机图 + 期望。
解答： 考虑 $G(n, 1/2)$。固定 $k$-子集 $S$，$S$为独立集的概率$= 2^{-\binom{k}{2}}$。独立 $k$-子集期望数 $= \binom{n}{k} 2^{-\binom{k}{2}}$。
取 $k = 2\log_2 n$，$\binom{n}{k} \le n^k / k!$，$2^{-\binom{k}{2}} = 2^{-k(k-1)/2}$。期望 $\le n^k 2^{-k^2/2} / k! \approx 2^{k \log_2 n - k^2/2}$。$k = 2\log_2 n$时代入$= 2^{2(\log n)^2 - 2(\log n)^2} \approx 1$，故存在图 $\alpha(G) \ge c \log_2 n$。
更精确的 Ramsey 下界见 概率方法与随机结构。$\square$
题49 [难度：进阶]
题目：用 alteration 方法证明 $\alpha(G) \ge n / (\Delta + 1)$（$G$为$n$顶点最大度$\Delta$ 图）。
分析：随机均匀顺序 + 期望。
解答： 随机均匀顺序处理顶点，$v$加入$I$当且仅当$v$ 在所有邻居前。$P(v \in I) = 1/(\deg(v) + 1) \ge 1/(\Delta + 1)$。
$E[|I|] = \sum_v P(v \in I) \ge n/(\Delta + 1)$。故存在顺序使 $|I| \ge n/(\Delta + 1)$，即 $\alpha(G) \ge n/(\Delta + 1)$。$\square$
题50 [难度：竞赛]
题目：用 Lovász 局部引理证明：$k$-均匀超图（每边含 $k$点）若每条边与至多$d = 2^{k-3}$ 条其他边相交，则 2-可染色。
分析：LLL 对称形式 $e p (d+1) \le 1$。
解答： 随机 2-染色每点。坏事件 $A_e$：边 $e$ 单色。$P(A_e) = 2 \cdot 2^{-k} = 2^{1-k}$。每条边依赖至多 $d' = k \cdot d$条边（共享顶点），但更精细地$A_e$ 仅与共享顶点的边相关。
LLL 条件 $e \cdot p \cdot (d+1) \le 1$即$e \cdot 2^{1-k} \cdot (d+1) \le 1$，即 $d \le 2^{k-1}/e - 1 \approx 2^{k-3}$（$e \approx 2.718$）。满足时存在正常 2-染色。$\square$
详见 概率方法与随机结构。
题51 [难度：竞赛]
题目：用第二矩方法证明 $G(n, p)$中三角形存在的阈值为$p = n^{-1}$。
分析：计算三角形数 $X$ 的期望与方差。
解答： $X = $ 三角形数，$E[X] = \binom{n}{3} p^3 \sim n^3 p^3 / 6$。
$p \gg n^{-1}$时$E[X] \to \infty$。第二矩：$\text{Var}(X) / E[X]^2 \to 0$（三角形间协方差可控），由 Chebyshev $P(X = 0) \le \text{Var}/E^2 \to 0$，故 $X > 0$ w.h.p.。
$p \ll n^{-1}$时$E[X] \to 0$，由 Markov $P(X \ge 1) \le E[X] \to 0$，故 $X = 0$ w.h.p.。
阈值 $p = c \cdot n^{-1}$。详见 概率方法与随机结构。$\square$
十七、Pólya 计数
题52 [难度：基础]
题目：用 3 种颜色染正方形 4 顶点，旋转等价的不同染色数？
分析：Burnside 引理，循环群 $C_4$ 作用。
解答： $C_4$元素：恒等（1 个，循环型$1^4$，不动点 $3^4 = 81$）、旋转 $90°$（1 个，循环型 $4$，不动点 $3$）、旋转 $180°$（1 个，循环型 $2^2$，不动点 $3^2 = 9$）、旋转 $270°$（1 个，循环型 $4$，不动点 $3$）。
Burnside：$\frac{1}{4}(81 + 3 + 9 + 3) = \frac{96}{4} = 24$。$\square$
详见 对称群与Pólya计数。
题53 [难度：进阶]
题目：用 $k$种颜色染$n$ 颗珠子的项链（旋转等价），不同方案数公式。
分析：$C_n$ 循环指标。
解答： $C_n$中阶$d$的元素有$\varphi(d)$ 个（$d | n$），每个循环型为 $(n/d)$个长$d$循环，不动点$k^{n/d}$。
Burnside：$\frac{1}{n} \sum_{d | n} \varphi(d) k^{n/d}$。$\square$
题54 [难度：竞赛]
题目：立方体 6 面用 $k$ 色染色（旋转等价），不同方案数。
分析：立方体旋转群（24 阶）循环指标，作用在 6 面上。
解答： 旋转群共轭类（按面作用）：
- 恒等（1）：循环型 $1^6$，不动点 $k^6$
- 面心-面心 $90°/270°$（6）：循环型 $1^2 4$，不动点 $k^3$
- 面心-面心 $180°$（3）：循环型 $1^2 2^2$，不动点 $k^4$
- 顶点-顶点 $120°/240°$（8）：循环型 $3^2$，不动点 $k^2$
- 边中-边中 $180°$（6）：循环型 $2^3$，不动点 $k^3$
总数 $= \frac{1}{24}(k^6 + 6k^3 + 3k^4 + 8k^2 + 6k^3) = \frac{1}{24}(k^6 + 3k^4 + 12k^3 + 8k^2)$。
$k = 3$时$= \frac{1}{24}(729 + 243 + 324 + 72) = \frac{1368}{24} = 57$。$\square$
详见 对称群与Pólya计数。
十八、组合数论与加法组合
题55 [难度：进阶]
题目：证明 Schur 数 $S(2) = 5$：任意 2-染色 $\lbrace 1, 2, 3, 4, 5\rbrace $必有同色$x + y = z$；但 $\lbrace 1, 2, 3, 4\rbrace $ 存在 2-染色无解。
分析：构造下界 + 反证上界。
解答： 下界（$S(2) > 4$）：染 $\lbrace 1, 4\rbrace $ 红、$\lbrace 2, 3\rbrace $ 蓝。红：$1+1=2$（蓝），$1+4=5$（外），$4+4=8$（外）；蓝：$2+2=4$（红），$2+3=5$（外），$3+3=6$（外）。无同色 $x+y=z$。
上界（$S(2) \le 5$）：任 2-染色 $\lbrace 1,2,3,4,5\rbrace $。不妨设 $1$红。若$2$ 红，$1+1=2$完成。若$2$蓝：若$4$ 蓝，$2+2=4$完成。若$4$红：若$3$ 红，$1+3=4$完成。若$3$蓝：若$5$ 蓝，$2+3=5$完成。若$5$ 红，$1+4=5$完成。穷举所有情形必有同色$x+y=z$。$\square$
详见 组合数论与加法组合。
题56 [难度：竞赛]
题目：证明 $W(3, 2) = 9$：任意 2-染色 $\lbrace 1, \ldots, 9\rbrace $必有同色 3-项等差数列；但$\lbrace 1, \ldots, 8\rbrace $ 存在 2-染色无同色 3-AP。
分析：构造下界 + 反证上界。
解答： 下界（$W(3,2) > 8$）：染 RBRRBRBR（即 $\lbrace 1,3,4,5,7\rbrace $... 实际构造需小心）。经典构造：染 $\lbrace 1,2,5,6\rbrace $ 红、$\lbrace 3,4,7,8\rbrace $蓝。验证无同色 3-AP：红色 3-AP 需$a, b, c$ 等差且同红。$1,2,3$（3 蓝）；$1,3,5$（3 蓝）；$1,4,7$（4,7 蓝）；$2,3,4$（3,4 蓝）；$2,5,8$（8 蓝）；$5,6,7$（7 蓝）；类似蓝色 $3,4,5$（5 红）；$3,5,7$（5 红）；$4,5,6$（5,6 红）；$4,6,8$（6 红）；$3,6,9$ 不在范围；$1,5,9$ 不在。穷举可验证无同色 3-AP。
上界（$W(3,2) \le 9$）：$\lbrace 1, \ldots, 9\rbrace $任 2-染色。不妨$5$红。若$1, 9$中有红，设$1$红，则$1, 5, 9$检查$9$：若 $9$ 红，$1,5,9$红 3-AP。若$9$蓝，考虑$3, 5, 7$：若 $3, 7$ 红，3-AP。需系统穷举（标准证明较长，见 组合数论与加法组合）。$\square$
题57 [难度：进阶]
题目：证明任意 5 个整数中必有 3 个其和被 3 整除（EGZ 定理 $n = 3$ 情形）。
分析：按模 3 余数分类。
解答： 5 个整数按模 3 余数 $0, 1, 2$ 分类。
- 若某类 $\ge 3$个：取该类 3 个，和$\equiv 3r \equiv 0 \pmod{3}$。
- 否则各类 $\le 2$个：5 个分 3 类，必有某类恰 2 个，另一类至少 1 个。但 5 个分 3 类每类$\le 2$，则 $5 = 2 + 2 + 1$（某排列）。取 $0, 1, 2$类各一个，和$\equiv 0 + 1 + 2 = 3 \equiv 0 \pmod{3}$。
但需确保每类都有元素。若某类为空，则 5 个分 2 类，鸽巢某类 $\ge 3$，回到第一种情形。故总有 3 个和被 3 整除。$\square$
详见 组合数论与加法组合。
题58 [难度：竞赛]
题目：证明 Cauchy–Davenport 定理：$A, B \subseteq \mathbb{Z}_p$（$p$ 素数），$|A + B| \ge \min(p, |A| + |B| - 1)$。
分析：对 $|B|$ 归纳 + Davenport 变换。
解答（要点）： 若 $|B| = 1$显然$|A + B| = |A|$。
设 $|B| \ge 2$，取 $b \in B$，$B' = B \setminus \lbrace b\rbrace $。由归纳 $|A + B'| \ge \min(p, |A| + |B| - 2)$。
若 $|A + B'| \ge p$完成。否则需证加入$b$至少新增 1 元素。若$(A + B') + b \subseteq A + B'$（无新增），则 $A + B'$在平移$b$下不变，故$A + B' = \mathbb{Z}_p$（$b$生成$\mathbb{Z}_p$），$|A + B'| = p$，矛盾。故 $|A + B| \ge |A + B'| + 1 \ge |A| + |B| - 1$。
完整证明见 组合数论与加法组合。$\square$
十九、设计与编码
题59 [难度：进阶]
题目：构造 Fano 平面 $(7, 3, 1)$-BIBD：7 点 7 线，每线 3 点，每两线交 1 点，每两点确定 1 线。
分析：用 $\mathbb{Z}_7$的差集$\lbrace 1, 2, 4\rbrace $。
解答： 取点集 $\mathbb{Z}_7 = \lbrace 0, 1, \ldots, 6\rbrace $。基础区组 $B_0 = \lbrace 0, 1, 3\rbrace $（或 $\lbrace 1, 2, 4\rbrace $），其他区组 $B_i = B_0 + i \pmod{7}$： $$\lbrace 0,1,3\rbrace , \lbrace 1,2,4\rbrace , \lbrace 2,3,5\rbrace , \lbrace 3,4,6\rbrace , \lbrace 4,5,0\rbrace , \lbrace 5,6,1\rbrace , \lbrace 6,0,2\rbrace $$
验证：每对点恰出现在一个区组（如 $\lbrace 0, 1\rbrace $在$\lbrace 0,1,3\rbrace $；$\lbrace 0, 2\rbrace $在$\lbrace 6,0,2\rbrace $；$\lbrace 0, 3\rbrace $在$\lbrace 0,1,3\rbrace $... 共 $\binom{7}{2} = 21$对，每区组$\binom{3}{2} = 3$ 对，7 区组共 21 对，一一对应）。$\square$
详见 设计与编码理论初步。
题60 [难度：竞赛]
题目：证明 Fisher 不等式：BIBD $(v, k, \lambda)$中区组数$b \ge v$。
分析：关联矩阵的秩。
解答： 设关联矩阵 $A$（$v \times b$），$A_{ij} = 1$当点$i$在区组$j$。则 $A A^T = (r - \lambda) I + \lambda J$（$J$ 为全 1 矩阵），$r$ 为每点区组数。
$A A^T$ 的特征值：$r - \lambda + \lambda v = r + \lambda(v-1) = r + r(k-1) = rk$（对应全 1 向量）和 $r - \lambda$（重数 $v - 1$）。$r > \lambda$（一般情形），故 $A A^T$ 满秩，$\text{rank}(A) = v$。但 $\text{rank}(A) \le \min(v, b)$，故 $b \ge v$。$\square$
详见 设计与编码理论初步。
题61 [难度：竞赛]
题目：构造 $H_4$Hadamard 矩阵并导出$(4u - 1, 2u - 1, u - 1)$-设计（$u = 1$即$(3, 1, 0)$-平凡，取 $u = 2$即$(7, 3, 1)$-Fano）。
分析：Sylvester 构造 $H_4 = H_2 \otimes H_2$。
解答： $H_2 = \begin{pmatrix} 1 & 1 \newline 1 & -1 \end{pmatrix}$，$H_4 = H_2 \otimes H_2 = \begin{pmatrix} 1 & 1 & 1 & 1 \newline 1 & -1 & 1 & -1 \newline 1 & 1 & -1 & -1 \newline 1 & -1 & -1 & 1 \end{pmatrix}$。
去掉首行首列（全 1），得 $3 \times 3$矩阵$M$，将 $-1$换为$0$： $$M = \begin{pmatrix} 0 & 1 & 0 \newline 1 & 0 & 0 \newline 0 & 0 & 1 \end{pmatrix}$$ 对应 $(v, k, \lambda) = (3, 1, 0)$-设计（平凡：3 点 3 单点区组）。
更一般地，从 $H_{4u}$去首行首列得$(4u - 1, 2u - 1, u - 1)$-对称设计。$u = 2$时$H_8 \to (7, 3, 1)$-Fano 平面。$\square$
详见 设计与编码理论初步。
题62 [难度：进阶]
题目：构造 $[7, 4, 3]_2$ Hamming 码并说明其纠错能力。
分析：Hamming 码校验矩阵 $H$列为$\mathbb{F}_2^3$ 的所有非零向量。
解答： 校验矩阵 $H$（$3 \times 7$）： $$H = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \newline 0 & 1 & 1 & 0 & 0 & 1 & 1 \newline 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$$ 列依次为 $1, 2, 3, 4, 5, 6, 7$ 的二进制表示。
码 $C = \lbrace x \in \mathbb{F}_2^7 : Hx = 0\rbrace $，维数 $7 - 3 = 4$，故 $|C| = 2^4 = 16$。
最小距离 $d = 3$：$H$任意 2 列线性无关（不同非零向量），故无重量$\le 2$ 码字；存在 3 列相关（如列 1, 2, 3 和为 0），故有重量 3 码字。
纠错：$d = 3$可纠正$\lfloor 3/2 \rfloor = 1$个错误。译码：收到$y$，计算 $Hy$（syndrome），等于 $H$第$i$列则在第$i$ 位翻转。完美码：达到 Hamming 界。$\square$
详见 设计与编码理论初步。
二十、综合题
题63 [难度：竞赛]
题目（CMO 风格）：$n$个男生$n$个女生，每个男生恰认识$k$个女生，每个女生恰认识$k$个男生。证明可以安排$n$ 对舞伴使每对互相认识。
分析：$k$-正则二部图必有完美匹配（题29）+ 双计数验证。
解答： 构造二部图 $G$（男生 $X$、女生 $Y$），认识连边。$X$每点度$k$，$Y$每点度$k$（由对称条件），故 $G$为$k$-正则二部图。
由题29（Hall 定理 + 正则性），$G$有完美匹配，即$n$ 对舞伴安排存在。$\square$
双计数验证条件自洽
$X$总边数$nk$=$Y$总边数$nk$ ✓。
题64 [难度：竞赛]
题目（IMO 2011 题2 风车简化版）：平面上 $2n+1$个点一般位置，证明存在一点$P$使以$P$为中心的「风车」旋转一周时，两侧点数始终为$n$和$n$。
分析：选取 $P$为某点，分析过$P$ 直线旋转时两侧点数变化。
解答（要点）： 取 $P$为凸包上的点。过$P$的直线$l$ 旋转时，其他点从一侧到另一侧的「越过」事件按角度排序。$l$从某初始位置旋转$\pi$后回到原方向但点在另一侧。由于$2n$个其他点，某时刻两侧恰$n, n$。
关键：选择初始 $l$使一侧恰$n$点（由中间角度），旋转过程中点数差$\Delta$每越过一点变化$\pm 1$，$\pi$周期内$\Delta$从$0$变$0$经过$\pm 1$... 严格证明见 组合几何。$\square$
题65 [难度：竞赛]
题目（TST 风格）：证明 $R(4, 4) \ge 18$ 的构造下界。
分析：构造 $K_{17}$的 2-染色无单色$K_4$。
解答（构造思路）： 用 $\mathbb{Z}_{17}$的二次剩余构造：将$\lbrace 1, 2, \ldots, 16\rbrace $中模 17 的二次剩余$Q = \lbrace 1, 2, 4, 8, 9, 13, 15, 16\rbrace $（8 个）和二次非剩余 $N$（8 个）。边 $ij$染红若$j - i \in Q$，染蓝若 $j - i \in N$。
此为 Paley 图 $P(17)$。$P(17)$的对称性使得无单色$K_4$（需验证：每个 4-子集中必有两点差在 $Q$、两点差在 $N$）。详细验证依赖二次剩余性质，见 拉姆齐理论与极图理论 与 组合数论与加法组合。
故 $R(4, 4) > 17$，结合上界 $R(4, 4) \le 18$（精确值 $R(4, 4) = 18$）。$\square$
题66 [难度：进阶]
题目（伯特兰投票定理）：候选人 A 得 $a$票、B 得$b$ 票（$a > b$）。证明：A 在整个计票过程中始终严格领先 B 的概率为 $\dfrac{a - b}{a + b}$。
分析：将计票序列编码为格点路径，用 André 反射原理计数「坏路径」。
解答： 将 A 得票记为「向右 $\to$」、B 得票记为「向上 $\uparrow$」。计票序列对应从 $(0,0)$到$(a, b)$的格点路径，总数$\binom{a+b}{a}$。A 始终严格领先 $\Leftrightarrow$路径始终满足$x > y$（在对角线 $y = x$ 严格下方）。
- 第一步必为 A 得票（$\to$），否则 B 领先。路径从 $(0,0)$到$(1,0)$。
- 从 $(1,0)$到$(a,b)$需始终$x > y$。「坏路径」= 触碰 $y = x$ 的路径。
- 反射：对每条坏路径，找到首次触碰 $y = x$的点，将该点之前的部分关于$y = x$ 反射。$(1,0)$反射为$(0,1)$，故坏路径与从 $(0,1)$到$(a,b)$ 的路径一一对应。
- 坏路径数 $= \binom{(a-0)+(b-1)}{a-0} = \binom{a+b-1}{a}$。
好路径数 $= \binom{a+b-1}{a-1} - \binom{a+b-1}{a}$。
化简： $$\frac{(a+b-1)!}{(a-1)!\thinspace{}b!} - \frac{(a+b-1)!}{a!\thinspace(b-1)!} = \frac{(a+b-1)!}{(a-1)!\thinspace(b-1)!}\left(\frac{1}{b} - \frac{1}{a}\right) = \frac{(a+b-1)!}{(a-1)!\thinspace(b-1)!} \cdot \frac{a-b}{ab}$$
$$= \frac{a-b}{a+b} \cdot \frac{(a+b)!}{a!\thinspace{}b!} = \frac{a-b}{a+b}\binom{a+b}{a}$$
概率 $P = \dfrac{\text{好路径数}}{\binom{a+b}{a}} = \dfrac{a-b}{a+b}$。$\square$
反射原理的精髓
反射原理将「带约束的路径」问题转化为「无约束路径」问题，是双射法在格点路径计数中的巅峰应用。Catalan 数 $C_n = \frac{1}{n+1}\binom{2n}{n}$ 也是同源（$a = b = n$，允许触碰对角线）。详见 计数原理与方法 §7.1。
题67 [难度：进阶]
题目（错排问题变体 — 伯努利装错信封）：$n$封信装入$n$个信封，全部装错的方案数$D_n$。求 $D_n$的通项公式，并验证$D_5 = 44$。
分析：容斥原理。设 $A_i$= 第$i$ 封信装对的事件。
解答： 全集 $|S| = n!$。$|A_i| = (n-1)!$，$|A_i \cap A_j| = (n-2)!$，$\ldots$，$|\bigcap_{t=1}^k A_{i_t}| = (n-k)!$。
由容斥原理： $$D_n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots + (-1)^n \binom{n}{n} 0!$$ $$= n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right) = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$$
验证 $D_5$： $$D_5 = 5!\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 120 \cdot \frac{44}{120} = 44 \thickspace \checkmark$$
渐近行为
当 $n \to \infty$ 时，$D_n \approx n!/e$（因 $\sum_{k=0}^{\infty} \frac{(-1)^k}{k!} = e^{-1}$）。即随机排列为错排的概率趋于 $1/e \approx 0.368$。详见 计数原理与方法 §5 与 §9（Möbius 反演视角）。$\square$
总结
组合数学题目集共 65 题，覆盖容斥原理、排列组合计数、鸽巢原理/拉姆齐、生成函数、二项式恒等式、图论基础、染色问题、组合极值与构造、双计数法、卡特兰数、Hall 婚姻定理与匹配、网络流与最小割、平面图与 Euler 公式、Ramsey 数与极图、组合几何、概率方法、Pólya 计数、组合数论与加法组合、设计与编码、综合题二十大主题，从一试基础到 CMO/TST/IMO 高档竞赛全面覆盖。