haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

抽屉原理3.12

发布时间:2014-04-03 09:04:04  












《晏子春秋》里有一个“二桃杀三士”的故事, 大意是: 齐景公养着三名勇士,他们名叫田开疆、 公孙接和古冶子。 这三名勇士都力大无比,武功超群,为齐景公 立下过不少功劳。但他们也刚愎自用,目中无人, 得罪了齐国的宰相晏婴。晏子便劝齐景公杀掉他们, 并献上一计:以齐景公的名义赏赐三名勇士两个桃 子,让他们自己评功,按功劳的大小吃桃。 三名勇士都认为自己的功劳很大,应该单独吃 一个桃子。于是公孙接讲了自己的打虎功,拿了一 只桃;田开疆讲了自己的杀敌功,拿起了另一桃。 两人正准备要吃桃子 ——

古冶子说出了自己更大的功劳。公孙接、田开疆都 觉得自己的功劳确实不如古冶子大,感到羞愧难当, 赶忙让出桃子。并且觉得自己功劳不如人家,却抢 着要吃桃子,实在丢人,是好汉就没有脸再活下去, 于是都拔剑自刎了。古冶子见了,后悔不迭。仰天 长叹道:如果放弃桃子而隐瞒功劳,则有失勇士尊 严;为了维护自己而羞辱同伴,又有损哥们义气。 如今两个伙伴都为此而死了,我独自活着,算什么 勇士!说罢,也拔剑自杀了。

晏子采用借“桃”杀人的办法,不费吹灰之 力,便达到了他预定的目的,可说是善于运用权 谋。汉朝有人在一首诗中曾不无讽刺地写道: “……一朝被谗言,二桃杀三士。谁能为此谋, 相国务晏子!”

在晏子的权谋之中,包含了一个重要的 数学原理——抽屉原理。

抽屉原理有时也被称为鸽巢原理,它是德国数学家狄利 克雷 (Dirichlet ,Peter Gustav Lejeune,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+1 这与题设相矛盾。 所以,至少有存在一个ai≥m+1.
n个 m

1947年,匈牙利数学家把这

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com