抽屉原理 :: 高中数学网志v2.0
未识别博客 · mathsblog · 2004-06-23
抽屉原理
时间: 2004/06/23
抽屉原理是组合数学中一个非常有用和重要的方法。本文将用它处理三个组合问题。例1和例2是与整除有关的问题,同学们读后不妨想一想,任意多少个整数中,至少有4个数的和为4的倍数,把4换成5、6,或者是n,能否得出一般的结论?
[定理引入]
若5个苹果放在两个抽屉中,则至少有一个抽屉有3个苹果,即有
个苹果;
若有10只鸽子,放在3个笼子中,则至少有一个笼中关有4只鸽子,即
只鸽子……
定理:若有p个元素放入q个盒子中,则当q|p时,至少有一个盒子中,放有
个元素;若q
p时,至少有一个盒子中,放有
+1个元素。
[定理应用]
例1.任意三个整数中,至少有两个整数的和为2的倍数,请予证明。
证明:任一整数或者是偶数,或者是奇数,再构造两只抽屉,一只放偶数,一只放奇数,根据抽屉原理,
,即至少有一个抽屉放了两个奇数,或者两个偶数,无论是哪一种情况,该抽屉内所放两数的和都是偶数(证毕)。
例2.任意5个整数中,至少有3个数的和为3的倍数。
分析:任一整数被3除的余数只有3种可能:或者整除,则余数为0,或者不能整除,则余数为1或2.
我们构造3个抽屉,分别放置形如3m、3m+1、3m+2的数,其中
,这三类数也可称为余0类,余1类,余2类。
把任意五个整数,按其余数情况放入这三个抽屉,由抽屉原理:必有某一抽屉有整数。
(个)
对这三个抽屉的数,进行分类讨论,命题可以得证。
证明:按余0类,余1类,余2类构造三个盒子,由抽屉原理,必有一盒子放有
个关于3的余数相同的数,则另外3个盒中放的3个数,或者同属一类,这时结论显然成立;若2个属一类,另一个属一类,这时从三类不同余数的盒子,各抽一个数,则此三数和必为3的倍数。
因而无论整数在三个抽屉中如何分布,总能找到其和为3的倍数的三个数。
例3.下面的结论是否正确,请予证明或举反例说明其伪。
在1999年高中数学冬令营中,有82名来自各省市的优秀选手,则其中必有10位选手来自同一省市或者来自十个不同省市。
解:若其中参加冬令营的省市超过10个,结论显然成立;若这些选手来自的省市不足十个,则由抽屉原理,必有一省市来了。
名选手,不论何种情况,结论成立
mathsblog
引用(Trackback0)
|
编辑
评论
发表评论
用户名:
Email:
主页:
最后更新
§1.3 交集、并集
§1.2 子集、全集、补集
§1.1集合
西方理性数学的倡导者――泰 勒 斯
最富创造性的数学家―黎曼
坚持理论联系实际
例谈创造性思维的自我培养
数学历史上的三次危机
圆锥曲线的产生与发展
数学家的文学修养
原始快照:web.archive.org