趣味数学抽屉原理

趣味数学讲座,?晏子春秋?里有一个“二桃杀三士的故事，大意是： 齐景公养着三名勇士，他们名叫田开疆、公孙接和古冶子。 这三名勇士都力大无比，武功超群，为齐景公立下过不少功绩。但他们也刚愎自用，目中无人，得罪了齐国的宰相晏婴。晏子便劝齐景公杀掉他们，并献上一计：以齐景公的名义赏赐三名勇士两个桃子，让他们自己评功，按功绩的大小吃桃。,三名勇士都认为自己的功绩很大，应该单独吃一个桃子。于是公孙接讲了自己的打虎功，拿了一只桃；田开疆讲了自己的杀敌功，拿起了另一桃。两人正准备要吃桃子古冶子说出了自己更大的功绩。,公孙接、田开疆都觉得自己的功绩确实不如古冶子大，感到羞愧难当，赶忙让出桃子。并且觉得自己功绩不如人家，却抢着要吃桃子，实在丢人，是好汉就没有脸再活下去，于是都拔剑自刎了。古冶子见了，懊悔不迭。仰天长叹道：如果放弃桃子而隐瞒功绩，那么有失勇士尊严；为了维护自己而羞辱同伴，又有损哥们义气。如今两个伙伴都为此而死了，我单独活着，算什么勇士！说罢，也拔剑自杀了。,晏子采用借“桃杀人的方法，不费吹灰之力，便到达了他预定的目的，可说是善于运用权谋。汉朝有人在一首诗中曾不无挖苦地写道：“一朝被谗言，二桃杀三士。谁能为此谋，相国务晏子！,在晏子的权谋之中，包含了一个重要的,数学原理,抽屉原理,。,抽屉原理,把n+1个物体放到n个抽屉中，那么至,少有一个抽屉里有不止一个这种物体。,什么叫做抽屉原理？,“ 抽屉原理又称“鸽笼原理，最先是由19世纪的德国数学家狄里克雷提出来的，所以又称“狄里克雷原理。,狄里克雷德国数学家。对数论、数学分析和数学物理有突出奉献，是解析数论的创始人之一。1805年2月13日生于迪伦，1859年5月5日卒于格丁根。中学时曾受教于物理学家G.S.欧姆；18221826年在巴黎求学，深受J.-B.-J.傅里叶的影响 。回国后先后在布雷斯劳大学、柏林军事学院和柏林大学任教27年，对德国数学开展产生巨大影响。1839年任柏林大学教授，1855年接任C.F.高斯在格丁根大学的教授职位。,狄利克雷原那么是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。,形式一：,设把n1个元素分为n个集合A,1,，A,2,，A,n,，用a,1,，a,2,，a,n,表示这n个集合里相应的元素个数，证明至少存在某个a,i,大于或等于2.,形式二： 设把nm1个元素分为n个集合A,1,，A,2,，A,n,，用a,1,，a,2,，a,n,表示这n个集合里相应的元素个数，证明至少存在某个a,i,大于或等于m1。,1947年，匈牙利数学家把这一原理引进到中学生数学竞赛中，当年匈牙利全国数学竞赛有一道这样的试题：“证明：任何六个人中，一定可以找到三个互相认识的人，或者三个互不认识的人。,如果B、C、D三人互不认识，那么我们就找到了三个互不认识的人；如果B、C、D三人中有两个互相认识，例如B与C认识，那么，A、B、C就是三个互相认识的人。不管哪种情况，此题的结论都是成立的。,用A、B、C、D、E、F代表六个人，从中随便找一个，例如A吧，把其余五个人放到“与A认识和“与A不认识两个“抽屉里去，根据抽屉原理，至少有一个抽屉里有三个人。不妨假定在“与A认识的抽屉里有三个人，他们是B、C、D。,幼儿园买来不,少熊、马、狗塑料,玩具，每个小朋友,任意选择两件，那,么至少要有几个小,朋友才能保证有两,人选的玩具相同？,6种可能出现的选择方式,就是6个“抽屉”,“苹果”是小朋友,把135块饼干分,给16个小朋友，如,果每个小朋友至少,要分到1块饼干，那,么不管怎样分，一,定会有2个小朋友得,到的饼干数目相,同。为什么？,要使16个小朋友个到的饼干数各不相同至,少需要1+2+3+,+15+16=,这与只有,135,块饼干矛盾.所以一定有2个小朋友得到的饼干数目相同.,练习：,六甲班共有学,生42人，从学校图,书室借来212本书，,是否有人能至少借,到6本或6本以上的,图书？,假设无人借6本或6本以上的图书，那么全班至多借书542=210本.但全班共借来212本，所以要么至少有两人借6本，要么至少有1人借7本.,练习,1.有黑色、白色、黄色的筷子各8根，混杂在一起，黑暗中想从这些筷子中取出颜色不同的两双筷子，问至少要取多少根才能保证到达要求？,最多取出8根只有一种颜色的筷子，再取任意3根即可保证到达要求。所以至少要取11根.,练习：,2.在1只箱子里面放着红、黑、白三种颜色的手套各6副，如想闭着眼睛从中取出两副颜色不同的手套，问至少要取出多少只才能到达要求？,1212,125,至少取出15只手套才能到达要求.,3. 在2323的方格纸中，将19这9个数字填入每个小方格中，并对所有形如“十字的图形中的5个数字和，对于小方格中的数字的任意一种填法，其中和数相等的“十字图形至少有多少个？,练习：,在2323的方格纸中共有2121=441个“十字图形，,“十字图形中5个数字的和最小为5，最大为45，共有45-4=41种不同的和.,由441=4110+30可知，和数相等的“十字图形至少有11个.,4. 400人中至少有两个人的生日相同.,练习：,分析：生日从1月1日排到12月31日，共有366个不相同的生日，我们把366个不同的生日看作366个抽屉，400人视为400个苹果，由表现形式1可知，至少有两人在同一个抽屉里，所以这400人中有两人的生日相同.,解：将一年中的366天视为366个抽屉，400个人看作400个苹果，由抽屉原理的表现形式1可以得知：至少有两人的生日相同.,5. 任取5个整数，必然能够从中选出三个，使它们的和能够被3整除.,练习：,证明：任意给一个整数，它被3除，余数可能为0，1，2，我们把被3除余数为0，1，2的整数各归入类r,，r,1,，r,2,.至少有一类包含所给个数中的至少两个.因此可能出现两种情况：,.某一类至少包含三个数；,.某两类各含两个数，第三类包含一个数.,假设是第一种情况，就在至少包含三个数的那一类中任取三数，其和一定能被3整除；,假设是第二种情况，在三类中各取一个数，其和也能被3整除.综上所述，原命题正确.,6. 某校派出学生204人上山植树15301株，其中最少一人植树50株，最多一人植树100株，那么至少有5人植树的株数相同.,练习：,证明：按植树的多少，从50到100株可以构造51个抽屉，那么个问题就转化为至少有5人植树的株数在同一个抽屉里.,(用反证法)假设无人或人以上植树的株数在同一个抽屉里，那只有人以下植树的株数在同一个抽屉里，而参加植树的人数为204人，所以，每个抽屉最多有4人，故植树的总株数最多有：,4(505199100),4,15300,15301,得出矛盾.,所以，至少有5人植树的株数相同.,形式一：,设把n1个元素分为n个集合A,1,，A,2,，A,n,，用a,1,，a,2,，a,n,表示这n个集合里相应的元素个数，证明至少存在某个a,i,大于或等于2.,形式二： 设把nm1个元素分为n个集合A,1,，A,2,，A,n,，用a,1,，a,2,，a,n,表示这n个集合里相应的元素个数，证明至少存在某个a,i,大于或等于m1。,抽屉原理的两种常见形式:,抽屉原理不仅在数学中有用，在现实生活中也到处在起作用，如招生录取、就业安排、资源分配、职称评定等等，都不难看到抽屉原理的作用。,谢谢,