第一部分：鸽巢原理

~~咕咕咕！！！~~

然鹅大家还是最熟悉我→

a数组：but 我也很重要

$：我好像也出现不少次

以上纯属灌水

文章简叙：鸽巢原理对初赛时的问题求解以及复赛的数论题目都有启发意义。直接的初赛考察一般在提高组出现。相当于抽屉。

别名：鸽笼原理。狄利克雷抽屉原理。

最简单的一种形式：有 $m + 1$ 只鸽子， $m$ 个笼子，那么至少有一个笼子有至少两只鸽子。当然，换个角度来说：有 $m - 1$ 只鸽子， $m$ 个笼子，那么至少有一个笼子是空的。

初级加强：有 $m$ 个笼子， $k * m + 1$ 只鸽子，那么至少有一个笼子有至少 $k + 1$ 只鸽子。

高级加强：令

$a_{1}, a_{2}, a_{3} . . . a_{m}$

为正整数。

$i f$ 我们将

$a_{1} + a_{2} + a_{3} + . . . + a_{n} - n + 1$

个鸽子放入 $n$ 个笼子里， $t h e n$ ，

||第一个笼子至少有 $a_{1}$ 只鸽子||第二个笼子至少有 $a_{2}$ 只鸽子||第三个笼子至少有 $a_{3}$ 只鸽子||…||第 $m$ 个笼子至少有 $a_{m}$ 只鸽子

鸽巢原理的应用

一位洛谷 $o i e r$ 要用 $12$ 周的时间准备 $<mtext> </mtext> C T S C <mtext> </mtext>$ ,为了练习，他每天至少要刷一题，因为题目有难度，他每星期刷题无法超过 $13$ 题。请你证明：存在连续的若干天期间，这位 $o i e r$ 恰好刷了 $11$ 题

开始证明：

1.我们可以令 $a_{1}$ 表示第一天所刷的题数， $a_{2}$ 表示前两天所刷的题数， $a_{3}$ 表示前三天所刷的题数.之后以此类推

2.而题目说，由于每天都要至少刷1题，所以数列

$a_{1}, a_{2}, a_{3}, a_{4}, . . ., a_{84}$

严格递增。另有 $a_{1} > = 1$ .又每周最多刷13题，故 $a_{84} < = 13 * 12 = 156$ .

3.因此又有：

$1 < = a_{1} < a_{2} < a_{3} < . . . < a_{84} < = 156$ .

4.同理，

$a_{1} + 11, a_{2} + 11, a_{3} + 11, . . ., a_{84} + 11$

同样是一个严格递增序列。范围：

$12 < = a_{1} + 11 < a_{2} + 11 < a_{3} + 11 < . . . < a_{84} + 11 < = 167$

5.我们把两个序列合起来看：

$a_{1}, a_{2}, a_{3}, . . ., a_{84}, a_{1} + 11, a_{2} + 11, a_{3} + 11, . . ., a_{84} + 11$

一共 $168$ 个数。其中每一个数都是 $1$ 到 $167$ 之间的一个整数。

6.根据鸽巢原理可得，其中必有两个数相等！！！

7.既然

$a_{1}, a_{2}, a_{3}, . . ., a_{84}$

中必然无相等的两个数，

那么 $a_{1} + 11, a_{2} + 11, a_{3} + 11, . . ., a_{84} + 11$

中同理。那么，必然存在一个 $x$ 和一个 $y$ ,使得

$a_{x} = a_{y} + 11$ ;

8.从而得出结论：这个 $o i e r$ 在第

$y + 1, y + 2, y + 3, . . ., x$

天内一共刷了 $11$ 道题

应用二

证明：在边长为 $2$ 的等边三角形中放上 $5$ 个点。则至少存在两个点，他们之间的距离小于等于 $1$ .

1.我们先画出一个边长为 $2$ 的等边三角形。

2.然后把三条边中点两两相连。就形成了这张图。

3.那么根据鸽巢原理，必然有两个点在一个边长为 $1$ 的小三角形里。

4.而我们知道，边长为 $1$ 的等边三角形里处处距离都小于等于 $1$

5.于是问题就解决了

应用三

已知 $n + 1$ 个正整数，它们全都小于或等于 $2 n$ ，证明当中一定有两个数是互质的。

1.要证明这个问题，我们就要利用一个互质的特性：两个相邻整数互质。

2.有了这个突破口，于是我们可以构造n个鸽巢，每一个里依次放入

$1, 2, 3, . . ., 2 n$

这2n个数中的两个数。

3.也就是说，我们要在这其中取出 $n + 1$ 个数。

4.根据鸽巢原理，无论如何，我们都会抽空一个鸽巢。

5.一个鸽巢中的两个数肯定互质，所以问题就解决了。

扒栗史：匈牙利大数学家厄杜斯(PaulErdous,1913 - 1996) 向当年年仅 $11$ 岁的波萨(LouisPósa)提出这个问题，而小波萨思考了不足半分钟便能给出正确的答案。

有趣的小（leng）知（xiao）识（hua）：
山东高考 $2017$ 年有 $54$ 万人。而人的头发大约有 $8 - 12$ 万根。那么必然有两人的头发数量相同。

好了，现在来一道初赛真题收（dian）心(di):

【NOIP2010 提高组】记 $T$ 为一队列，初始时为空，现有n个总和不超过 $32$ 的正整数依次入队，如果无论这些数具体为什么值，都能找到一种出队的方式，使得存在某个时刻队列 $T$ 中的数之和恰好为 $9$ ，那么 $n$ 的最小值是_______________

1.第一眼看到此题，蒟蒻就知道自己只能~~根据结果推过程~~了

2.刚开始看了一眼答案： $18$ .

3.于是就根据这个开始推导过程。我们可以令 $a_{i}$ 表示前 $i$ 个数的和，并约定： $a_{0} = 0$ .

4.题目要求求出最小的 $n$ ，使得存在 $0 < = x < y < = n$ 满足 $a_{y} = a_{x} + 9$ ;

5.于是我们可将 $a$ 数组看做鸽子，用不能同时取的一组（差为 $9$ ）的集合构造笼子，

6.构造方法如下：一共有 $n = 18$ 个集合按此方式选取：

$0, 9 、 1, 10 、 2, 11 、 . . . 、 8, 17 、 18, 27 、 19, 28 、 20, 29 、 . . . 、 23, 32 、 24 、 25 、 26$ 。

7.由题意可知，我们一旦在某个集合中取了两个元素， $t h e n$ 一定存在某个时刻队列 $T$ 中数的总和恰好为 $9$ .

8.于是由鸽巢原理，我们可以得知： $n = 18$ 一定满足条件.

但是题目要让我们求出最小值，为了保险起见（都看答案了还保什么险）：

1.我们还要证明一下 $n = 17$ 不可行。

2.然鹅我们只需要举出反例即可：

1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1

3.说明：因为每到了 $8$ 个 $1$ 就被 $10$ 隔断，故不可行。

第二部分：Ramsey定理

扒栗史：此定理由Frank Plumpton Ramsey（弗兰克·普伦普顿·拉姆齐， $1903 - 1930$ ）提出.

此定理有一个广为流传的例子：6 个人中至少存在3人相互认识或者相互不认识。

转换：该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形

证明如下：

1、首先，把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。

2、设：如果两个人认识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色。

3、由鸽巢原理可知：这五条线段中至少有三条是同色的。不妨设AB、AC、AD为红色。若BC或CD为红色，则结论显然成立。若BC和CD均为蓝色，则若BD为红色，则一定有三个人相互认识；若BD为蓝色，则一定有三个人互相不认识。

以下部分正在补充，本文未完成

鸽巢原理及其扩展——Ramsey定理

第一部分：鸽巢原理

鸽巢原理的应用

应用二

应用三

第二部分：Ramsey定理

后记：部分内容来自于一本通