鸽笼原理讲课版ppt课件.pptx

《鸽笼原理讲课版ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章鸽笼原理回顾前一章——计数：本章重点介绍简单形式和加强形式的鸽笼原理及其在排列组合中的（存在性）应用‘介绍鸽巢原理的推广：Ramsey定理例子、意义鸽笼原理及其推广Ramsey(瑞姆赛)定理Ramsey数排列组合组合恒等式1§2.1鸽笼原理定理§2.1鸽笼原理4=4+0+0=3+1+0=2+2+0=2+1+12§2.1鸽笼原理定理§2.1鸽笼原理定理2.1鸽笼原理（抽屉原理）若把n+1个物体放到n（n≥1）个盒子中去，则至少有一个盒子放有至少2个物体。证明：用反证法证明。如果n个盒子中每个盒子至多放入一个物体，则放入n个盒子中的物体总数至多为n个。这与假设有n+1个物体矛盾。从而定理得证

2、。注：鸽笼原理只指出了至少存在这样的盒子，并没有给出“确定哪一个盒子有此性质的方法”，因此，它只能用来解决存在性问题。实际应用中，如何构造“鸽子”和“鸽笼”是困难所在。3§2.1鸽笼原理例1、2、3§2.1鸽笼原理例题例1a、一年有365天，今有366个人，则其中至少有两个人生日相同。证明：此例中把“天”当作盒子，相当于365个盒子放入366个物体。得证。例1b、抽屉里有10双相同的手套，从中取11只出来，其中至少有两只是完整配对的。证明：此例中把“每双手套”当作盒子，相当于10个盒子放11个物体。得证。例1c、一个教师每周上8次课，则这教师至少有一天要上至少2次课。证明：此例中把“天”当作盒

3、子，相当于7个盒子放8个物体，从而得证。4§2.1鸽笼原理例9§2.1鸽笼原理例题课本p7例2、证明：把5个顶点放到边长为2的正方形中，至少存在两个顶点，它们之间的距离小于或等于。证明：把边长为2的正方形分成四个全等的边长为1的小正方形，则每个小正方形的对角线长为。如果把每个小正方形当作一个盒子，由鸽笼原理知，把5个顶点放到4个盒子中，必有一个盒子中放入了两个顶点。即必有一个小正方形中有2个顶点；而小正方形的对角线长为，也就是说小正方形中任意两点的最大距离为。这就证明了本题。5§2.1鸽笼原理例7证明：构造一个序列则此时有两种可能：（1）若这m个和中有一个sh(1≤h≤m)是m的倍数，则结论成

4、立。（2）若这m个和中没有一个是m的倍数，则这些和被m除时必有1,2,…,m-1这样的余数。由于有m个和，且只有m-1个余数，于是我们可以构造m-1个盒子，第i个“盒子”是被m除余数为i的数，(i=1,2,…,m-1)。由鸽笼原理知，用m除各和时，至少有两个和的余数是相同的。则存在整数k和l(k＜l)，使得sk和sl被m除有相同的余数，即sk≡slmodm。故§2.1鸽笼原理例题课本p7例3、设a1a2…am是正整数的序列，则至少存在整数k和l，1≤k＜l≤m，使得和ak+1+ak+2+…+al是m的倍数。（m≥2）6§2.1鸽笼原理例7§2.1鸽笼原理例题课本p7例4、一个棋手有11周时间准

5、备锦标赛，他决定每天至少下一盘棋，7天内下棋的次数不能多于12次，证明：在此期间的连续一些天中他正好下棋21次。证明：令分别为这11周期间每天下棋的次数，并做部分和：根据题意，有ai都是正整数，故而且故根据假设有做序列序列（S）共154项，分别为从1到153的整数。根据鸽笼原理，其中必有两项相等。7§2.1鸽笼原理例8§2.1鸽笼原理证明：但序列是严格单调递增的，所以这77项是互不相等的；从而序列这77项也是互不相等的。有鸽笼原理的结论可知：一定存在，使得因此，这说明从第i+1天到第j天这连续j-i天中，他刚好下了21盘棋。证毕8§2.1鸽笼原理例6证明：设所取n+1个数是a1,a2,…,an

6、,an+1，对该序列中的每一个数去掉一切2的因子，直至剩下一个奇数为止，即ri=ai/2x，x=0,1,2,…。结果得由奇数组成的序列R：r1,r2,…,rn,rn+1。1到2n中只有n个奇数，故序列R中至少有两个数是相同的。设为，对应的有，则ai是aj的倍数。§2.1鸽笼原理例题例5、从1到2n的正整数中任取n+1个，则这n+1个数中至少有一对数，其中一个数是另一个数的倍数（n≥1）。课本P8的例5例5、从1,2,…,200中任意选出101个数，必有两个数其中一个能够整除另一个。9例题例6(中国余数定理)、设m和n是互素的正整数，即它们的最大公约数是1，0am-1，0bn-1，则必存

7、在正整数x，使得m除x余a，n除x余b。证明：考虑n个数a,m+a,…,(n1)m+a，这n个数除以m的余数都等于a。若其中两个数im+a和jm+a被n除余数相同，则n

8、(ij)m。根据已知(m,n)=1,得到n

9、(ij)，这与0<

10、ij

11、