组合数学第三章2学习资料

鸽笼原理的一般形式设qi为正整数(i=1,2,…,n)，

，如把q个物体放入n个盒子中，则至少存在一个i，使得第i个盒子中至少有qi个物体。§3.2鸽笼原理一般形式§3.2鸽笼原理的一般形式定理3.2证明：用反证法证明。假设结论不成立，即对每一个i，第i个盒子至多放有ni个物体，，从而这n个盒子放入物体的总数为这与

矛盾。从而定理得证。§3.2鸽笼原理的推论1§3.2鸽笼原理的一般形式三个推论推论3.2.1：若把m个物体放到n个盒子中去，则至少有一个盒子放有不少于

(m-1)/n

+1个物体。

证明：用反证法证明。假设结论不成立，即对每个盒子中至多放有

(m-1)/n

个物体，从而这n个盒子放入物体的总数最多为n×(m-1)/n

≤m-1这与假设矛盾。§3.2鸽笼原理的推论2§3.2鸽笼原理的一般形式三个推论推论3.2.1：若把m个物体放到n个盒子中去，则至少有一个盒子放有不少于

(m-1)/n

+1个物体。

推论3.2.2：若把n(r-1)+1个物体放到n个盒子中去，则至少有一个盒子放有不少于r个物体。

证明：这是定理2.2当q1=q2=…=qn=r时的特殊情况。 §3.2鸽笼原理的推论3§3.2鸽笼原理的一般形式三个推论推论3.2.3：若mi为正整数(i=1,2,…,n),

，则至少存在一个i，使得mi≥r。推论3.2.1：若把m个物体放到n个盒子中去，则至少有一个盒子放有不少于

(m-1)/n

+1个物体。

推论3.2.2：若把n(r-1)+1个物体放到n个盒子中去，则至少有一个盒子放有不少于r个物体。

证明：用反证法证明。假设结论不成立，即对每个i，mi≤r-1，则这与假设矛盾。§3.2鸽笼原理推广例1-1例题§3.2鸽笼原理的一般形式例1、设A=a1a2…a20时有10个0和10个1组成的某一20位2进制数，B=b1b2…b20是任意的20位2进制数，先把A、B分别计入图（A）、（B）两个20个格子，分别得（A）、（B）两种图像，并把两个B联接的40位的2进制数C=b1b2…b20

b1b2…b20，它的图像为（C）。则存在某个i，1≤i≤20，使得cici+1…ci+19与a1a2…a20至少有10位对应相等。...ABC第i

格第i+19格12…192012…1920

12…

19201…1920...............§3.2鸽笼原理推广例1-2例题§3.2鸽笼原理的一般形式证明：在C=c1c2…c40中，当i遍历1,2,…,20时，每一个bj,j=1,2,…,20，历遍

a1,a2,…,a20。因A中有10个0和10个1，每一个bj都有10位次对应相等，从而当

i历遍1,2,…,20时，共有10×20=200位次对应相等。故对每个

i平均有200/20=10位相等，因而对某个i至少有10位对应相等。...ABC第i

格第i+19格12…192012…1920

12…

19201…1920...............§3.2鸽笼原理推广例2例题§3.2鸽笼原理的一般形式例2、将两个大小不一的圆盘分别分成200个相等的扇形。在大圆盘上任取100个扇形染成红色，另外的100个扇形染成蓝色，并将小圆盘上的扇形任意染成红色或蓝色，然后将小圆盘放在大圆盘上且中心重合时，转动小圆盘可使其每一扇形都叠放于大圆盘的某一扇形内。证明：当适当转动小圆盘可使叠放的扇形对中，同色者至少100对。证明：设使大小两盘中心重合，固定大盘，转动小盘，则有200个不同的位置使小盘上的每个小扇形含在大盘上的小扇形中，（将这200种可能的位置看作200个不同的盒子）。由于大盘上的200个小扇形中有100个染成红色，100个染成蓝色，所以小盘上的每个小扇形在转动过程中，无论染成红色或蓝色，在200个可能的重合位置上恰好有100次与大盘上的小扇形同色（将同色的扇形看作放入盒子的物体）。因而小盘上的200个小扇形在200个重合位置上共同色100

200=20000次。而20000＞200(100-1)+1，由推论2.2.2知，存在着某个位置，使同色的小扇形数大于等于100个。§3.2鸽笼原理推广例3例题§3.2鸽笼原理的一般形式例3、将[1,67]划分为４个子集，必有一个子集中有一数是同子集中的两数之差（或和）。证明：设从1到67的整数任意分成4部分p1,p2,p3,p4，作如下分析：①由鸽笼原理知，1到67的整数中必有一部分，不妨设为p1,至少有

(67-1)/4+1=17个元素。并设这17个元素为a1＜a2＜…＜a17，若ai中存在一个元素是某两个元素之差，则命题得证。否则，令b1=a2-a1,b2=a3-a1,…,b16=a17-a1，显然1≤bi＜67，故bi不属于p1，属于p2,p3或p4。②同理，bi中至少有

(17-1)/3+1=6个元素属于p2，设这6个元素为c1＜c2＜…＜c6，若ci中存在一个元素是某两个元素之差，则命题得证。否则，令d1=c2-c1,d2=c3-c1,…,d5=c6-c1，显然1≤di＜67，且存在1≤l,m≤17,di=ci-c1=al-am,i=1,2,…,5，故di不属于p1,p2，属于p3,p4。③di中至少有

(6-1)/2+1=3个元素属于p3，设这3个元素为f1＜f2＜f3，若fi中存在一个元素是某两个元素之差，则命题得证。否则，令g1=f2-f1,g2=f3-f1，显然1≤gi＜67，且存在1≤l,m≤17,gi=fi-f1=al-am,i=1,2

，故fi不属于p1,p2,p3，属于p4。④若g1=g2-g1，则命题得证。否则，令h=g2-g1，显然1≤h＜67，且同上可以证明h不属于p1,p2,p3,p4中任一个，与已知矛盾。§3.2鸽笼原理推广例4例题§3.2鸽笼原理的一般形式例4、证明：在每个包含n2+1个不同的实数的序列中，存在一个长度为n+1的递增子序列，或者存在一个长度为n+1的递减子序列。（一个序列的长度是指该序列的元素个数）。证明：设 是一个实数序列，并假设在这个序列中没有长度为n+1的递增子序列，则要证明一定有一个长度为n+1的递减子序列。令表示以为首项的最长递增子序列的长度 则对每个k

，由假设知道这相当于把个物品放入个盒子中，由推论2.2.2知，必有一个盒子里面至少有个物品，即存在及 ，使得对应于这些下标的实数序列必满足它们构成一长为的递减子序列。否则，若有某个使得 ，那么以 为首项的最长递增子序列加上 ，就得到一个以为首项的递增子序列，由定义知，这与 矛盾。因此， 成立。

这是一个长度为n+1的递减子序列，故结论成立。§3.2鸽笼原理推广例5例题§3.2鸽笼原理的一般形式例5、将1,2,…,10随机地摆成一圆，则必有某相邻三数之和至少是17。证明：设 表示该圆上相邻三个数之和（i居中）。这样的和共有10个。而1,2,…,10中的每一个都出现在这十个和的三个之中，故由推论2.2.3知，存在一个i

，使。§3.3Ramsey定理3§2.3Ramsey定理定理3.36个人中一定有3个人相互认识或相互不认识。证明：先考虑6个人中的任意一个人，不妨把这个人称作p。则其他的5个人可以分为下面的两个集合F和S。其中F=与p相识的人的集合，S=与p不相识的人的集合由鸽笼原理知，这两个集合中至少有一个集合包含有3个人。若F包含有3个人，则这3个人或者彼此不相识，或者有两个人彼此相识。如果F中有3个人彼此不相识，则结论成立。如果F中有2人相识，则由于这两个人都与p相识，因此有3人彼此相识，故定理结论成立。类似的，如果S包含3个人，则这3个人或者彼此相识，或者有两个人彼此不相识。如果这3个人彼此相识，则结论成立。如果有两个人彼此不相识，则由于这两个人都与p也不相识，因此有3个人彼此不相识，故定理结论成立。§3.3Ramsey定理4§3.3Ramsey定理定理3.410人中一定有4人相互认识或有3人相互不认识。

证明：在这10个人中任意挑选一个人，不妨把这个人称作p。则其他的9个人可以分为下面的两个集合F和S。其中F=与p相识的人的集合，S=与p不相识的人的集合如果S中有4个（或4个以上）人，则或者这4个人（或4个人以上）或者彼此认识，或者有两个人彼此不认识。如果有4个人彼此认识，则结论成立。如果在S中有2人彼此不认识，则由于这两个人都与p不认识，因此有3人彼此不认识，故定理结论成立。如果S中最多有3个人，则由鸽笼原理知，F中至少有6个人。由定理2.3知，F中一定有3人相互认识或有3人相互不认识。如果有3个人彼此不认识，则定理成立。如果有3个人彼此认识，则把p加入，就有4个彼此认识的人，故定理得证。§3.3Ramsey定理5§3.3Ramsey定理定理3.410人中一定有4人相互认识或有3人相互不认识。定理3.510人中一定有3人相互认识或有4人相互不认识。证明：在定理3.4中，如果把“不认识”换成“认识”，“认识”换成“不认识”，则有定理3.5，该定理的证明类似于定理3.4。§3.3Ramsey定理6§3.3Ramsey定理定理3.620个人中一定有4个人相互认识或相互不认识。证明：在这20个人中任意挑选一个人，不妨把这个人称作p。则其他的19个人可以分为下面的两个集合F和S。其中F=与p相识的人的集合，S=与p不相识的人的集合由鸽笼原理知，这两个集合中至少有一个包含（至少）10个人。如果F中有10个（或10个以上）人，则或者这10个人（或10个人以上）有3个人相互认识