现在工程数学第二天课件鸽笼原理

1、Contact UsCollage of Software Beihang University: softqm鸽笼原理例子、意义鸽笼原理及其推广Ramsey定理Ramsey数Contact UsCollage of Software Beihang University: softqm12存放4个物体3453个盒子Contact UsCollage of Software Beihang University: softqm2.1 鸽笼原理定理2.1鸽笼原理若把n+1个物体放到n （n1）个盒子中去，则至少有一个盒子放有至少2个物体。Contact UsCollage of Software

2、 Beihang University: softqm鸽子笼子应用原理：设法构造出“鸽子”与“笼子”Contact UsCollage of Software Beihang University: softqm笼子例1鸽子13个人中，至少有两个人生日在同一。笼子鸽子366个人中，至少有两个人生日在同一个天。笼子鸽子例2用10种颜色给11件物品涂色，至少有两件物品有相同的颜色。Contact UsCollage of Software Beihang University: softqm例3设有n对夫妇，从这2n个人中至少选出多少人，才能保证有一对夫妇被选出？答：至少选择n+1人。Contac

3、t UsCollage of Software Beihang University: softqm649个号码球(1到49),摇出6个,另摇出第7个作为特别号8Contact UsCollage of Software Beihang University: softqm例4：每次的正选号码中至少有两个第一位数字一样 (假设1=01, 2=02, 3=03, 4=04).9Contact UsCollage of Software Beihang University: softqmDateDraw NumberDraw Results20/12/200202/110+17/12/20020

4、2/109+12/12/200202/108+10/12/200202/107+05/12/200202/106+03/12/200202/105+28/11/200202/104+26/11/200202/103+21/11/200202/102+19/11/200202/101+每次要摇出6个正选号码;而对每个号码,第一位的选择有0,1,2,3,4 共5种;由鸽笼原理有6个鸽子到5个鸽笼中,至少有一个鸽笼中有两个鸽子,即至少有两个号码有相同的第一位.10Contact UsCollage of Software Beihang University: softqm例5：从1至200中选出1

5、01个整数。证明：其中一个可以被另一个整除。两个整数，证明：整数 n = 2 k a , a是1至199中的奇数选出的101个数中，至少两个数有(共100 个）。相同 a .m = 2r a ,n = 2 s a设则m 可以整除 n, 或n可以整除 m .Contact UsCollage of Software Beihang University: softqm例6、从1到2n的正整数中n+1个，则这n+1个数中至少有一对数，其中一个数是另一个数的倍数（n1）。 证明：设所取n+1个数是a1,a2,an,an+1，对该序列中的每一个数去掉一切2的因子，直至剩下一个奇 数为止，即 ri =

6、ai / 2x ，x = 0,1,2,。结果得由奇数组成的序列R：r1,r2,rn,rn+1。1到2n中只有n个奇数，故序列R中至少有两个数是相同的。ri = rj = r, i j设为，= 2ai r，a= 2a j r，不妨设a ，a对应的有 aijij则ai是aj的倍数。Contact UsCollage of Software Beihang University: softqm例7、设a1a2am是正整数的序列，则至少整数 k 和 l ， 0k lm ，使得和 ak+1+ak+2+al是m的倍数。 （m2）s1 = a1 , s2 = a1 + a2 , ., sm = a1 + a

7、2 + . + am。s1 s2 . sm证明：构造一个序列则此时有两种可能：（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 。sl - sk= ak +1 + ak +2+ . + al 0mod mContact UsCollage of Sof

8、tware Beihang University: softqm例8、设a1a2a100是由1和2组成的序列， 已知从其中任意一个数开始的顺序10个数的和不超过16，即对于1i91恒有ai+ai+1+ai+916。则至少h1，使得ah+ah+1+ak=39 。h和k，kContact UsCollage of Software Beihang University: softqms1 = a1 , s2 = a1 + a2 , ., s100 = a1 + a2 + . + a100。证明：作序列s1 s2 . s100由于每个ai都是正的整数，故= (a1 + a2 + . + a10 )

9、+ (a11 + a12 + . + a20 )s100而且+ . + (a91 + a92 + . + a100 )。 10 16 = 160s100故根据假设有s1 , s2 , ., s100 , s1 + 39, s2 + 39,., s100 + 39（S）做序列14444444244444443共200项最后的项 s100 + 39 160 + 39 = 199但序列（S）共200项，为从1到199的整数。根据鸽笼原理，其中必有两项相等。但序列（S）中前100项为单调增，后100为单调增，故= sh + 39， 1 h k 100h和k，使sk则即或sk - sh = 39(a1

10、+ a2 + . + ak ) - (a1 + a2 + . + ah ) = 39ah+1 + ah+2+ . + ak = 39Contact UsCollage of Software Beihang University: softqm通过前面几道例题可以看出，应用鸽笼原理可以巧妙的解决看似复杂的，其关键是如何去构造中的“鸽子”和“鸽笼”Contact UsCollage of Software Beihang University: softqm例9、证明：把5个顶点放到边长为2的正方形中，至少两个顶点，它们之间的距离小于或等于 2 。证明：把边长为2的正方形分成四个全等的边长为1的

11、小正方形，2则每个小正方形的对角线长为。如果把每个小正方形当作一个盒子，由鸽笼原理知，把5个顶点 放到4个盒子中，必有一个盒子中放入了两个顶点。即必有一个小正方形中有2个顶点；而小正方形的对角线长为2 ，也就是说小正方形中任意两点的最大距离为2 。这就证明了本题。Contact UsCollage of Software Beihang University: softqm 例10：一位国际象棋大师有11周的时间备战一场锦标赛，他决定每天至少下一，但是为了使不过分疲劳他还决定连续若干天，期间这位大在每周不能下棋超过12盘。证明师恰好下了21。Contact UsCollage of Softw

12、are Beihang University: softqm一共备战117=77天。令x1,x2,x77分别为第1,2,77天下的棋 数，则xi1(i=1,2,77)。我们构造如下严格递增序列：a1=x1, a2=x1+x2, a3=x1+x2+x3,a77=x1+x2+x3+x77，其中，ai表示前i (i=1,2,77)天下棋的总数，并且1a1a2a3,a771112=132 。则序列a1+21, a2+21,a3+21,a77+21 也是一个严格递增序列，并且22a1+21a2+21a3+21,a77+21 153 。于是，这154个数：a1,a2,a77,a1+21,a2+21,a77

13、+21中的每一个都是1到153中的一个整数。如果这个序列中的每个元素作为鸽子，1到153中的每个数作为笼子，根据鸽笼原理，在这154中必有两个元素相等，既然a1,a2,a77中没有相等的元素，a1+21,a2+21,a77+21中也没有相等的元素，则必然j(1i,j 77)使得aj=ai+21，从而这位国际象棋大师在第一个i和i+1,i+2,j天总共下了21。Contact UsCollage of Software Beihang University: softqm2.2鸽笼原理的一般形式定理 2.2+-(1证明：反证法Contact UssoftqmUniversityof Softwa

14、re BeihangeCollag:设q , 1q, 2 L ,n 是q个n 正整数。若将q )1 -(+ q21+) Lq-n(+ 1q) =1q1 2 +Lq+nn+1个物体放入 n个盒子，则k , 使得某一盒子内至少放有qk 个物体。推论2.2.1：若把m个物体放到n个盒子中去， 则至少有一个盒子放有不少于(m-1)/n+1个物体。推论2.2.2(特例)：若把n(r-1)+1个物体放到n 个盒子中去，则至少有一个盒子放有不少于 r个物体。Contact UsCollage of Software Beihang University: softqm推论2.2.3（平均原理）Contact

15、 UsCollage of Software Beihang University: softqm设m ,L , m 是非负整数 ,若 m 1 + L + mn r + 11nn则至少有一个整数 r - 11nn则至少有一个整数 r 。 例1 (中国剩余定理)：令m和n是两个互素的整数，并令a和b为两个整数，且0am-1以及0bn-1 。于是一个整数x，使得x除以m的为a，并且x除以n的为b，即，x既可以写成x=pm+a的同时又可以写成x=qn+b的形式，在这里，p和q为两个整数。素数定义：如果两个整数m和n的最大公约数为1，我们称m和n 为互素。为了证明这个结论，我们需要构造出x，那么如何构

16、造？我们首先按照x=pm+a的形式构造x(p取0,1,n-1)，考虑如下n 个整数：a, m+a, 2m+a, (n-1)m+a。这些整数中的每个除以m的都为a，即x可以写成pm+a的形式。如果我们能够证明a, m+a, 2m+a, (n-1)m+a这n个数中一个数能够写成qn+b的形式，则即可证明本题结论。Contact UsCollage of Software Beihang University: softqm如果a, m+a, 2m+a, (n-1)m+a中的每个数除以n的这n个数作为物体，n的都不相等，则0,1,2,n-1作为盒子，根据鸽笼原理， 0,1,2,n-1都会出现，特别是

17、数b作为中的每个数作为也会出现。令p为整数，满足0 p n-1，且使数x=pm+a除以n的为b，则对某个适当的q，有x=qn+b，因此，x=pm+a且x=qn+b，从而x具有所要求的性质。否则，如果这n个数两个数除以n有相同的r，我们令这两个数分别为im+a和jm+a，其中，0i20(10-1)+1，因而对某个 i 至少有10位对应相等。命题得证。12.19 201B219 20.A第 i 格第 i +19格.C1219 20 119 20推论2.2.2：若把n(r-1)+1个物体放到n个盒子中 去，则至少有一个盒子放有不少于r个物体。Contact UsCollage of Software

18、 Beihang University: softqm例3、将两个大小不一的圆盘分别分成200个相等的扇形。在大圆盘上任取100个扇形染成红色，另外的100个扇形染成，并将小圆盘上的扇形任意染成红色或，然后将小圆盘放在大圆盘上且中心重合时，转动小圆盘可使其每一扇形都叠放于大圆盘的某一扇形内。证明：当适当转动小圆盘可使叠放的扇形对中，同色者至少100对。证明：设使大小两盘中心重合，固定大盘，转动小盘，则有200个不同 的位置使小盘上的每个小扇形含在大盘上的小扇形中， （将这200种可能的位置看作200个不同的盒子）。由于大盘上的200个小扇形中有100个染成红色，100个染成，所以小盘上的每个小

19、扇形在转动过，无论染成红色或，在200个可能的重合位置上恰好有100次与大盘上的小扇形同色（将同色的扇形看作放入盒子的物体）。因而小盘上的200个小扇形在200个重合位置上共同色100200=20000次。而20000200(100-1)+1，由推论2.2.2知，扇形数大于等于100个。着某个位置，使同色的小推论2.2.2：若把n(r-1)+1个物体放到n个盒子中 去，则至少有一个盒子放有不少于r个物体。Contact UsCollage of Software Beihang University: softqm例4、将1, 67划分为个子集，必有一个子集中有一数是同子集中的两数之差（或和）

20、。证明：设从1到67的整数任意分成4部分p1,p2,p3,p4，作如下分析：由鸽笼原理知， 1到67的整数中必有一部分，不妨设为p1, 至少有(67-1)/4+1=17个元素。并设这17个元素为a1a2a17，若ai中存在一个元素是某两个元差，则命题得证。否则，令b1=a2-a1,b2=a3-a1,b16=a17-a1，显然1bi67，故bi不属于p1，属于p2,p3或p4。同理，bi中至少有(16-1)/3+1=6个元素属于p2，设这6个元素为c1c2c6，若ci中一个元素是某两个元差，则命题得证。否则，令d1=c2-c1,d2=c3-c1,d5=c6-c1，显然1di67，且1l,m17,

21、di=ci+1-c1=al-am, i=1,2,5，故di不属于p1,p2，属于p3,p4。di中至少有(5-1)/2+1=3个元素属于p3，设这3个元素为f1f2f3，若fi中一个元素是某两个元差，则命题得证。否则，令g1=f2-f1, g2=f3-f1，显然1gi67，且1l,m17, gi=fi+1-f1=al-am, i=1,2 ，故gi不属于p1,p2,p3，属于p4。若g1=g2-g1，则命题得证。否则，令h=g2-g1，显然1h67，且同上可以证明h不属于p1,p2,p3, p4中任一个，与已知。推论2.2.1：若把m个物体放到n个盒子中去，则至少有一个盒子放有不少于(m-1)/

22、n+1个物体。Contact UsCollage of Software Beihang University: softqm例5、证明：在每个包含n2+1个不同的实数的序列中， 子序列，或者一个长度为n+1的递增一个长度为n+1的递减子序列。（一个序列的长度是指该序列的元素个数）。推论2.2.2：若把n(r-1)+1个物体放到n个盒子中去，则至少有一个盒子放有不少于r个物体。Contact UsCollage of Software Beihang University: softqma1 , a2 , ., an2 +1证明：设是一个实数序列，并假设在这个序列中没有长度为n+1的递增子序列

23、，则要证明一定有一个长度为n+1的递减子序列。令mk表示以 ak为首项的最长递增子序列的长度(k = 1, 2, ., n2 + 1)(1 k n2 + 1)1 m n则对每个k，由假设知道k这相当于把 n2 + 1个物品放入 n个盒子中，由推论2.2.2知，必有k1 k2 . kn+1一个盒子里面至少有 n + 1个物品，即mk= mk= . = mk= i1 i n及，使得n +112对应于这些下标的实数序列必满足下列等式，否则m值大于iak ak . akn +112j,(1 j n)一长为 n + 1的递减子序列。否则，若有某个它们，那么以 ak为首项的最长递增子序列加上j +1 17

24、 - 110 17。(i = 1, 2, .,10) ，使mi由推论2.2.3知，一个iContact UsCollage of Software Beihang University: softqm例6：一个抽屉里有20件衬衫，其中4件，7件灰色，9件红色.从中随意取出至少多少件，才能保证有4 件是同色的？保证5，6，7，8，9件同色呢？提示：n个鸽笼，kn+1只鸽子，至少有一个鸽笼里面有k+1个鸽子解:1、33110保证4件同色。2、442113保证5件同色。3、452115保证6件同色。4、462117保证7件同色。5、477119保证8件同色。6、478120保证9件同色。Contac

25、t UsCollage of Software Beihang University: softqm2.3 Ramsey定理Frank Plumpton Ramsey（1903-1930）哲学家、数学家、学院会员、校长之子26 岁英年早逝，对学家和三一学院昔日的学者、马学纯理论是一个损失，尽管他的主要在哲学和数理逻辑方面The Decision Analysis Society annually awards the Frank P. Ramsey Medal to recognise substantial contributions to decision theory and its a

26、pplication to important classes of real decision problems.组合数学中定理的一个广泛流传例子。 世界上任意6个人中，总有3个人相互认识，或互相皆不认识(定理2.3)。Collage of Software Beihang University证明：先考虑6个人中的任意一个人，不妨把这个人称作p。则 其他的5个人可以分为下面的两个集合F和S。其中F=与p相识的人的集合，S=与p不相识的人的集合由鸽笼原理知，这两个集合中至少有一个集合包含有3个人。 若F包含有3个人，则这3个人或者彼此不相识，或者有两个人彼此相识。如果F中有3个人彼此不相识，

27、则结论成立。如果F中有2 人相识，则由于这两个人都与p相识，因此有3人彼此相识，故定理结论成立。类似的，如果S包含3个人，则这3个人或者彼此相识，或者有两 个人彼此不相识。如果这3个人彼此相识，则结论成立。如果有 两个人彼此不相识，则由于这两个人都与p也不相识，因此有3 个人彼此不相识，故定理结论成立。Contact UsCollage of Software Beihang University: softqm定理2.4 10人中一定有4人相互认识或有3人相互不认识。证明：在这10个人中任意挑选一个人，不妨把这个人称作p。则 其他的9个人可以分为下面的两个集合F和S。其中F=与p相识的人的集

28、合，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个彼此认识的人，故定理得证。Contact UsCollage of Software Beihang University: softqm定理2.5 2

29、0个人中一定有4个人相互认识或相互不认识。证明：在这20个人中任意挑选一个人，不妨把这个人称作p。则 其他的19个人可以分为下面的两个集合F和S。其中F=与p相识的人的集合，S=与p不相识的人的集合由鸽笼原理知，这两个集合中至少有一个包含（至少）10个人。 如果F中有10个（或10个以上）人，则或者这10个人（或10个人以上）有3个人相互认识，或者有4个人彼此不认识。如果有4个人彼此不认识，则结论成立。如果有3人彼此认识，则由于这3 个人都与p认识，因此有4人彼此认识，故定理结论成立。如果S中有10个（或10个以上）人，则或者这10个人（或10个人 以上）有3个人相互不认识，或者有4个人彼此认

30、识。如果有4个 人彼此认识，则结论成立。如果有3人彼此不认识，则由于这3 个人都与p不认识，因此有4人彼此不认识，故定理结论成立。Contact UsCollage of Software Beihang University: softqm纯三角形：用图形表示这个定理，上述描述为：对平面上的6个点用实线或虚线连结成的完全图中，其中实线表示这一对人互相认识，虚线表示这对人彼此不认识，或者一个实线三角形或者形。一个虚线三角形。这种三角形称之为纯三角类似可推广为纯n角形，或纯红、的n角形。即所有的的n个顶点的完全图。是实线（或虚线、红色、）Contact UsCollage of Software

31、 Beihang University: softqmRamsey数：设a、b为正整数，令R(a,b)是保证a个人彼此认识或b个人彼此不认识的所需最少人数，则称R(a,b)为Ramsey数。R(彼此认识人的参数，彼此不认识人数的参数)Contact UsCollage of Software Beihang University: softqmRamsey数著名数学家G. C. Rota曾说过：如果别人问我们，组合数学中最的东西是什么？那么大多数组合数学家都会说是Ramsey数。R.美国汽车可以自选牌号的数字、字母，美国数学会前任L.Graham，他的私人小汽车的牌号用的就是RAMSEY这6个

32、英文字母。可查到2000篇以上有关Ramsey数研究的。目前只有有限个Ramsey数的值被确定，其他的都还是未知的。43Contact UsCollage of Software Beihang University: softqm 常见的Ramsey数R(m,n)Contact UsCollage of Software Beihang University: softqmRamsey定理说明了对于任意m、n，R(m,n)都是的。虽然Ramsey定理说明了Ramsey数的性，但是对于Ramsey数的求法，目前还没有凡的结论，比如说R(3,10)、R(5,5)，现在还没人知道它们的准确取值。nm2345672234567336925551425661877下表（from Mathworld）给出了目前已知的Ramsey数的部分结果，一部分数目前只有取值范围Contact UsCollage of Software Beihang University: softqmRamsey数的简单性质性质1：R(a,b)=R(b,a)性质2:R(a,2)=aContact UsCollage of Software Beihang University: softqm性质3：若a, b2，则R(a,b)为一有限数，且R(a,b)R(a-1,b)R(a,b-1)+由于R(5,2