抽屉原理 :: 高中数学网志v2.0

抽屉原理 时间: 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