资源描述
趣味数学讲座,主讲人:赵国钊,晏子春秋里有一个“二桃杀三士”的故事,大意是: 齐景公养着三名勇士,他们名叫田开疆、公孙接和古冶子。 这三名勇士都力大无比,武功超群,为齐景公立下过不少功劳。但他们也刚愎自用,目中无人,得罪了齐国的宰相晏婴。晏子便劝齐景公杀掉他们,并献上一计:以齐景公的名义赏赐三名勇士两个桃子,让他们自己评功,按功劳的大小吃桃。 三名勇士都认为自己的功劳很大,应该单独吃一个桃子。于是公孙接讲了自己的打虎功,拿了一只桃;田开疆讲了自己的杀敌功,拿起了另一桃。两人正准备要吃桃子 ,古冶子说出了自己更大的功劳。公孙接、田开疆都觉得自己的功劳确实不如古冶子大,感到羞愧难当,赶忙让出桃子。并且觉得自己功劳不如人家,却抢着要吃桃子,实在丢人,是好汉就没有脸再活下去,于是都拔剑自刎了。古冶子见了,后悔不迭。仰天长叹道:如果放弃桃子而隐瞒功劳,则有失勇士尊严;为了维护自己而羞辱同伴,又有损哥们义气。如今两个伙伴都为此而死了,我独自活着,算什么勇士!说罢,也拔剑自杀了。,晏子采用借“桃”杀人的办法,不费吹灰之力,便达到了他预定的目的,可说是善于运用权谋。汉朝有人在一首诗中曾不无讽刺地写道:“一朝被谗言,二桃杀三士。谁能为此谋,相国务晏子!”,在晏子的权谋之中,包含了一个重要的 数学原理抽屉原理。,抽屉原理,把n+1个物体放到n个抽屉中,那么至 少有一个抽屉里有不止一个这种物体。,什么叫做抽屉原理?,东西多,抽屉少,那 么至少有两个东西放 在一个抽屉里。,如:,有6个苹果,要放入5个 抽屉中,那么至少有一 个抽屉里面会放2个苹 果。,至少,抽屉原理有时也被称为鸽巢原理,它是德国数学家狄利克雷 (Dirichlet ,Peter Gustav Lejeune,1805 1859) 首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。,形式一: 设把n1个元素分为n个集合A1,A2,An,用a1,a2,an表示这n个集合里相应的元素个数,证明至少存在某个ai大于或等于2.,(用反证法)假设结论不成立,即对每一个ai都有ai2,则因为ai是整数,应有ai1,于是有:a1a2an111nn1这与题设矛盾。,所以,至少有一个ai2,即必有一个集合中含有两个或两个以上的元素。,形式二: 设把nm1个元素分为n个集合A1,A2,An,用a1,a2,an表示这n个集合里相应的元素个数,证明至少存在某个ai大于或等于m1。,(用反证法)假设结论不成立,即对每一个ai 都有aim1,因为ai是整数,所以aim,于是有:,a1a2anmmmnm nm1,这与题设相矛盾。,所以,至少有存在一个aim1.,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副,如想闭着眼睛从中取出两副颜色不同的手套,问至少要取出多少只才能达到要求?,1212125,至少取出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. 边长为1的正方形中,任意放入9个点,求证这9 个点中任取3个 点组成的三角形 中,至少有一 个的面积不超 过1/8.,E,D,F,G,解:将边长为1的正方形等分成边长为,的四个小正方形,视这四个正方形为 抽屉,9个点任意放入这四个正方形中, 据形式2,必有三点落入同一个正方形 内.现特别取出这个正方形来加以讨论.,把落在这个正方形中的三点记为D、E、F. 通过这三点中的任意一点(如E)作平行 线, 如图可知:,h,SDEFSDEGSEFG ,E,D,F,G,6. 任取5个整数,必然能够从中选出三个,使它们的和能够被3整除.,练习:,证明:任意给一个整数,它被3除,余数可能为0,1,2,我们把被3除余数为0,1,2的整数各归入类r,r1,r2.至少有一类包含所给个数中的至少两个.因此可能出现两种情况:,.某一类至少包含三个数; .某两类各含两个数,第三类包含一个数.,若是第一种情况,就在至少包含三个数的那一类中任取三数,其和一定能被3整除;,若是第二种情况,在三类中各取一个数,其和也能被3整除.综上所述,原命题正确.,7. 某校派出学生204人上山植树15301株,其中最少一人植树50株,最多一人植树100株,则至少有5人植树的株数相同.,练习:,证明:按植树的多少,从50到100株可以构造51个抽屉,则个问题就转化为至少有5人植树的株数在同一个抽屉里.,(用反证法)假设无人或人以上植树的株数在同一个抽屉里,那只有人以下植树的株数在同一个抽屉里,而参加植树的人数为204人,所以,每个抽屉最多有4人,故植树的总株数最多有:,4(505199100) 4,15300 15301 得出矛盾.,所以,至少有5人植树的株数相同.,形式一: 设把n1个元素分为n个集合A1,A2,An,用a1,a2,an表示这n个集合里相应的元素个数,证明至少存在某个ai大于或等于2.,形式二: 设把nm1个元素分为n个集合A1,A2,An,用a1,a2,an表示这n个集合里相应的元素个数,证明至少存在某个ai大于或等于m1。,抽屉原理的两种常见形式:,抽屉原理不仅在数学中有用,在现实生活中也到处在起作用,如招生录取、就业安排、资源分配、职称评定等等,都不难看到抽屉原理的作用。,谢谢,
展开阅读全文