资源预览内容
第1页 / 共29页
第2页 / 共29页
第3页 / 共29页
第4页 / 共29页
第5页 / 共29页
第6页 / 共29页
第7页 / 共29页
第8页 / 共29页
第9页 / 共29页
第10页 / 共29页
亲,该文档总共29页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
主讲人:赵国钊主讲人:赵国钊晏子春秋里有一个“二桃杀三士”的故事, 大意是: 齐景公养着三名勇士,他们名叫田开疆 、公孙接和古冶子。 这三名勇士都力大无比,武功超群,为齐景公 立下过不少功劳。但他们也刚愎自用,目中无人, 得罪了齐国的宰相晏婴。晏子便劝齐景公杀掉他们 ,并献上一计:以齐景公的名义赏赐三名勇士两个 桃子,让他们自己评功,按功劳的大小吃桃。三名勇士都认为自己的功劳很大,应该单独吃 一个桃子。于是公孙接讲了自己的打虎功,拿了一 只桃;田开疆讲了自己的杀敌功,拿起了另一桃。 两人正准备要吃桃子 古冶子说出了自己更大的功劳。公孙接、田开疆都 觉得自己的功劳确实不如古冶子大,感到羞愧难当 ,赶忙让出桃子。并且觉得自己功劳不如人家,却 抢着要吃桃子,实在丢人,是好汉就没有脸再活下 去,于是都拔剑自刎了。古冶子见了,后悔不迭。 仰天长叹道:如果放弃桃子而隐瞒功劳,则有失勇 士尊严;为了维护自己而羞辱同伴,又有损哥们义 气。如今两个伙伴都为此而死了,我独自活着,算 什么勇士!说罢,也拔剑自杀了。 晏子采用借“桃”杀人的办法,不费吹灰之力 ,便达到了他预定的目的,可说是善于运用权谋 。汉朝有人在一首诗中曾不无讽刺地写道:“ 一朝被谗言,二桃杀三士。谁能为此谋,相国务 晏子!” 在晏子的权谋之中,包含了一个重要的 数学原理抽屉原理。 抽屉原理有时也被称为鸽巢原理,它是德国数学家狄利 克雷 (Dirichlet ,Peter Gustav Lejeune,1805 1859) 首先明确 的提出来并用以证明一些数论中的问题,因此,也称为狄利 克雷原则。它是组合数学中一个重要的原理。把它推广到一 般情形有以下几种表现形式。 形式一: 设把n1个元素分为n个集合A1,A2 ,An,用a1,a2,an表示这n个集合里相应的 元素个数,证明至少存在某个ai大于或等于2.(用反证法)假设结论不成立,即对每一个ai都有ai2,则 因为ai是整数,应有ai1,于是有:a1a2an11 1nn1这与题设矛盾。 所以,至少有一个ai2,即必有一个集合中含有两个或两个以 上的元素。形式二: 设把nm1个元素分为n个 集合A1,A2,An,用a1,a2,an表示 这n个集合里相应的元素个数,证明至少存在 某个ai大于或等于m1。(用反证法)假设结论不成立,即对每一个 ai 都有aim1,因为ai是整数,所以aim,于 是有: a1a2anmmmnm nm1n个m 这与题设相矛盾。 所以,至少有存在一个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。要使要使1616个小朋友个到的饼干数各不相同至个小朋友个到的饼干数各不相同至少需要少需要1+2+3+1+2+3+15+16=+15+16=这与只有这与只有135135块饼干矛盾块饼干矛盾. .所以一定有所以一定有2 2个个 小朋友得到的饼干数目相同小朋友得到的饼干数目相同. .假设无人借假设无人借6 6本或本或6 6本以上的图书,本以上的图书, 则全班至多借书则全班至多借书542=542=210210(本)(本). .但全班但全班 共借来共借来212212本,所以要么至少有两人借本,所以要么至少有两人借6 6 本,要么至少有本,要么至少有1 1人借人借7 7本本. .1.有黑色、白色、黄 色的筷子各8根,混杂在一起, 黑暗中想从这些筷子中取出颜 色不同的两双筷子,问至少要 取多少根才能保证达到要求?最多取出最多取出8 8根只有一种颜色的筷子根只有一种颜色的筷子 ,再取任意,再取任意3 3根即可保证达到要求。所根即可保证达到要求。所 以至少要取以至少要取1111根根. .2.在1只箱子里面放着红、 黑、白三种颜色的手套各6副, 如想闭着眼睛从中取出两副颜 色不同的手套,问至少要取出 多少只才能达到要求?1212125至少取出至少取出1515只手套才能达到要求只手套才能达到要求. .3.在2323的方格纸中,将19 这9个数字填入每个小方格中,并对 所有形如“十字”的图形中的5个数字 求和,对于小方格中的数字的任意一 种填法,其中和数相等的“十字”图形 至少有多少个?在在23232323的的 方格纸中共有方格纸中共有 2121=2121=441441个个“ “十十 ” ”字图形,字图形,“ “十十” ”字图字图 形中形中5 5个数字的个数字的 和最小为和最小为5 5,最,最 大为大为4545,共有,共有 45-4=45-4=4141种不同种不同 的和的和. .由由441=41441=411010+30+30可知,和数相等的可知,和数相等的“ “十十” ” 字图形至少有字图形至少有1111个个. .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.EDF G解:将边长为1的正方形等分成边长为的四个小正方形,视这四个正方形为 抽屉,9个点任意放入这四个正方形中, 据形式2,必有三点落入同一个正方形 内.现特别取出这个正方形来加以讨论.把落在这个正方形中的三点记为D、E、F. 通过这三点中的任意一点(如E)作平行 线, 如图可知:hSDEFSDEGSEFG EDFG6. 任取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)415300 15301 得出矛盾. 所以,至少有5人植树的株数相同.形式一: 设把n1个元素分为n个集合A1 ,A2,An,用a1,a2,an表示这n个集 合里相应的元素个数,证明至少存在某个ai大 于或等于2.形式二: 设把nm1个元素分为n个集 合A1,A2,An,用a1,a2,an表示这n 个集合里相应的元素个数,证明至少存在某个 ai大于或等于m1。抽屉原理的两种常见形式 :抽屉原理不仅在数学中有用,在 现实生活中也到处在起作用,如招生 录取、就业安排、资源分配、职称评 定等等,都不难看到抽屉原理的作用 。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号