← BMO 备考详情开始专项练习 →
组合与博弈
Combinatorics & Games
考点概述
组合与博弈在 BMO 证明题里出现极频。主力武器是：**鸽巢原理**（关键在抽屉设计）、**极值原理**（取最大/最小配置再微调）、**不变量与单变量**（找守恒量证不可达、找单调量证终止）、**双重计数**、**归纳与构造**（分治、插入、剥离），以及 **Ramsey / Erdős–Szekeres** 型存在性。思路口诀：**「找对抽屉、取极端、找守恒量」**。
核心知识点
ESAT 考试重点
- ◆抽屉设计的常见维度：余数、最大奇因子、坐标奇偶、几何小区域
- ◆「对象数 > 取值数」型：如子集数 > 可能和数 ⇒ 两子集等和
- ◆补紧性构造（如 $\{n+1,\dots,2n\}$）证明界最优
ESAT 考试重点
- ◆「取极端 + 微调矛盾」是存在性/构造题的万能起手
- ◆常配「移动一个元素 / 交换两元素」作微调
- ◆最大割、最长路径、最小反例都属此类
ESAT 考试重点
- ◆证「不可达」找不变量（模 2 / 模 3 / 染色和）
- ◆证「终止 / 有限步」找单调量（非负整数不能无限下降）
- ◆先问：什么在操作下不变？什么在单调变化？
ESAT 考试重点
- ◆「一个量、两种数法」= 双重计数
- ◆$\sum\deg=2|E|$；奇度顶点个数为偶
- ◆局部约束（边上不等式）→ 求和 → Cauchy–Schwarz 收口
ESAT 考试重点
- ◆分治：难在「让每个子问题都满足归纳假设」（常需一块拼图桥接）
- ◆增量计数：算「加入第 $k$ 个对象新增多少」再求和
- ◆插入 / 剥离用于「可线性化 / 可匹配」的存在性
ESAT 考试重点
- ◆Ramsey：先鸽巢逼出同色邻域，再分类内部
- ◆「贴坐标标签 + 鸽巢」是 Erdős–Szekeres 的范式
- ◆组合几何存在性 → 先按凸包形状分类
考点例题精讲
以下例题重点在于理解解题思路，建议先尝试自己解，再对照讲解。
1例 1：Ramsey $R(3,3)$——六人聚会
2例 2：奇部鸽巢——$\{1,\dots,2n\}$ 取 $n+1$ 个必有整除对