组合数学第二章.pptVIP

Chapter2PigeonholePrinciple4periods

Roadmap2.1鸽巢原理的简单形式2.2鸽巢原理的加强形式2.3Ramsey定理hlju.edu

PigeonholePrinciple的简单形式Theorem1.1假设n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体；或n+1个物体用n种颜色涂色，那么至少有两个物体的颜色相同。例1.1 13个人中必有两个人的生日在同一个月中。例1.2 在边长为２的正方形中任取５点，必有两点的距离小于。 证明：如图，将正方形等分为４个小正方形，任取５点，必有２点落在同一个小正方形，从而证毕。hlju.edu

简单形式例1.3 从1—2n中任取n+1个，那么必存在这样两个数，其中一个是另一个的倍数。 证明：任一正整数可写作2k×a的形式，其中 由a的取值可将这2n个数分为n类，故取出的n+1个数中必有两个数为同一类，从而结论成立。例1.4 证明：n个代表参加会议，试证其中至少有2人各自的朋友数相等。 证明：每个人的朋友数只能取0，1，…，n-1。 但假设有人的朋友数为0，即此人和其他人都不认识，那么其他人的最大朋友数不超过n-2。故此时这n个人的朋友数的实际取数只有n-1种可能； 否那么假设无人的朋友数为0，那么这n个人的朋友数的实际取数仍只有n-1种可能〔1，2，…，n-1〕，所以至少有２人的朋友数相等。hlju.edu

简单形式例1.5 给定m个整数a1,a2,…,am，那么存在0≤pq≤m，使得能被m整除。 证明：考虑m个和式，假设其中有一个可被m整除，那么结论成立。否那么每个和式除以m都有一个非零余数，余数在1，2，…，m-1中取值。 由于有m个余数，根据鸽巢原理，必有两个余数相同，即存在p，q，pq，使 二式相减，得， 即可被m整除。hlju.edu

简单形式例1.6 一位象棋大师有11周的时间备战比赛，他决定每天至少下一盘棋，但每周下棋不超过12盘，证明：存在连续假设干天他恰好共下了21盘棋。改为更少的盘数如何？改为22盘如何？ 证明：设为前ｉ天下棋的总盘数。 显然 故， 又， 这154个数在1－153间取值，必有两个相同， 又，， 故存在ｉ，ｊ，使， 即第ｊ＋１，．．．，ｉ天共下了２１盘棋。题中“每周下棋不超过12盘”可减弱为“总共下棋不超过132盘”hlju.edu

由上述证明过程可知，假设将命题结论改为“小于21盘”，显然是成立的。22盘棋的情况：假设有一周下棋盘数缺乏12盘，那么 故这154个数在1和153之间，有假设每周都下满12盘棋，那么该154个数在1和154之间，假设命题不成立，那么这154个数取遍1，2，…,154，即 故第一周只下了7盘棋，矛盾！ 因此，存在连续假设干天，共下了22盘棋。hlju.edu

例1.7在0，1，2，…，10中任取7个数，那么其中必有两个数之和等于10。 证明： 将0-10分为6组，即{0,10}，{1,9}，{2,8}，{3,7}，{4,6}，{5}， 由鸽巢原理，任取的7个数中至少有两个数在同一组，显然其和等于10。hlju.edu

Roadmap2.1鸽巢原理的简单形式2.2鸽巢原理的加强形式2.3Ramsey定理hlju.edu

加强形式Theorem2.1 设q1,q2,…,qn为正整数，假设将q1+q2+...+qn-n+1个物体放入n个盒子，那么或者第一个盒子至少含有q1个物体，或者第二个盒子至少含有q2个物体，……，或者第n个盒子至少含有qn个物体。 证明：反证法。易证。Corollary2.1 假设将n(r-1)+1个物体放入n个盒子，那么必有一个盒子含有r个或更多的物体。 证明：即为Th2.1中q1=q2=…=qn=r的情形。hlju.edu

加强形式Corollary2.2 设q1,q2,…,qn为非负整数，假设 ，那么至少有一个整数大于或等于r。 证明：假设，那么 ，矛盾。假设将条件换为