组合数学复习

鸽巢原理

定理

1. 若有 $n$ 个笼子和 $n+1$ 只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少 $2$ 只鸽子。
2. 一堆实数 $a_1,a_2,\ldots,a_n$ 若他们的平均值大于 $x$，那么至少存在一个 $a_i>x$。

例题

任意 $n+1$ 个整数中，必存在两个不同的数 $a$,$b$，使得 $n\mid a - b$。

1. 任意整数除以 $n$，余数只能是 $0,…,n-1$ 一共 n 种可能，而 $n+1$ 个整数每个数对应一个余数，一定会有两个不同整数的余数相同。
2. 根据模运算的定义 $a \equiv b \pmod{n} \iff n \mid a - b$

给定 $n$ 个整数 $a_1, a_2, \ldots, a_n$，必存在非空连续子串，其和被 $n$ 整除。

1. 提到连续子串所以构造前缀和数组 $S_0 = 0, \quad S_k = a_1 + a_2 + \cdots + a_k \quad (k = 1, \ldots, n)$
2. 根据上一个例子，n+1 个前缀和数组一定存在两个对 $n$ 同余 $\existsi < j, \quad S_i \equiv S_j \pmod{n}$
3. 根据模运算定义 $n \mid S_j - S_i$，即 $n \mid a_{i+1} + a_{i+2} + \cdots + a_j$

每天至少玩1局，每周最多玩12局，坚持11周，则必存在连续若干天，恰好合计玩了21局。

1. 构造前缀和，设 $a_i$=前 $i$ 天的累计总局数，令 $a_0 = 0$，则：$0 = a_0 < a_1 < a_2 < \cdots < a_{77}$，且 $77 \leq a_{77} \leq 11 \times 12 = 132$
2. 我们希望​找到 $a_j - a_i = 21$ 等价于 $a_j = a_i + 21$，所以构造 $B = {a_0+21, a_1+21, \ldots, a_{77}+21} \subseteq [21,153]$
3. 两个集合落在 $[0, 153]$ 一共 154 个数，根据鸽巢原理肯定有两个相等，并且两个集合内部分别递增，所以 $\existsi < j, \quad S_i \equiv S_j \pmod{n}$

在边长为 1 的正方形中任取 5 个点，其中必有两点距离 $\leq \dfrac{\sqrt{2}}{2}$

1. 将正方形等分为 4 个小正方形，每个边长为 $\dfrac{1}{2}$
2. 5个点放入4个小正方形，由鸽巢原理：$\exists \text{ 某个小正方形，包含至少 2 个点}$
3. 每个小正方形的对角线长度为：$d = \sqrt{\left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2} = \sqrt{\frac{1}{2}} = \frac{\sqrt{2}}{2}$

圆圈等分为200格，分内外两圈各100格。内外圈各放100白100黑。证明：存在某种旋转对齐方式，使得内外圈中至少100对位置颜色相同。

1. 我们假设 $\text{黑} = +1, \quad \text{白} = -1$，那么外圈和内圈可以分别表示为 $a_0, \ldots, a_{199}$ 和 $b_0, \ldots, b_{199}$，并且满足 $\sum_{i=0}^{199} a_i = 0, \sum_{i=0}^{199} b_i = 0$。
2. 旋转 $k$ 格时，位置 $i$ 颜色相同 $\iff a_i b_{i+k} = +1$，故需证明：$C_k=\sum_{i=1}^{200}a_i\cdot b_{i+k}\geq0$
3. 根据强抽屉原理：若 k 个元素和大于 n，则至少存在一个元素大于 $\frac{n}{k}$，所以只需证明 $\sum C_k \geq 0$
4. $\sum_{k=1}^{200} C_k = \sum_{k=1}^{200}\sum_{i=1}^{200} a_i b_{i+k} = \sum_{i=1}^{200} a_i \underbrace{\sum_{k=1}^{200} b_{i+k}}{\text{遍历所有 }b_j\text{ 恰好一次}} = \sum{i=1}^{200} a_i \cdot \underbrace{\sum_{j=1}^{200} b_j}_{=0} = 0$

给定一个长度为 $n^2 + 1$ 的数列 $a_1, a_2, \dots, a_{n^2+1}$ 一定存在长度 ≥ $n+1$ 的递增子序列或长度 ≥ $n+1$ 的递减子序列

在一个半径为 1 的圆中任取 7 个点，则其中一定存在两点使得 它们之间的距离不大于 L，问 L 最小可以是多少，并证明。

将圆周等分成6个弧，每段弧长60°（圆心角60°）。 7个点放入6个“抽屉”（弧），由基本鸽巢原理，至少有一个弧含≥2个点。 在60°圆心角的弦上，两点最大距离为弦长： 2 × sin(30°) = 2 × 1/2 = 1。 故一定存在两点距离≤1。为什么L=1是最小的： 若L<1，则考虑6个正六边形顶点（正六边形内接单位圆，边长恰为1），此时所有距离=1>L，不存在距离≤L的点对。但题目是对7个点的强制结论，用L=1已是最优鸽巢界（6个点可达=1，7个点必然突破）。课堂鸽巢加强版直接给出此界。