一个每天早上都会遇到的问题

抽屉里有五种颜色的袜子。天还没亮，你要摸黑找出一双配对的袜子。问题是：至少要摸出多少只，才能保证无论运气多差都有一双同色的？

答案是 $6$。最坏的情况是前五只恰好各是一种颜色，那么第六只无论是什么颜色，都会与已经摸出的某一只配成一对。

这个推理之所以成立，是因为只有 $5$ 种颜色，而你拿出了 $6$ 只。课程用鸽子和鸽笼来命名这件事：把 $n$ 只鸽子放进 $m$ 个笼子，只要 $n>m$，就一定有至少两只鸽子挤在同一个笼子里。

原理本身简单得像废话，但它的力量来自换一个角度看问题：难点从来不是原理，而是判断「什么是鸽子、什么是笼子」。这一讲用五个越来越难的例子反复训练这件事。

时间轴

课程定位

这门课的目标不只是讲数学，还要教怎样把证明写得清楚。课程把好的证明比作好的代码：模块化、把复杂的部分抽成引理、让读者在读到细节之前就看见整体蓝图。

这一讲一边讲鸽巢原理，一边示范三件事：

1. 先声明证明方法（例如「我们用反证法」），别让读者读到最后才知道在干什么。
2. 给记号起有意义的名字（$I_s$ 里的 $I$ 代表 increasing）。
3. 区分「数学上必需的步骤」与「帮助读者理解的教学性步骤」。

原理的精确陈述

鸽巢原理（基本形式）。 设 $n$ 只鸽子被放进 $m$ 个笼子。若 $n>m$，则至少有一个笼子里至少有两只鸽子。

鸽巢原理（定量形式）。 若 $n$ 只鸽子放进 $m$ 个笼子，则至少有一个笼子里至少有 $\left\lceil n/m \right\rceil$ 只鸽子。

用反证法证明定量形式

假设结论不成立，即每个笼子里至多有 $\lceil n/m\rceil-1$ 只鸽子。设第 $h$ 个笼子里有 $N_h$ 只，则

$$N_h\le \left\lceil \frac{n}{m}\right\rceil-1<\frac{n}{m}$$

对每个 $h$ 成立。把所有笼子加起来：

$$n=\sum_{h=1}^{m}N_h<\sum_{h=1}^{m}\frac{n}{m}=n .$$

得到 $n<n$，矛盾。所以必有某个笼子装有至少 $\lceil n/m\rceil$ 只鸽子。$\square$

证明的关键只有一步：用两种方式数同一批鸽子。一边按笼子求和，一边知道总数是 $n$。这个「双重计数」的套路会在整门课里反复出现。

课程把证明过程本身当作教学材料：开头就写明「用反证法」，让读者提前知道方向；证明结束时明确宣布矛盾来自哪里。这些细节不影响正确性，却决定读者能不能跟上。

应用一：聚会上认识同样多的人

命题。 一个聚会上有 $n\ge 2$ 个人（包括你自己）。那么无论谁在场，总能找到两个人，他们认识的其他人的数目相同。

这看起来和抽屉毫无关系。把它翻译成图论就好了。

建模：人 = 顶点，认识 = 边

把每个人画成一个顶点，两人认识就画一条边。这样得到一个有 $n$ 个顶点的简单图。

顶点的度数是与之相连的边数，也就是这个人认识的人数。于是原命题变成：任意 $n\ge2$ 个顶点的简单图中，必有两个顶点度数相同。

第一次尝试：为什么差一点

用度数当笼子、顶点当鸽子。每个顶点的度数在 $\{0,1,\dots,n-1\}$ 中，共 $n$ 个可能的取值；而顶点也有 $n$ 个。鸽子和笼子一样多，原理用不上——它要求严格大于。

关键观察：$0$ 与 $n-1$ 不能同时出现

• 若有人认识其余所有人，则他的度数为 $n-1$；这意味着他认识每一个人，因此没有人是「谁都不认识」的，度数 $0$ 不可能出现。
• 若没有人度数为 $n-1$，那么所有度数都在 $\{0,1,\dots,n-2\}$ 中，只有 $n-1$ 个可能值。

分两种情况：

情形一：存在度数为 $n-1$ 的顶点。 此时度数 $0$ 不出现，笼子只有 $n-1$ 个；$n$ 只鸽子进 $n-1$ 个笼子，必有两个同度数。

情形二：不存在度数为 $n-1$ 的顶点。 所有度数落在 $\{0,\dots,n-2\}$ 中，同样只有 $n-1$ 个笼子，结论相同。

两种情形合起来覆盖了所有可能，命题得证。$\square$

这个例子的价值在于：鸽子和笼子不是天然存在的，需要先找到正确的抽象（图），再修正笼子的数量。课程特意保留了「第一次尝试失败」的过程，因为真实的证明就是这样摸索出来的。

应用二：20 个四位数里的同和子集

命题。 给定任意 $20$ 个严格正的四位数 $x_1,\dots,x_{20}$，一定存在两个不相交的非空子集，其元素之和相等。

三句话就能说清的问题，证明却不显然。先把英文陈述翻译成数学：

要找集合 $I,J\subseteq\{1,\dots,20\}$，满足

$$I\ne\varnothing,\qquad J\ne\varnothing,\qquad I\cap J=\varnothing,\qquad \sum_{i\in I}x_i=\sum_{j\in J}x_j .$$

选鸽子与笼子

• 鸽子：非空子集。共有 $2^{20}-1$ 个。
• 笼子：可能出现的和。最大的和小于 $20\times 10^4=2\times 10^5$，而每个和都是非负整数，所以笼子不到 $2\times 10^5$ 个。

为什么非空子集有 $2^{20}-1$ 个？每个元素有两种命运——被选入或不被选入，对应一个 $20$ 位的 0-1 串；共有 $2^{20}$ 个串，再减去「一个都不选」的空集。这个「子集 ↔ 0-1 串」的对应就是最朴素的双射，后面讲计数时会正式展开。

数一下：$2^{20}-1=1\,048\,575>200\,000$。鸽子远多于笼子，于是存在两个不同的非空子集 $A\ne B$，其和相等。

陷阱：$A$ 与 $B$ 可能相交

鸽巢原理只保证「两个不同子集同和」，没有保证它们不相交。如果 $A$ 与 $B$ 都含有 $x_1$，结论就不符合要求。

修正办法：把公共部分同时删掉。令

$$I=A\setminus B,\qquad J=B\setminus A .$$

这两个集合显然不相交。又因为

$$\sum_{i\in A}x_i=\sum_{j\in B}x_j,$$

两边同时减去公共部分 $\sum_{k\in A\cap B}x_k$，得到

$$\sum_{i\in I}x_i=\sum_{j\in J}x_j .$$

所以 $I$ 与 $J$ 仍然同和。

为什么 $I$、$J$ 非空

还需要检查最后这个技术条件。假设 $I=\varnothing$，则 $A\subseteq B$，且

$$0=\sum_{i\in I}x_i=\sum_{j\in J}x_j .$$

由于所有 $x_j$ 都是正数，若干正数之和为零只能是一个都没取，即 $J=\varnothing$。于是 $A\subseteq B$ 且 $B\subseteq A$，得 $A=B$，与 $A\ne B$ 矛盾。所以 $I\ne\varnothing$；同理 $J\ne\varnothing$。$\square$

存在不等于找得到

这个结论有个耐人寻味的地方：它保证了同和子集存在，却没有给出找它们的办法。要从 $2^{20}$ 个子集里挑出碰撞的一对，直接搜索是指数级的。课程提到，国家人口这类现实数据中确实存在人口数完全相同的国家子集，但没有人知道更快的算法；这与密码学中的一些问题相关。

用这节课的话说：证明存在性，比构造出对象容易得多。

应用三：每个排列都有很长的单调子序列

定理（Erdős–Szekeres）。 任意 $nm+1$ 个不同实数的排列中，要么存在长度为 $n+1$ 的递增子序列，要么存在长度为 $m+1$ 的递减子序列。

先解释术语：

• 排列：把 $1,2,\dots,nm+1$ 打乱顺序排成一列。
• 子序列：从原序列中按原顺序选出的若干项，不要求相邻。

取 $n=m=3$，考虑 $10$ 个数的排列

$$3,\ 2,\ 1,\ 6,\ 5,\ 4,\ 9,\ 8,\ 7,\ 10 .$$

递增子序列 $3,6,9,10$ 的长度是 $4=n+1$，正好达到定理的承诺。这个例子也是紧的：最长的递减子序列只有长度 $3$（例如 $3,2,1$），达不到 $m+1=4$。

证明：给每个位置记两个数

这是本讲最精细的构造。对序列的第 $s$ 个位置，定义

• $I_s$：以第 $s$ 项结尾的最长递增子序列的长度；
• $D_s$：以第 $s$ 项结尾的最长递减子序列的长度。

注意「以第 $s$ 项结尾」这个限制很重要。它让每个位置都有一对唯一的「进度标记」$(I_s,D_s)$。

引理。 若 $s\ne t$，则 $(I_s,D_s)\ne(I_t,D_t)$。

证明。 不妨设 $s>t$（否则交换两者）。记第 $s$ 项为 $a_s$，第 $t$ 项为 $a_t$。由于所有项互不相同，只有两种可能：

• 若 $a_s>a_t$：取以第 $t$ 项结尾、长度为 $I_t$ 的递增子序列，再接上 $a_s$。因为 $s>t$（$a_s$ 在后面）且 $a_s>a_t$，得到的仍是递增子序列，长度为 $I_t+1$。所以 $I_s\ge I_t+1>I_t$。
• 若 $a_s<a_t$：同理，取以第 $t$ 项结尾、长度为 $D_t$ 的递减子序列，再接上 $a_s$，得到长度 $D_t+1$ 的递减子序列，所以 $D_s\ge D_t+1>D_t$。

两种情况都使两个有序对至少有一个坐标不同，故 $(I_s,D_s)\ne(I_t,D_t)$。$\square$

收尾：计算笼子的数量

用反证法。假设定理不成立，即不存在长度为 $n+1$ 的递增子序列，也不存在长度为 $m+1$ 的递减子序列。于是对每个位置 $s$，

$$1\le I_s\le n,\qquad 1\le D_s\le m .$$

有序对 $(I_s,D_s)$ 至多有 $n\cdot m$ 种取值——这就是 $nm$ 个笼子。而序列共有 $nm+1$ 个位置，也就是 $nm+1$ 只鸽子。由鸽巢原理，必有两个不同位置 $s\ne t$ 落在同一个笼子里，即

$$(I_s,D_s)=(I_t,D_t),$$

与引理矛盾。因此假设不成立，定理得证。$\square$

为什么这个构造能想到

课程坦率地说：在考场上凭空想出这个定义几乎不可能。它的来源是动态规划的思路——如果想知道「以这里结尾的最长递增子序列有多长」，就要把前面子问题的答案拼起来。而一旦固定了结尾元素，只需要知道「长度」和「是否递增」这两条信息，就足以判断能否接上下一项。

这也解释了这个证明为什么优雅：它把「子序列的长度」这个看似需要记住整条序列的信息，压缩成了一对数。

趣味应用：每个人的家谱里都有近亲

命题。 每个人的祖先中，都存在一个人的父母是血亲。

证明只用四条关于生物学的、几乎无法反驳的假设：

1. 每个人都有两位生物学父母。
2. 没有人能在 $100$ 岁以后生育。
3. 人类至少已有 $4000$ 年历史。
4. 历史上存在过的人类总数至多 $10^{12}$。

建模：祖先位置 = 顶点

从你出发向上追溯：父母 $2$ 人，祖父母 $4$ 人，曾祖父母 $8$ 人……第 $k$ 代祖先有 $2^k$ 个「位置」。这些位置是角色，不是具体的人——「母亲的父亲」和「父亲的母亲」是两个不同的位置，可能恰好是同一个人。

由假设 2 和 3，向上追溯的代数至少是

$$\frac{4000}{100}=40 .$$

所以祖先位置的数目至少是

$$2^{40}=1\,099\,511\,627\,776>10^{12} .$$

而在整部人类历史中，活过的人至多 $10^{12}$ 个。角色比人多了至少约 $10\%$，由鸽巢原理，至少有两个不同的祖先位置由同一个人占据。

同一个人出现在你祖先树的两个不同位置，说明你的祖先谱系中出现了「汇合」：沿着两条不同的路径向上追溯会走到同一个人。这意味着这个人的两条后代线最终结合，也就意味着存在某位祖先，其父母之间有血缘关系。$\square$

严格地说，最后一步还需要一个小论证：若两条路径在某人处汇合，则这个人的两个不同后代（沿两条线）后来结合，这两条线的另一端共享同一个祖先，从而构成近亲繁殖。课程把它作为直观结论给出，重点在于展示「把生物学事实翻译成计数」的威力。

概率的形式化：为后面几讲做准备

课程在最后给出概率论的基本框架，为下一讲的条件概率做铺垫。

样本空间

样本空间 $\Omega$ 是所有可能结果的集合。掷一枚普通骰子，$\Omega=\{1,2,3,4,5,6\}$。

样本空间可以是无限的。例如「一直抛硬币，直到第一次出现正面」所需的次数，理论上可以是任意正整数，$\Omega=\{1,2,3,\dots\}$。

概率

对每个结果 $x\in\Omega$ 指定一个实数 $p(x)$，满足两条公理：

$$p(x)\ge 0\quad\text{对一切 }x\in\Omega, \qquad \sum_{x\in\Omega}p(x)=1 .$$

公平骰子取 $p(x)=1/6$。无限样本空间同样可以满足这两条：例如

$$p(k)=2^{-k}\quad(k=1,2,3,\dots), \qquad \sum_{k=1}^{\infty}2^{-k}=1,$$

它恰好描述「第 $k$ 次才抛出正面」的概率。

事件与补事件

事件是样本空间的子集 $E\subseteq\Omega$，其概率定义为其中各结果概率之和：

$$P(E)=\sum_{x\in E}p(x).$$

例如掷出偶数对应 $E=\{2,4,6\}$，概率为 $1/2$。

补事件 $\overline{E}$（也写作 $\neg E$）是 $\Omega$ 中不属于 $E$ 的一切。因为 $E$ 与 $\overline{E}$ 不相交且并为 $\Omega$，

$$P(E)+P(\overline{E})=\sum_{x\in\Omega}p(x)=1,$$

于是

$$P(\overline{E})=1-P(E).$$

这条简单公式后面会频繁使用：正面算不清楚时，就算反面。

本节结论

• 鸽巢原理：$n$ 只鸽子进 $m$ 个笼子，若 $n>m$ 则某笼至少两只；定量版本给出 $\lceil n/m\rceil$。
• 证明的核心是双重计数：按笼子求和与按总数计算必须一致。
• 应用的关键从来不是原理，而是选出正确的「鸽子」与「笼子」：
  • 聚会问题：顶点是鸽子，度数是笼子；再用「$0$ 与 $n-1$ 互斥」把笼子减一。
  • 子集和问题：非空子集是鸽子，可能的和是笼子；相交时删去公共部分。
  • 最长子序列：位置是鸽子，有序对 $(I_s,D_s)$ 是笼子。
  • 家谱问题：祖先位置是鸽子，历史总人口是笼子。
• 存在性证明不等于构造算法：同和子集确实存在，但快速找出它们仍是难题。
• 概率的三件套：样本空间、概率公理、事件与补事件。

理解检验

1. 抽屉里有 5 种颜色的袜子，为什么摸出 6 只就能保证有一双？如果要保证有 3 只同色，需要摸出几只？

参考答案：前 5 只最坏情况下各是一种颜色，第 6 只必然与其中之一同色，这是 $n=6>m=5$ 的直接应用。若要保证 3 只同色，用定量形式：需要 $\lceil n/5\rceil\ge3$，即 $n/5>2$，最小整数 $n=11$。检验：最坏情况是每种颜色各取 2 只，共 $10$ 只仍可能没有 3 只同色；第 11 只必然使某种颜色达到 3 只。

2. 证明定量鸽巢原理：$n$ 只鸽子、$m$ 个笼子，必有某笼至少 $\lceil n/m\rceil$ 只鸽子。

参考答案：反设每个笼子至多 $\lceil n/m\rceil-1$ 只。因为 $\lceil n/m\rceil-1<n/m$，所以每个笼子的鸽子数都严格小于 $n/m$。设第 $h$ 个笼子有 $N_h$ 只，则

$$n=\sum_{h=1}^{m}N_h<\sum_{h=1}^{m}\frac{n}{m}=n,$$

得到 $n<n$，矛盾。故结论成立。（这里用到 $N_h$ 是整数，所以 $N_h\le\lceil n/m\rceil-1$ 等价于 $N_h<n/m$ 的整数化。）

3. 在「聚会上两人认识同样多的人」的证明里，为什么不能直接把度数 $0,\dots,n-1$ 当作 $n$ 个笼子就用鸽巢原理？

参考答案：因为鸽子数也是 $n$（$n$ 个人），鸽巢原理要求鸽子数严格大于笼子数，$n>n$ 不成立，用不上。必须把笼子减少到 $n-1$ 个。关键观察是度数 $0$ 与 $n-1$ 不可能同时出现：若某人认识其余所有人（度数 $n-1$），就没有人是谁都不认识的（度数 $0$）。于是分两种情形——存在度数 $n-1$ 时，度数只能取 $1,\dots,n-1$ 共 $n-1$ 个值；不存在度数 $n-1$ 时，度数只能取 $0,\dots,n-2$ 共 $n-1$ 个值。两种情形下都是 $n$ 只鸽子进 $n-1$ 个笼子，结论成立。

4. 子集和问题中，鸽巢原理给出的两个同和子集 $A,B$ 为什么可能相交？相交时如何处理，处理之后为什么仍然非空？

参考答案：鸽巢原理只保证「两个不同的非空子集落在同一个和上」，并未附加「不交」的条件，所以 $A\cap B$ 可能非空。处理办法是令 $I=A\setminus B$、$J=B\setminus A$，把公共元素从两边同时删掉。由于两个和相等，减去同一个量 $\sum_{k\in A\cap B}x_k$ 后仍然相等；而 $I\cap J=\varnothing$ 由构造直接得到。非空性：若 $I=\varnothing$，则 $A\subseteq B$，且 $\sum_{j\in J}x_j=0$；所有 $x_j>0$，正数之和为零只能是 $J=\varnothing$，于是 $A=B$，与 $A\ne B$ 矛盾。所以 $I\ne\varnothing$，同理 $J\ne\varnothing$。

5. Erdős–Szekeres 定理的证明中，为什么必须用有序对 $(I_s,D_s)$，只用 $I_s$ 不行吗？

参考答案：只用 $I_s$ 不够。若两个位置有相同的 $I_s$，并不能推出矛盾——它们只是「以各自结尾的最长递增子序列等长」，完全可能合法共存。真正需要的是让每个位置携带足够的信息，使得任意两个不同位置必然至少有一个坐标不同。引理证明的正是这件事：对 $s>t$，若 $a_s>a_t$ 则 $I_s>I_t$，若 $a_s<a_t$ 则 $D_s>D_t$。两种情况下有序对都不同。于是 $nm+1$ 个位置必须占据 $nm+1$ 个不同的有序对；但若定理不成立，$I_s\le n$、$D_s\le m$，只有 $nm$ 个有序对可用，矛盾。有序对的第二个坐标正是补上「递减」这一半信息的关键。

6. 家谱问题中，$2^{40}>10^{12}$ 推出的结论到底是什么？为什么它能说明「父母是血亲」？

参考答案：$2^{40}$ 是向上追溯 $40$ 代时祖先位置的数目——每一位祖先是一个角色，例如「母亲的父亲的母亲」。历史上活过的人至多 $10^{12}$ 个，而位置多于人，由鸽巢原理，必有同一个真人占据两个不同的位置。同一个人出现在两条不同的祖先路径上，意味着这两条路径在这一点汇合：这个人的两条后代线后来结合，因而存在某位祖先，其父母在血缘上相关。需要注意，鸽巢原理直接给出的是「某人在祖先树中重复出现」，最后一层「因此父母是血亲」依赖祖先树的树状结构，属于直观推断而非纯计数结论。

与前后课的关系

这一讲建立了全课的第一个工具，也定下了写证明的基调：先声明方法、给记号起有意义的名字、把读者的理解路径设计进证明里。

接下来两讲转向概率：先讲条件概率与独立性，再用容斥原理处理「至少一个事件发生」的计数。计数与概率会在此后反复出现——生成函数、尾界、编码理论、线性规划，几乎每一个主题都要回到「数一数有多少种可能」这个动作上。

A problem everyone faces each morning

Your drawer holds socks in five colours. It is still dark, and you want a matching pair. How many socks must you pull out to guarantee a pair, no matter how unlucky you are?

The answer is $6$. The worst case is five socks, one of each colour; whatever the sixth is, it matches one already in your hand.

The reasoning works because there are only $5$ colours and you took $6$ socks. The course names this after pigeons and holes: put $n$ pigeons into $m$ holes; if $n>m$, some hole contains at least two pigeons.

The principle sounds trivially obvious, yet its power comes from seeing the problem from a different angle. The difficulty is never the principle — it is deciding what counts as a pigeon and what counts as a hole. The lecture trains exactly that skill with five examples of increasing difficulty.

Timeline

Where this course is going

The aim is not only to teach mathematics but to teach how to write a proof clearly. The course compares a good proof to good code: modular, with the complicated part extracted into a lemma, and with the overall blueprint visible before the details.

This lecture demonstrates three habits while proving things:

1. Announce the method up front (for instance "we argue by contradiction"), so the reader is never lost until the final line.
2. Choose notation with meaning ($I$ in $I_s$ stands for increasing).
3. Distinguish steps that are mathematically necessary from steps that merely help the reader understand.

The precise statement

Pigeonhole principle (basic form). Let $n$ pigeons be placed in $m$ holes. If $n>m$, then some hole contains at least two pigeons.

Pigeonhole principle (quantitative form). If $n$ pigeons are placed in $m$ holes, then some hole contains at least $\lceil n/m\rceil$ pigeons.

Proof of the quantitative form

Suppose the claim fails: every hole contains at most $\lceil n/m\rceil-1$ pigeons. Let $N_h$ be the number in hole $h$. Since $\lceil n/m\rceil-1<n/m$,

$$N_h\le \left\lceil \frac{n}{m}\right\rceil-1<\frac{n}{m}$$

for every $h$. Summing over all holes,

$$n=\sum_{h=1}^{m}N_h<\sum_{h=1}^{m}\frac{n}{m}=n .$$

This gives $n<n$, a contradiction. Hence some hole holds at least $\lceil n/m\rceil$ pigeons. $\square$

Only one idea is at work: count the same pigeons two ways — once hole by hole, once by knowing the total is $n$. This double-counting pattern returns throughout the course.

The lecture treats the write-up itself as teaching material: state the method first, then name the contradiction explicitly at the end. None of this affects correctness, but all of it affects whether a reader can follow.

Application 1: two people who know equally many others

Claim. At a party with $n\ge 2$ people (yourself included), there are always two people who know the same number of other people.

This looks nothing like a pigeonhole problem. Translating it into graph theory fixes that.

Model: people are vertices, acquaintance is an edge

Draw each person as a vertex, and connect two vertices when those people know each other. The result is a simple graph with $n$ vertices.

The degree of a vertex is the number of edges meeting it — here, the number of people that person knows. The claim becomes: every simple graph with $n\ge2$ vertices has two vertices of equal degree.

First attempt: why it falls just short

Use vertices as pigeons and degrees as holes. Each degree lies in $\{0,1,\dots,n-1\}$, giving $n$ possible values, while there are $n$ vertices. Pigeons and holes are equal in number, and the principle requires strictly more pigeons than holes.

The key observation: degrees $0$ and $n-1$ cannot coexist

• If someone knows everybody else, that person has degree $n-1$; then nobody knows no one, so degree $0$ does not occur.
• If nobody has degree $n-1$, all degrees lie in $\{0,1,\dots,n-2\}$, only $n-1$ possible values.

Now split into cases.

Case 1: a vertex of degree $n-1$ exists. Then degree $0$ is absent, leaving $n-1$ holes. With $n$ pigeons and $n-1$ holes, two vertices share a degree by the pigeonhole principle.

Case 2: no vertex of degree $n-1$ exists. All degrees lie in $\{0,\dots,n-2\}$, again $n-1$ holes, and the same conclusion follows.

The two cases exhaust all possibilities, so the claim holds. $\square$

The lesson: pigeons and holes do not come for free. One must first find the right abstraction (a graph), then correct the count of holes. The lecture deliberately keeps the failed first attempt, because real proofs are found this way.

Application 2: equal-sum subsets among twenty four-digit numbers

Claim. Given any $20$ strictly positive four-digit integers $x_1,\dots,x_{20}$, there exist two disjoint nonempty subsets with equal sums.

Three sentences to state, yet the proof needs care. First translate the English into mathematics: find $I,J\subseteq\{1,\dots,20\}$ with

$$I\ne\varnothing,\qquad J\ne\varnothing,\qquad I\cap J=\varnothing,\qquad \sum_{i\in I}x_i=\sum_{j\in J}x_j .$$

Choosing pigeons and holes

• Pigeons: nonempty subsets. There are $2^{20}-1$ of them.
• Holes: possible sums. The largest possible sum is less than $20\times 10^4=2\times 10^5$, and every sum is a nonnegative integer, so there are fewer than $2\times10^5$ holes.

Why $2^{20}-1$? Each element has two fates — chosen or not — corresponding to a $20$-bit string. There are $2^{20}$ strings; discard the empty subset and $2^{20}-1$ remain. This "subset ↔ bit string" correspondence is the simplest bijection, to be developed formally when counting begins.

Numerically, $2^{20}-1=1\,048\,575>200\,000$. Pigeons greatly outnumber holes, so two distinct nonempty subsets $A\ne B$ have equal sums.

The catch: $A$ and $B$ may intersect

The principle only guarantees "two different subsets with the same sum"; it says nothing about disjointness. If both $A$ and $B$ contain $x_1$, the conclusion is not yet what was promised.

Fix it by removing the common part from both: set

$$I=A\setminus B,\qquad J=B\setminus A .$$

These are disjoint by construction. Because

$$\sum_{i\in A}x_i=\sum_{j\in B}x_j,$$

subtracting the shared contribution $\sum_{k\in A\cap B}x_k$ from both sides gives

$$\sum_{i\in I}x_i=\sum_{j\in J}x_j .$$

So $I$ and $J$ still have equal sums.

Why $I$ and $J$ are nonempty

Suppose $I=\varnothing$. Then $A\subseteq B$ and

$$0=\sum_{i\in I}x_i=\sum_{j\in J}x_j .$$

A sum of positive numbers is zero only when nothing is summed, so $J=\varnothing$. Then $A\subseteq B$ and $B\subseteq A$, hence $A=B$, contradicting $A\ne B$. Therefore $I\ne\varnothing$; the same argument gives $J\ne\varnothing$. $\square$

Existence is not construction

The result has a striking feature: it guarantees that equal-sum subsets exist without saying how to find them. Searching $2^{20}$ subsets for a colliding pair is exponential. The lecture notes that subsets of countries with literally equal populations exist in real data, yet no fast algorithm is known; the problem is connected to cryptography.

In the language of the lecture: proving that something exists is far easier than constructing it.

Application 3: every permutation has a long monotone subsequence

Theorem (Erdős–Szekeres). In any permutation of $nm+1$ distinct real numbers, there is either an increasing subsequence of length $n+1$ or a decreasing subsequence of length $m+1$.

Definitions first:

• A permutation is an arrangement of $1,2,\dots,nm+1$ in any order.
• A subsequence selects terms in their original relative order; the chosen positions need not be adjacent.

Take $n=m=3$ and the permutation

$$3,\ 2,\ 1,\ 6,\ 5,\ 4,\ 9,\ 8,\ 7,\ 10 .$$

The increasing subsequence $3,6,9,10$ has length $4=n+1$, exactly what the theorem promises. The example is also tight: the longest decreasing subsequence has length only $3$ (for instance $3,2,1$), short of $m+1=4$.

Proof: two labels per position

This is the delicate construction of the lecture. For the $s$-th position of the sequence define

• $I_s$: the length of the longest increasing subsequence ending at position $s$;
• $D_s$: the length of the longest decreasing subsequence ending at position $s$.

The phrase "ending at position $s$" matters: it assigns each position a unique pair $(I_s,D_s)$ of progress markers.

Lemma. If $s\ne t$, then $(I_s,D_s)\ne(I_t,D_t)$.

Proof. Assume without loss of generality that $s>t$. Write $a_s$ and $a_t$ for the corresponding terms. Since all terms are distinct, exactly one of two cases holds.

• If $a_s>a_t$: take the increasing subsequence of length $I_t$ ending at $t$ and append $a_s$. Because $s>t$ (so $a_s$ comes later) and $a_s>a_t$, the result is still increasing, of length $I_t+1$. Hence $I_s\ge I_t+1>I_t$.
• If $a_s<a_t$: similarly, take the decreasing subsequence of length $D_t$ ending at $t$ and append $a_s$, obtaining a decreasing subsequence of length $D_t+1$. Hence $D_s\ge D_t+1>D_t$.

In either case the two ordered pairs differ in at least one coordinate, so $(I_s,D_s)\ne(I_t,D_t)$. $\square$

Finish: count the holes

Argue by contradiction. Suppose the theorem is false: there is no increasing subsequence of length $n+1$ and no decreasing subsequence of length $m+1$. Then for every position $s$,

$$1\le I_s\le n,\qquad 1\le D_s\le m .$$

The pair $(I_s,D_s)$ therefore takes at most $n\cdot m$ values — those are the $nm$ holes. But the sequence has $nm+1$ positions, that is, $nm+1$ pigeons. By the pigeonhole principle, two distinct positions $s\ne t$ land in the same hole:

$$(I_s,D_s)=(I_t,D_t),$$

contradicting the lemma. Hence the theorem holds. $\square$

Where the construction comes from

The lecture admits that inventing this definition on the spot in an exam would be extraordinary. Its origin is dynamic programming: to learn the length of the longest increasing subsequence ending here, combine answers to earlier subproblems. Once the ending element is fixed, two pieces of information — length, and whether the run is increasing — suffice to decide whether the next term can extend it.

This explains the elegance: the proof compresses "the length of a subsequence", which seems to require remembering the whole sequence, into a single pair of numbers.

A playful application: every family tree contains a close-relative marriage

Claim. Every person's ancestry contains someone whose parents are blood relatives.

The proof uses four biological assumptions that are hard to dispute:

1. Every person has two biological parents.
2. Nobody has children after age $100$.
3. The human species is at least $4{,}000$ years old.
4. At most $10^{12}$ humans have ever lived.

Model: ancestor slots are vertices

Trace upward from yourself: two parents, four grandparents, eight great-grandparents, and so on. Generation $k$ has $2^k$ slots. A slot is a role, not a person — "mother's father" and "father's mother" are different slots that may happen to be filled by the same individual.

By assumptions 2 and 3, the ancestry extends back at least

$$\frac{4000}{100}=40$$

generations. Hence there are at least

$$2^{40}=1\,099\,511\,627\,776>10^{12}$$

ancestor slots. But at most $10^{12}$ humans have ever lived. Slots outnumber people by roughly ten percent, so by the pigeonhole principle at least two distinct ancestor slots are occupied by the same person.

One person appearing in two distinct slots means the ancestry tree "merges": two different upward paths meet at the same individual. That means the two lines of descent from that person eventually came together, so some ancestor had parents who were blood relatives. $\square$

Strictly speaking, the last step needs a small argument: if two paths merge at someone, two distinct descendants of that person later produced a child together, making their shared ancestry the source of consanguinity. The lecture gives this as the intuitive conclusion; the point is to display the power of translating biological facts into counting.

The formalism of probability: groundwork for the next lectures

The lecture closes with the basic framework, preparing for conditional probability.

Sample space

The sample space $\Omega$ is the set of all possible outcomes. Rolling an ordinary die gives $\Omega=\{1,2,3,4,5,6\}$.

The sample space may be infinite. For "flip a coin until the first head appears", the number of flips can be any positive integer, so $\Omega=\{1,2,3,\dots\}$.

Probability

Assign a real number $p(x)$ to each outcome $x\in\Omega$, subject to two axioms:

$$p(x)\ge 0\quad\text{for all }x\in\Omega, \qquad \sum_{x\in\Omega}p(x)=1 .$$

A fair die takes $p(x)=1/6$. Infinite sample spaces satisfy the axioms too: for example

$$p(k)=2^{-k}\quad(k=1,2,3,\dots), \qquad \sum_{k=1}^{\infty}2^{-k}=1,$$

which is exactly the distribution of "the first head appears on flip $k$".

Events and complements

An event is a subset $E\subseteq\Omega$, with probability equal to the sum of the probabilities of its outcomes:

$$P(E)=\sum_{x\in E}p(x).$$

Rolling an even number corresponds to $E=\{2,4,6\}$, with probability $1/2$.

The complement $\overline{E}$ (also written $\neg E$) consists of everything in $\Omega$ outside $E$. Since $E$ and $\overline{E}$ are disjoint and together cover $\Omega$,

$$P(E)+P(\overline{E})=\sum_{x\in\Omega}p(x)=1,$$

so

$$P(\overline{E})=1-P(E).$$

This simple identity will be used constantly: when the event itself is hard to count, count its complement.

What this lecture establishes

• Pigeonhole principle: $n$ pigeons in $m$ holes with $n>m$ force a repeat; the quantitative form gives $\lceil n/m\rceil$.
• The proof is double counting: summing by hole must agree with the known total.
• The work is always in choosing pigeons and holes:
  • Party problem: vertices are pigeons, degrees are holes, and "$0$ and $n-1$ are exclusive" removes one hole.
  • Subset sums: nonempty subsets are pigeons, attainable sums are holes; intersections are deleted.
  • Longest subsequences: positions are pigeons, pairs $(I_s,D_s)$ are holes.
  • Family trees: ancestor slots are pigeons, the historical population is the hole.
• An existence proof is not a construction: equal-sum subsets exist, but finding them quickly is hard.
• Probability rests on three objects: a sample space, the probability axioms, and events with complements.

Comprehension check

1. With socks in 5 colours, why do 6 socks guarantee a pair? How many are needed to guarantee three socks of one colour?

Reference answer: In the worst case the first 5 socks are one of each colour, so the 6th must match one of them — a direct application with $n=6>m=5$. For three of one colour use the quantitative form: we need $\lceil n/5\rceil\ge3$, i.e. $n/5>2$, so the least integer is $n=11$. Check: two socks of each colour give $10$ socks with no colour reaching three; the 11th forces some colour to three.

2. Prove the quantitative pigeonhole principle: $n$ pigeons in $m$ holes force some hole to hold at least $\lceil n/m\rceil$ pigeons.

Reference answer: Suppose every hole holds at most $\lceil n/m\rceil-1$. Since $\lceil n/m\rceil-1<n/m$, every hole holds strictly fewer than $n/m$ pigeons. With $N_h$ pigeons in hole $h$,

$$n=\sum_{h=1}^{m}N_h<\sum_{h=1}^{m}\frac{n}{m}=n,$$

so $n<n$, a contradiction. (The step uses integrality: $N_h\le\lceil n/m\rceil-1$ is the integer version of $N_h<n/m$.)

3. In the party problem, why can we not simply use the $n$ possible degrees $0,\dots,n-1$ as holes?

Reference answer: Because there are also $n$ pigeons, and the principle needs strictly more pigeons than holes; $n>n$ fails. The number of holes must be reduced to $n-1$. The key observation is that degrees $0$ and $n-1$ cannot both occur: if someone knows everybody (degree $n-1$), nobody knows no one (degree $0$). Case 1: a vertex of degree $n-1$ exists, so degrees range over $1,\dots,n-1$ — only $n-1$ values. Case 2: no vertex of degree $n-1$, so degrees range over $0,\dots,n-2$ — again $n-1$ values. Either way, $n$ pigeons enter $n-1$ holes.

4. Why may the two equal-sum subsets $A,B$ produced by the pigeonhole principle intersect, and why does deleting the intersection preserve both disjointness and nonemptiness?

Reference answer: The principle only guarantees two distinct nonempty subsets with the same sum; it imposes no disjointness. Set $I=A\setminus B$ and $J=B\setminus A$. Since the two sums are equal, subtracting the shared amount $\sum_{k\in A\cap B}x_k$ from both leaves them equal, and $I\cap J=\varnothing$ by construction. For nonemptiness: if $I=\varnothing$ then $A\subseteq B$ and $\sum_{j\in J}x_j=0$; a sum of positive terms is zero only if $J=\varnothing$, giving $A=B$ and contradicting $A\ne B$. Hence $I\ne\varnothing$, and symmetrically $J\ne\varnothing$.

5. In the Erdős–Szekeres proof, why must the pair $(I_s,D_s)$ be used? Would $I_s$ alone not suffice?

Reference answer: No. Two positions with equal $I_s$ can coexist perfectly legally — they merely have equally long increasing subsequences ending there, which is no contradiction. What is needed is a label rich enough that any two distinct positions must differ in at least one coordinate. The lemma proves exactly that: for $s>t$, if $a_s>a_t$ then $I_s>I_t$, and if $a_s<a_t$ then $D_s>D_t$; either way the pairs differ. Then $nm+1$ positions must occupy $nm+1$ distinct pairs, whereas if the theorem failed we would have $I_s\le n$ and $D_s\le m$, only $nm$ pairs. The second coordinate supplies the missing "decreasing" half of the information.

6. In the family-tree argument, what exactly does $2^{40}>10^{12}$ establish, and how does it imply that someone's parents were blood relatives?

Reference answer: $2^{40}$ counts ancestor slots forty generations back — each slot is a role such as "mother's father's mother". At most $10^{12}$ humans have ever lived, and slots outnumber people, so by the pigeonhole principle one real person occupies two distinct slots. A person appearing on two different upward paths means the paths merge: two distinct descendant lines from that person later produced a child together, so some ancestor had parents who were related by blood. Note that the principle directly yields "someone repeats in the ancestor tree"; the final step to "the parents were blood relatives" uses the tree structure and is an intuitive inference beyond pure counting.

Relation to neighbouring lectures

This lecture supplies the course's first tool and sets the tone for proof writing: announce the method, choose meaningful notation, and design the reader's path through the argument.

The next two lectures turn to probability — first conditional probability and independence, then inclusion–exclusion for counting when at least one event occurs. Counting and probability recur everywhere afterwards: generating functions, tail bounds, coding theory and linear programming all return to the same act of counting how many possibilities exist.