Chap19 组合数学引言、鸽巢原理与 Ramsey 定理
返回：0100 离散数学课程总目录 · 上一章：0118 格与布尔代数 · 下一章：0120 计数原则、排列组合与组合恒等式
1、学习目标
本章进入组合存在性。它不急着数“有多少种”，而是先问：在对象足够多、模式足够少的情况下，某种结构是否必然出现。
主线：
1 | 组合数学引言：一一对应、数学归纳法、上下界逼近。 |
本章要能熟练处理：
1 | 1. 找出题目里的“鸽子”和“巢”。 |
本站页面编号是 0119，但课件与习题内部称为“第二十章/习题二十”。下面的习题答案按教材题号写成 20.1-20.20。
2、组合数学的基本技巧
组合数学常见内容包括：
1 | 组合存在：鸽巢原理、Ramsey 定理、Hall 定理。 |
本章重点是存在性，常用三种技巧。
一一对应
把难数的对象换成好数的对象。
例子：
1 | 3 x 3 x 3 的立方体切成 27 个小立方体至少要 6 次。 |
再如：
1 | n 个选手两两比赛决出冠军，需要 n-1 场。 |
数学归纳法
常见形式：
1 | 第一归纳法：P(0) 真，P(n)=>P(n+1)。 |
Ramsey 定理的存在性证明就会用到归纳法。
上下界逼近
确定某个最小值时通常分两步：
1 | 1. 证明上界：足够大时一定能做到。 |
如果上界和下界相等，就得到精确值。
例如：
1 | R(3,3)=6 |
3、鸽巢原理
简单形式
1 | n+1 个物体放入 n 个盒子，则至少有一个盒子含有 2 个或更多物体。 |
典型证明方法：
1 | 反证：若每个盒子最多 1 个物体，则总物体数最多 n 个，矛盾。 |
一般形式
设 q1,q2,...,qn 是正整数，若把：
1 | q1+q2+...+qn-n+1 |
个物体放入 n 个盒子，则至少出现下面某一种情况：
1 | 第 1 个盒子至少 q1 个； |
特别地，若每个盒子的阈值相同，q1=...=qn=r，则：
1 | n(r-1)+1 个物体放入 n 个盒子 |
函数形式：
1 | f:A -> B，|A|=m，|B|=n |
等价公式：
1 | ceil(m/n) = floor((m-1)/n)+1 |
常见建模
余数类：
1 | 证明整除、差可整除、循环小数、只含 0/7 的倍数。 |
前缀和：
1 | 证明存在连续子段，使子段和满足某个条件。 |
奇偶模式：
1 | 空间格点的坐标奇偶性只有 8 种。 |
序列模式：
1 | 若长度 n^2+1 的实数序列没有长 n+1 的递增子序列， |
鸽巢题最关键的一步不是套公式，而是把“对象”和“模式”找出来。对象是鸽子，模式是巢。
4、Ramsey 定理
简单 Ramsey 数
R(p,q) 表示最小正整数 n，使得当 n 个顶点的完全图 K_n 的边任意红蓝染色时，必有：
1 | 蓝色 K_p |
也可以交换红蓝颜色，所以：
1 | R(p,q)=R(q,p) |
基础值：
1 | R(a,2)=R(2,a)=a |
递推上界：
1 | R(p,q) <= R(p-1,q)+R(p,q-1) |
证明思路：
1 | 取一个顶点 v。 |
图语言与集合语言
图语言：
1 | K_n 的边红蓝染色。 |
集合语言：
1 | 设 S 是 n 元集。 |
集合语言可以推广到 r 元子集。
一般 Ramsey 数
记：
1 | R(q1,q2,...,qk; r) |
含义：
1 | 把 n 元集 S 的所有 r 元子集划分成 k 类 T1,T2,...,Tk。 |
特殊情况：
1 | r=1：退化为鸽巢原理 |
已知典型值：
1 | R(3,3)=6 |
5、相异代表系与置换矩阵
虽然本页课件主体是鸽巢原理和 Ramsey 定理，但习题二十后半部分出现了相异代表系。
设有集合族：
1 | A1,A2,...,An |
若可以选择：
1 | x1 in A1, x2 in A2, ..., xn in An |
且：
1 | x1,x2,...,xn 两两不同 |
则 <x1,x2,...,xn> 是这个集合族的相异代表系。
Hall 条件：
1 | 集合族 A1,...,An 存在相异代表系 |
置换矩阵分解可理解为二分图完美匹配的反复选取：如果一个非负整数矩阵行列和都相等，就可以逐次选取置换矩阵并相减。
6、证明套路
鸽巢题：
1 | 1. 明确要证明的“重复/拥挤/存在”是什么。 |
Ramsey 题：
1 | 1. 把图 G 与补图翻译成 K_n 的红蓝染色。 |
相异代表系题：
1 | 1. 列出每个集合的可选代表。 |
7、习题二十答案速查
20.1、三角形内放点
题目：
1 | 边长为 1 的等边三角形内任意放 10 个点， |
答案：
1 | 把大三角形划分成 9 个边长为 1/3 的小等边三角形。 |
一般化：
1 | 把边长 1 的等边三角形划分成 n^2 个边长 1/n 的小等边三角形。 |
所以：
1 | m_n = n^2+1 |
20.2、有理数小数展开循环
设有理数写成既约分数：
1 | p/q，q>0 |
做十进制除法时，每一步余数只能取：
1 | 0,1,2,...,q-1 |
若余数为 0，小数展开有限；若余数一直不为 0，非零余数只有 q-1 种，鸽巢原理保证某两个步骤余数相同。余数相同后，后续除法过程完全重复，因此小数从某一位开始循环。
20.3、只由 0 和 7 构成的倍数
考虑 N 个数：
1 | 7, 77, 777, ..., 77...7 |
若某个数除以 N 余 0，结论成立。
否则 N 个余数都在：
1 | 1,2,...,N-1 |
中，必有两个余数相同。设第 i 项和第 j 项余数相同，i<j，则二者差：
1 | 77...700...0 |
只由 7 和 0 组成，并且能被 N 整除。
20.4、差与和的整除
第一问：
1 | n+1 个正整数除以 n，只有 n 种余数。 |
第二问：
设 n+2 个正整数除以 2n 的余数为：
1 | r1,r2,...,r_{n+2} |
若有两个余数相同，则对应整数的差能被 2n 整除。
否则把余数分成 n+1 组：
1 | {0}, {1,2n-1}, {2,2n-2}, ..., {n-1,n+1}, {n} |
n+2 个不同余数放入 n+1 组，必有两个落入同一组。它们要么同余相等，要么互补到 2n，于是对应整数的差或和能被 2n 整除。
20.5、连续若干天正好 13 小时
令：
1 | a_i = 第 1 天到第 i 天的累计复习时数 |
每天至少 1 小时，所以：
1 | 1 <= a1 < a2 < ... < a37 <= 60 |
再考虑：
1 | a1+13, a2+13, ..., a37+13 |
这 74 个数：
1 | a1,...,a37,a1+13,...,a37+13 |
都在 1..73 之间，因此必有两项相等。只能是：
1 | a_i+13 = a_j |
于是从第 i+1 天到第 j 天正好复习：
1 | a_j-a_i=13 |
小时。
20.6、认识人数相同
设组内有 n 个人，每个人认识的人数只能取：
1 | 0,1,2,...,n-1 |
如果所有人的认识人数都不同，则必同时有人认识 0 人和有人认识 n-1 人。
但若某人认识 n-1 人，他认识所有人，就不可能另有一个人认识 0 人。矛盾。
因此必有两个人在组内认识人数相同。
20.7、每年至少且至多三个 13 日是星期五
设：
1 | a1,a2,...,a12 |
分别表示 1 月 13 日到 12 月 13 日是星期几。
至少一个星期五：
1 | 若没有星期五，则 ai 只能取另外 6 种星期值。 |
至多三个星期五：
1 | 同一个星期值在 12 个 13 日中最多出现 3 次。 |
答案中的典型重复组为：
1 | a2=a3=a11 |
闰年情形同理处理。
20.8、盒子中最多与至少的精确界
要证：
1 | m 个球放入 n 个盒子，至少有一个盒子含有 floor((m-1)/n)+1 个球。 |
因为：
1 | floor((m-1)/n)+1 = ceil(m/n) |
由鸽巢原理函数形式，至少一个盒子含有 ceil(m/n) 个球。
另一方面，设：
1 | m=nq+r，0<=r<n |
若 r=0，每盒放 q 个；若 r>0，r 个盒子放 q+1 个，其余放 q 个。这样没有盒子超过：
1 | ceil(m/n)=floor((m-1)/n)+1 |
所以这个界是最好的。
20.9、球数小于 n(n-1)/2 时必有两个盒子球数相同
设 n 个盒子中的球数为：
1 | a1,a2,...,an |
若两两不同，则最小可能取值只能是：
1 | 0,1,2,...,n-1 |
总数至少：
1 | 0+1+...+(n-1)=n(n-1)/2 |
与题设：
1 | m < n(n-1)/2 |
矛盾。因此至少有两个盒子的球数相同。
20.10、36 个扇形中三个连续扇形和至少 56
圆盘有 36 个连续三扇形块。把所有连续三扇形块的数字和加起来时，每个数字恰好被计数 3 次，所以总和为：
1 | (1+2+...+36)*3 = 37*18*3 |
平均每个连续三扇形块的和为：
1 | (37*18*3)/36 = 55.5 |
因此至少有一个连续三扇形块的和不小于：
1 | ceil(55.5)=56 |
20.11、Ramsey 数的二项式上界
要证教材定理推论：
1 | R(p,p) <= C(2p-2,p-1) <= 2^(2p-2) |
更一般地可证明：
1 | R(p,q) <= C(p+q-2,p-1) |
用归纳法配合 Ramsey 递推：
1 | R(p,q) <= R(p-1,q)+R(p,q-1) |
以及 Pascal 恒等式：
1 | C(p+q-3,p-2)+C(p+q-3,p-1)=C(p+q-2,p-1) |
令 p=q 得：
1 | R(p,p) <= C(2p-2,p-1) |
又因为 C(2p-2,p-1) 是 (1+1)^(2p-2) 展开式中的一项，所以：
1 | C(2p-2,p-1) <= 2^(2p-2) |
20.12、10 个顶点图中的团或独立集
把图 G 的边染成蓝色，把补图 G' 的边染成红色。于是题目等价于：
1 | K10 任意红蓝染色，必有蓝色 K3 或红色 K4。 |
由 Ramsey 递推：
1 | R(3,4) <= R(2,4)+R(3,3)=4+6=10 |
所以任意 10 个顶点的图 G 中，必存在：
1 | 大小为 3 的团 |
20.13、证明 R(r,r,q;r)=q
这里是一般 Ramsey 数：
1 | R(r,r,q;r) |
表示把 r 元子集分成三类时的 Ramsey 数。
上界：
1 | 令 S 为 q 元集。 |
所以上界为 q。
下界：
1 | 若 |S|=q-1，把所有 r 子集都放入 T3。 |
因此：
1 | R(r,r,q;r)=q |
20.14、Ramsey 数的单调性
设：
1 | Q=max{q1,q2,...,qn} |
任取 m 元集 S，把所有 r 元子集划分成 n 类。由 m 的定义，存在某一类 Ti，使得 S 中有 Q 个元素，其所有 r 元子集都属于 Ti。
由于：
1 | Q >= qi |
从这 Q 个元素中任取 qi 个，仍然得到第 i 类的齐次 qi 元子集。
所以：
1 | R(Q,Q,...,Q;r) >= R(q1,q2,...,qn;r) |
20.15、证明 R(3,5)=14
上界：
1 | R(3,5) <= R(2,5)+R(3,4)=5+9=14 |
下界：
1 | 构造一个 13 个顶点的图 G， |
答案给出的反例可以取循环图：
1 | C(2,3) |
即顶点标记为 0,1,...,12，当两个顶点差模 13 等于 ±2 或 ±3 时连边。这个图没有 K3，补图没有 K5。因此：
1 | R(3,5) >= 14 |
综合上下界：
1 | R(3,5)=14 |
20.16、四个文件的一位识别码
文件代码：
1 | A: 123 |
可以选：
1 | A -> 3 |
四个代表数字互不相同，因此可以用一位代码识别。
20.17、确定相异代表系
第一组：
1 | A1={1,2}, A2={2,3}, A3={3,4}, A4={4,5}, A5={5,1} |
所有相异代表系：
1 | <1,2,3,4,5> |
第二组：
1 | A1={1,2}, A2={2,3}, ..., An={n,1} |
所有相异代表系：
1 | <1,2,...,n> |
20.18、四个码字的所有存入方法
码字：
1 | abcd, cde, ab, ce |
若存入方法记为：
1 | <x1,x2,x3,x4> |
其中 x1 来自 abcd，x2 来自 cde，x3 来自 ab，x4 来自 ce，且四个字母互不相同。
所有方法：
1 | <a,c,b,e> |
20.19、证明 Ai={1,…,n}-{i} 存在相异代表系
设：
1 | Ai={1,2,...,n}-{i}, i=1,2,...,n, n>=2 |
用 Hall 条件。任取 k 个集合：
1 | Ai1,Ai2,...,Aik |
若 k=1：
1 | |Ai1|=n-1>=1 |
若 k>1，因为至少选了两个不同的缺失元素，这些集合的并集就是：
1 | {1,2,...,n} |
所以：
1 | |Ai1 ∪ Ai2 ∪ ... ∪ Aik| = n >= k |
Hall 条件成立，因此存在相异代表系。
20.20、矩阵分解为置换矩阵之和
给定矩阵：
1 | M = |
每一行、每一列的和都是 6，可分解为 6 个置换矩阵之和。用“每行 1 所在列”的向量表示置换矩阵：
1 | P1 = <1,2,3,4,5> |
于是：
1 | M = P1+P2+P3+P4+P5+P6 |
其中每个 Pi 都是一个 0-1 置换矩阵。
8、复盘清单
1 | 1. 鸽巢原理：对象多于模式时，必有重复或拥挤。 |
微信
支付宝
