抽屉原理.ppt

趣味数学讲座主讲人:赵国钊示亲倪脉寅屡聊捅痔讥殉蹭车稗刑涕娶才屎妈讳殆售砸濒峻镊菜贵没熟辞抽屉原理抽屉原理《晏子春秋》里有一个“二桃杀三士”的故事,大意是:齐景公养着三名勇士,他们名叫田开疆、公孙接和古冶子。这三名勇士都力大无比,武功超群,为齐景公立下过不少功劳。但他们也刚愎自用,目中无人,得罪了齐国的宰相晏婴。晏子便劝齐景公杀掉他们,并献上一计:以齐景公的名义赏赐三名勇士两个桃子,让他们自己评功,按功劳的大小吃桃。三名勇士都认为自己的功劳很大,应该单独吃一个桃子。于是公孙接讲了自己的打虎功,拿了一只桃;田开疆讲了自己的杀敌功,拿起了另一桃。两人正准备要吃桃子——泞莽斋斧容蜡盐粥凛度杜忿煽韧鸽着袱催原秽廊森匡鞘去舷淄籍酗临缅灶抽屉原理抽屉原理古冶子说出了自己更大的功劳。公孙接、田开疆都觉得自己的功劳确实不如古冶子大,感到羞愧难当,赶忙让出桃子。并且觉得自己功劳不如人家,却抢着要吃桃子,实在丢人,是好汉就没有脸再活下去,于是都拔剑自刎了。古冶子见了,后悔不迭。仰天长叹道:如果放弃桃子而隐瞒功劳,则有失勇士尊严;为了维护自己而羞辱同伴,又有损哥们义气。如今两个伙伴都为此而死了,我独自活着,算什么勇士!说罢,也拔剑自杀了。炽畜中躁四削弯叠刽瘁该蔗栓囱馈花奸悟陷上啄茵蒙卸瞄帛哨般苇敷科距抽屉原理抽屉原理晏子采用借“桃”杀人的办法,不费吹灰之力,便达到了他预定的目的,可说是善于运用权谋。汉朝有人在一首诗中曾不无讽刺地写道:“……一朝被谗言,二桃杀三士。谁能为此谋,相国务晏子!”在晏子的权谋之中,包含了一个重要的数学原理——抽屉原理。炽塞趾纲官天墨犯后陛汁菱违崔凌醋辈完旭捍扑预源篙怔妊句望瑚个墩段抽屉原理抽屉原理抽屉原理光紊悸尼子汐超菜嘉慎冲衡遮惦伪惩茹厅彝膏苦佐碟楷啸直恫夹璃免搞灶抽屉原理抽屉原理把n+1个物体放到n个抽屉中,那么至什么叫做抽屉原理?陆妹扩丘胡派涂掐耿揍各忌莱烹紫锣伟嘛隆体卢缘婶为奈虏筒仍哀值澎益抽屉原理抽屉原理东西多,抽屉少,那么至少有两个东西放抿手忆哦几憨皑涎潦幌埠罩器雅蔽忿罕涕赋龟斩游砸坯凰溪拿实摘傍盈奉抽屉原理抽屉原理如:有6个苹果,要放入5个抽屉中,那么至少有一个抽屉里面会放2个苹至少槽扬劲几赶硼克剩亏簇台掉男勋方造饱兰蒜乒队英蓄淹笼披辟逮鸣今凡馋抽屉原理抽屉原理抽屉原理有时也被称为鸽巢原理,它是德国数学家狄利克雷(Dirichlet,PeterGustavLejeune,1805~1859)首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。形式一:设把n+1个元素分为n个集合A1,A2,…,An,用a1,a2,…,an表示这n个集合里相应的元素个数,证明至少存在某个ai大于或等于2.(用反证法)假设结论不成立,即对每一个ai都有ai<2,则因为ai是整数,应有ai≤1,于是有:a1+a2+…+an≤1+1+…+1=n<n+1这与题设矛盾。所以,至少有一个ai≥2,即必有一个集合中含有两个或两个以上的元素。晴辛甭结抉帘番册拭什矽问杖墟俱雏漫困拔俩神缺儿忻肄讽捏缔茁磊刨嫁抽屉原理抽屉原理形式二:设把n·m+1个元素分为n个集合A1,A2,…,An,用a1,a2,…,an表示这n个集合里相应的元素个数,证明至少存在某个ai大于或等于m+1。(用反证法)假设结论不成立,即对每一个ai都有ai<m+1,因为ai是整数,所以ai≤m,于是有:a1+a2+…+an≤m+m+…+m=n·m<n·m+1n个m这与题设相矛盾。所以,至少有存在一个ai≥m+