趣味数学抽屉原理.pptx

趣味数学讲座,晏子春秋,里有一个“二桃杀三士”的故事，大意是：齐景公养着三名勇士，他们名叫田开疆、公孙接和古冶子。这三名勇士都力大无比，武功超群，为齐景公立下过不少功劳。但他们也刚愎自用，目中无人，得罪了齐国的宰相晏婴。晏子便劝齐景公杀掉他们，并献上一计：以齐景公的名义赏赐三名勇士两个桃子，让他们自己评功，按功劳的大小吃桃。,三名勇士都认为自己的功劳很大，应该单独吃一个桃子。于是公孙接讲了自己的打虎功，拿了一只桃；田开疆讲了自己的杀敌功，拿起了另一桃。两人正准备要吃桃子古冶子说出了自己更大的功劳。,公孙接、田开疆都觉得自己的功劳确实不如古冶子大，感到羞愧难当，赶忙让出桃子。并且觉得自己功劳不如人家，却抢着要吃桃子，实在丢人，是好汉就没有脸再活下去，于是都拔剑自刎了。古冶子见了，后悔不迭。仰天长叹道：如果放弃桃子而隐瞒功劳，则有失勇士尊严；为了维护自己而羞辱同伴，又有损哥们义气。如今两个伙伴都为此而死了，我独自活着，算什么勇士！说罢，也拔剑自杀了。,晏子采用借“桃”杀人的办法，不费吹灰之力，便达到了他预定的目的，可说是善于运用权谋。汉朝有人在一首诗中曾不无讽刺地写道：“,一朝被谗言，二桃杀三士。谁能为此谋，相国务晏子！”,在晏子的权谋之中，包含了一个重要的,数学原理,抽屉原理,。,抽屉原理,把,n+1,个物体放到,n,个抽屉中，那么至,少有一个抽屉里有不止一个这种物体。,什么叫做抽屉原理？,东西多，抽屉少，那,么至少有两个东西放,在一个抽屉里。,如：,有,6,个苹果，要放入,5,个,抽屉中，那么至少有一,个抽屉里面会放,2,个苹,果。,至少,“,抽屉原理”又称“鸽笼原理”，最先是由,19,世纪的德国数学家,狄里克雷,提出来的，所以又称“狄里克雷原理”。,狄里克雷,德国数学家。对数论、数学分析和数学物理有突出贡献，是解析数论的创始人之一。,1805,年,2,月,13,日生于迪伦，,1859,年,5,月,5,日卒于格丁根。中学时曾受教于物理学家,G.S.,欧姆；,1822,1826,年在巴黎求学，深受,J.-B.-J.,傅里叶的影响。回国后先后在布雷斯劳大学、柏林军事学院和柏林大学任教,27,年，对德国数学发展产生巨大影响。,1839,年任柏林大学教授，,1855,年接任,C.F.,高斯在格丁根大学的教授职位。,狄利克雷原则是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。,形式一：,设把,n,1,个元素分为,n,个集合,A,1,，,A,2,，,，,A,n,，用,a,1,，,a,2,，,，,a,n,表示这,n,个集合里相应的元素个数，证明至少存在某个,a,i,大于或等于,2.,形式二：设把,n,m,1,个元素分为,n,个集合,A,1,，,A,2,，,，,A,n,，用,a,1,，,a,2,，,，,a,n,表示这,n,个集合里相应的元素个数，证明至少存在某个,a,i,大于或等于,m,1,。,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,副，如想闭着眼睛从中取出两副颜色不同的手套，问至少要取出多少只才能达到要求？,12,12,1,25,至少取出,15,只手套才能达到要求,.,3.,在,23,23,的方格纸中，将,19,这,9,个数字填入每个小方格中，并对所有形如“十字”的图形中的,5,个数字和，对于小方格中的数字的任意一种填法，其中和数相等的“十字”图形至少有多少个？,练习：,在,2323,的方格纸中共有,2121=,441,个“十”字图形，,“,十”字图形中,5,个数字的和最小为,5,，最大为,45,，共有,45-4=,41,种不同的和,.,由,441=41,10,+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(50,51,99,100),4,15300,15301,得出矛盾,.,所以，至少有,5,人植树的株数相同,.,形式一：,设把,n,1,个元素分为,n,个集合,A,1,，,A,2,，,，,A,n,，用,a,1,，,a,2,，,，,a,n,表示这,n,个集合里相应的元素个数，证明至少存在某个,a,i,大于或等于,2.,形式二：设把,n,m,1,个元素分为,n,个集合,A,1,，,A,2,，,，,A,n,，用,a,1,，,a,2,，,，,a,n,表示这,n,个集合里相应的元素个数，证明至少存在某个,a,i,大于或等于,m,1,。,抽屉原理的两种常见形式,:,抽屉原理不仅在数学中有用，在现实生活中也到处在起作用，如招生录取、就业安排、资源分配、职称评定等等，都不难看到抽屉原理的作用。,谢谢,