《鸽笼原理讲课版ppt课件.pptx》由会员分享，可在线阅读，更多相关《鸽笼原理讲课版ppt课件.pptx（10页珍藏版）》请在三一办公上搜索。
1、第2章 鸽笼原理,回顾前一章计数： 本章重点介绍简单形式和加强形式的鸽笼原理及其在排列组合中的（存在性）应用介绍鸽巢原理的推广：Ramsey 定理 例子、意义 鸽笼原理及其推广 Ramsey (瑞姆赛)定理 Ramsey数,排列组合组合恒等式,1,2.1 鸽笼原理定理,2.1 鸽笼原理,4 = 4+0+0 = 3+1+0 = 2+2+0 = 2+1+1,2,2.1 鸽笼原理定理,2.1 鸽笼原理,定理 2.1,鸽笼原理（抽屉原理）若把n+1个物体放到n （n1）个盒子中去，则至少有一个盒子放有至少2个物体。,证明：用反证法证明。 如果n个盒子中每个盒子至多放入一个物体，则放入n个盒子中的物体总
2、数至多为n个。这与假设有n+1个物体矛盾。从而定理得证。注：鸽笼原理只指出了至少存在这样的盒子，并没有给出“确定哪一个盒子有此性质的方法”，因此，它只能用来解决存在性问题。实际应用中，如何构造“鸽子”和“鸽笼”是困难所在。,3,2.1 鸽笼原理例1、2、3,2.1 鸽笼原理,例 题,例1a、一年有365天，今有366个人，则其中至少有两个人生日相同。,证明：此例中把“天”当作盒子，相当于365个盒子放入366个物体。得证。,例1b、抽屉里有10双相同的手套，从中取11只出来，其中至少有两只是完整配对的。,证明：此例中把“每双手套”当作盒子，相当于10个盒子放11个物体。得证。,例1c、一个教师
3、每周上8次课，则这教师至少有一天要上至少2次课。,证明：此例中把“天”当作盒子，相当于7个盒子放8个物体，从而得证。,4,2.1 鸽笼原理例9,2.1 鸽笼原理,例 题课本p7,例2、证明：把5个顶点放到边长为2的正方形中，至少存在两个顶点，它们之间的距离小于或等于 。,证明：把边长为2的正方形分成四个全等的边长为1的小正方形，则每个小正方形的对角线长为 。如果把每个小正方形当作一个盒子，由鸽笼原理知，把5个顶点放到4个盒子中，必有一个盒子中放入了两个顶点。即必有一个小正方形中有2个顶点；而小正方形的对角线长为 ，也就是说小正方形中任意两点的最大距离为 。这就证明了本题。,5,2.1 鸽笼原理
4、例7,证明：构造一个序列则此时有两种可能：（1）若这m个和中有一个sh(1hm)是m 的倍数，则结论成立。（2）若这m个和中没有一个 是m 的倍数，则这些和被m除时必有1,2,m-1这样的余数。由于有m个和，且只有m-1个余数，于是我们可以构造m-1个盒子，第i个“盒子”是被m除余数为i的数，(i=1,2,m-1)。由鸽笼原理知，用m除各和时，至少有两个和的余数是相同的。则存在整数k和l (kl) ，使得sk和sl 被m除有相同的余数，即 sksl mod m 。故,2.1 鸽笼原理,例 题课本p7,例3、设a1a2am是正整数的序列，则至少存在整数k和l，1klm，使得和ak+1+ak+2+
5、al是m的倍数。 （m2）,6,2.1 鸽笼原理例7,2.1 鸽笼原理,例 题课本p7,例4、一个棋手有11周时间准备锦标赛，他决定每天至少下一盘棋，7天内下棋的次数不能多于12次，证明：在此期间的连续一些天 中他正好下棋21次。,证明：令 分别为这11周期间每天下棋的次数，并做部分和：根据题意，有ai都是正整数，故而且故根据假设有 做序列序列（S）共154项，分别为从1到153的整数。根据鸽笼原理，其中必有两项相等。,7,2.1 鸽笼原理例8,2.1 鸽笼原理,证明：但序列 是严格单调递增的，所以这77项是互不相等的；从而序列 这77项也是互不相等的。有鸽笼原理的结论可知：一定存在 ，使得因
6、此，这说明从第i+1天到第j天这连续j-i天中，他刚好下了21盘棋。证毕,8,2.1 鸽笼原理例6,证明：设所取n+1个数是a1,a2,an,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个数中至少有一对数，其中一个数是另一个数的倍数（n1） 。,课本P8的例5,例5、从 1, 2, , 20
7、0 中任意选出 101 个数，必有两个数其中一个能够整除另一个。,9,例 题,例6(中国余数定理)、设 m 和 n 是互素的正整数，即它们的最大公约数是 1，0 a m-1 ，0 b n-1，则必存在正整数 x ，使得m 除 x 余 a，n 除 x 余 b。,证明：考虑 n 个数 a, m + a, , (n 1)m + a，这n 个数 除以m的余数都等于a 。若其中两个数 im + a 和 jm + a 被 n 除余数相同，则 n | (i j)m 。根据已知(m, n)=1, 得到n | (i j)，这与0 | i j | n矛盾，所以a, m + a, , (n 1)m + a 被 n 除余数各不相同，其中有 mk + a 被 n 除余 b，取 x = mk + a 。,2.1 鸽笼原理例4、5,2.1 鸽笼原理,从以上几个例子可以看出，尽管鸽笼原理很简单，但是它确能解决一些看似很复杂的问题，应用过程中的关键是：如何构造具体问题中的鸽子和鸽笼？,10,
