鸽巢原理及其扩展——Ramsey定理
ShineEternal · · 个人记录
第一部分：鸽巢原理
别名：鸽笼原理。狄利克雷抽屉原理。
最简单的一种形式：有
初级加强：有
高级加强：令
-
a_1,a_2,a_3...a_m
- 为正整数。
-
a_1+a_2+a_3+...+a_n-n+1
- 个鸽子放入
n 个笼子里，then ，
||第一个笼子至少有
鸽巢原理的应用
一位洛谷
开始证明：
1.我们可以令
2.而题目说，由于每天都要至少刷1题，所以数列
-
a_1,a_2,a_3,a_4,...,a_{84}
- 严格递增。另有
a_1>=1 .又每周最多刷13题，故a_{84}<=13*12=156 .
3.因此又有：
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 ,使得
8.从而得出结论：这个
-
y+1,y+2,y+3,...,x
- 天内一共刷了
11 道题
应用二
证明：在边长为
1.我们先画出一个边长为
2.然后把三条边中点两两相连。就形成了这张图。
3.那么根据鸽巢原理，必然有两个点在一个边长为
4.而我们知道，边长为
5.于是问题就解决了
应用三
已知
1.要证明这个问题，我们就要利用一个互质的特性：两个相邻整数互质。
2.有了这个突破口，于是我们可以构造n个鸽巢，每一个里依次放入
-
1,2,3,...,2n
- 这2n个数中的两个数。
3.也就是说，我们要在这其中取出
4.根据鸽巢原理，无论如何，我们都会抽空一个鸽巢。
5.一个鸽巢中的两个数肯定互质，所以问题就解决了。
扒栗史：匈牙利大数学家厄杜斯(PaulErdous,1913 - 1996) 向当年年仅
有趣的小（leng）知（xiao）识（hua）：
山东高考
好了，现在来一道初赛真题收（dian）心(di):
【NOIP2010 提高组】记
1.第一眼看到此题，蒟蒻就知道自己只能根据结果推过程了
2.刚开始看了一眼答案：
3.于是就根据这个开始推导过程。我们可以令
4.题目要求求出最小的
5.于是我们可将
6.构造方法如下：一共有
7.由题意可知，我们一旦在某个集合中取了两个元素，
8.于是由鸽巢原理，我们可以得知：
但是题目要让我们求出最小值，为了保险起见（都看答案了还保什么险）：
1.我们还要证明一下
2.然鹅我们只需要举出反例即可：
- 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1
3.说明：因为每到了
第二部分：Ramsey定理
扒栗史：此定理由Frank Plumpton Ramsey（弗兰克·普伦普顿·拉姆齐，
- 此定理有一个广为流传的例子：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为蓝色，则一定有三个人互相不认识。
以下部分正在补充，本文未完成