# 斯本纳引理（Sperner’s Lemma）是什么？ > **一句话**：如果把一个大三角形（或更高维单纯形）切成很多小三角形，并按一定“边界规则”为顶点涂色，那么**一定**能在里面找到一块“小三角形”三顶点三种颜色都不同。 > 直观比喻 > > - 把大三角形想成“国家”，边界规定了语言只能用两种；内部城市随便说话。 > > - 无论你怎么给城市分区、随便分配语言，都必然会出现一个小区，三个城市分别说三种不同语言。 > # 1 ▪ 最简单的二维版本 1. **准备**： - 画一个大等边三角形 ABC。 - 随意把它用线段切成许多小三角形（“三角剖分”）。 2. **着色规则（斯本纳条件）**： - 顶点 A 只能涂 **红色 1** - 顶点 B 只能涂 **绿色 2** - 顶点 C 只能涂 **蓝色 3** - 大三角形每条边上，其端点两种颜色之间，只能使用这**两种**（不能出现第三种）。 > 例如 AB 边上只能涂 1 或 2，不能出现 3。 3. **随意涂色**：内部顶点你爱怎么涂就怎么涂，只要满足上面边界规则。 4. **斯本纳引理结论**： - 在这些小三角形中，**必定至少存在 1 个** “红‑绿‑蓝” 三色全具的小三角形！ - 并且其个数一定是 **奇数**（1 个、3 个、5 个…）。 --- # 2 ▪ 为什么成立？（极简思路） - **把 AB 边视为 1‑2 电缆**： - 沿着剖分边缘走，只要遇到 “1‑2” 边就算一条“电缆”。 - **统计奇偶**： - 大三角形整条 AB 边本身是 1‑2，一定贡献 1 条“电缆”出口。 - “电缆”只能在小三角形内部**成对进出**，除非在某个小三角形里被三色顶点“截断”。 - 于是总出口数 = 截断次数 (mod 2)。 - 因为出口是 1 条奇数 ⇒ 截断次数也奇数 ⇒ 至少 1 个三色小三角。 > 这就是经典的“奇偶计数”证明，完整推导可在教材中看到。 --- # 3 ▪ 高维版本（一句话） - 把“大三角形”换成 **n 维单纯形**（n + 1 个顶点的凸包）； - 把“小三角剖分”换成 **单纯形剖分**； - 把“着色”换成把每个顶点标号为 {1…n + 1}，并对每个面使用对应编号子集； - 结论：一定存在至少一个 **完整标号的 n 维小单纯形**。 --- # 4 ▪ 有什么用？ | 应用 | 说明 | | ----------------- | --------------------------------------------------------------- | | **Brouwer 不动点定理** | 斯本纳引理可视为 Brouwer 不动点定理的“离散版本”；对单纯形不断细分并施加颜色映射，极限可推出“连续函数必有不动点”。 | | **游戏论 / 经济学** | 闭包配对、[[纳什均衡]]存在性证明常用它的高维变体 (KKM‑lemma)。 | | **公平切蛋糕 / 划分土地** | “必须存在三色小块”对应必须存在一个“所有人都同意的公平份额”。| | **计算拓扑** | 算法式证明：可把不动点问题转化为在网格上搜索三色单元，衍生 PPAD 复杂度结果（如 END‑OF‑THE‑LINE）。| | **编程竞赛** | 少见但偶尔出现离散拓扑题：“给定剖分和着色，证明存在三色小三角并定位其索引”。| --- # 5 ▪ 动手体验 1. 在方格纸上画大三角，手工剖分 10‑20 个小三角。 2. 照边界规则随意掷骰子着色。 3. 找到一个红‑绿‑蓝三角；如果时间允许，数一数总共有多少个——你会发现必是奇数。 4. 用 Python + networkx 写个 DFS 检测“1‑2” 边条数，也能印证奇偶性。 --- ## 小结 - **斯本纳引理 = “离散版不动点定理”**：给定边界限制，内部必出现全色小单元。 - 思想核心是 **奇偶计数 / 路径配对**，证明非常朴素，但威力巨大。 - 牢记它与 Brouwer、KKM、纳什、PPAD 的链式关系，今后看到“不动点”“公平分割”“配对路径”类问题就能想到它。