概念

鸽巢原理

n+1 只鸽子放入 n 个笼子必有一笼两只，其加权与连续版本（如埃尔德什-塞凯赖什定理）能在看似混沌的序列中保证有序子结构存在。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

鸽巢原理组合数学

01定义

鸽巢原理：

n+1

只鸽子放入

n

个笼子，必有一笼至少两只。这个显然的事实在加权与推广后威力惊人——它能在看似混沌的序列中保证有序子结构的存在，是存在性证明的入门武器。

6 只鸽子进 3 个笼子：必有一笼至少两只

一般形式： $mn+1$ 个对象入 $n$ 盒，必有一盒 $\geq m+1$ 个；实数版本与积分平均值论证都是同一思想的化身。

任意 $n+1$ 个取自 $\{1,\dots,2n\}$ 的数必有一对整除；367 人中必有两人同生日；同余类划分证明存在和被 $n$ 整除的子列。

任意足够长的实数序列必含长的单调子序列——鸽巢原理在序结构上的升华，是拉姆齐式「无序中找有序」的先声。

mn+1\ \text{个对象},\ n\ \text{盒}\Rightarrow\exists\ \text{盒}\geq m+1\ \text{个}

狄利克雷 1834 年以「抽屉原理」证明丢番图逼近定理；该论证以「平均值论证」之名成为组合学、数论与理论计算机科学的日常工具。

哈希冲突的必然性分析、数据压缩的下界论证、拉姆齐理论的下界构造——「存在性不需要构造」的最简范例。

鸽巢原理：m 只鸽入 n 巢必有满巢增大 m 或减小 n，观察最大巢数 ≥ ⌈m/n⌉

m 鸽子数13n 巢数4