第十章鸽笼原理.ppt

;10.1鸽笼原理的简单形式;定理10.2：s(s≥1)个元素分成t个组，那么必存在一个组至少含有?s/t?(这里??为“上整数”记号)个元素。

证明：用反证法证明。

若每个组至多含有(?s/t?-1)个元素，则t个组最多有元素t*(?s/t?-1)，

因为s/t≤?s/t?(s/t)+1，

所以有t*(?s/t?-1)t*((s/t)+1)-1)s，

导致矛盾。故必存在一个组至少含有?s/t?个元素。

任意13个人中，至少有二人生日在同一个月;

任意70个人中，至少有?s/t?=?70/12?=6人生日同月;;例：在n+1个小于或等于2n的互不相等的正整数中，必存在两个互质的数。

证明：s=n+1,关键是如何构造鸽笼。

注意到这样的事实：任何相邻两数互质。

因此可以考虑把1,2,…,2n这2n个数分成n个组:{{1,2},{3,4},…,{2n-1,2n}}，

例：在1,2,…,2n中任取n+1个互不相同的数中，必存在两个数，其中一个数是另一个数的倍数。

证明：因为任何正整数n都可表示成n=2a·b(这里a=0,1,2,…，且b为奇数)。

设取出的n+1个数为k1,k2,…,kn+1，则ki=2aibi，;设a1,a2,…,an为整数，则存在k和l(0?kl?n),使得ak+1+ak+2+…+al被n整除。

证明:构造Si=a1+a2+…+ai,

则有S1,S2,…,Sn,

余数有n个,但为0则表示被n整除,因此考虑分开讨论;例：一个国际象棋选手为参加国际比赛，突击练习77天，要求每天至少下一盘棋，每周至多下12盘棋。证明:无论如何安排总可使他在这77天里有连续几天共下了21盘棋。

证明：用ai表示从第1天到第i天下棋的总盘数(i=1,2,…,77)。

由于规定每天至少下一盘棋，且每周至多下12盘棋，故有：1≤a1a2…a77≤12×(77/7)=132

现构造一个新的序列:a1+21a2+21…a77+21。

现有这样的序列:

a1,…,a77,a1+21,…,a77+21，

如果要求证明无论如何安排总可使他在这77天里有连续几天共下了22盘棋,怎样做?;10.2鸽笼原理的加强形式;推论10.1:若将n(r-1)+1个元素分成n个组，则至少有一个组中含有r个或者更多的元素(这里n、r皆为正整数)。

推论10.2:若n个正整数m1,m2,…,mn的平均数满足不等式:

(m1+m2+…+mn)/nr-1，则m1,m2,…,mn中至少有一个不小于r。;例10.5：两个同心圆盘的每个圆周均分为200段，从大盘上任选100段涂上红色，其余涂上蓝色，而在小盘的每个小段上任意涂上红色??蓝色。证明在旋转小盘时可以找到某个位置，使得小盘上至少有100个小段与大盘上对应段颜色相同。

证明：固定大盘，对小盘上任一段，每转一格，因大盘不动，就与大盘某段组成一种颜色，旋转一周200格，就与大盘上的所有段构成200种颜色组合，其中同色的有100组。

小盘上共有200段，故小盘上的所有段在旋转一周后，与大盘对应段构成的同色组共有20000个。

设转i格的同色组为mi(这里i=1,2,…,200)，;例10.6：设a1,a2,…,an2+1，是n2+1个不同实数的序列，则必可从此序列中选出n+1个数的子序列，使这子序列为递增序列或递减序列。

证明:若存在长度为n+1的递增序列，结论成立。

若不存在长度为n+1的递增序列，目标证明存在长度为n+1的递减序列。

首先要找到一个长度为n+1的子序列，然后证明是递减序列;作业:

P2211,3,4,5,7

课件地址：

54

集合与图论;谢谢大家！