抽屉原理(第一课时)

课题：抽屉原理
课时：第1课时
教学目的：
（1）学生能够初步学会用抽屉原理解决实际问题；
（2）进一步巩固抽屉原理的各种形式；
教学手段：计算机辅助教学
教学方法：问题教学法
教学过程：
一、从简单的填数谈起
1、 填数问题
能否在10×10的方格表的每个空格中分别填上1、2、3这三个数之一，使得每行、每列及对角线上的各个数字和互不相同？
2、填数问题的求解
【分析】在产生的数字和中，最小为10，最大为30，至多可能出现21种取值情况；而行数、列数与对角线共22，即使21种情况全出现，仍然有两个要重复，所以不可能使得这些数字和互不相同。

二、抽屉原理的基本形式
1、若有1+n 个元素放进n 个集合，则必存在一个集合至少放2个元素。

2、若把1+mn 个元素放进n 个集合，则必存在一个集合至少放有1+m 个元素。

3、若把121++++n m m m 个元素放进n 个集合，则必存在一个集合)1(n k A k ≤≤至少放有1+k m 个元素。

4、若),,2,1(0n i a i =>，且S a a a n =+++ 21，则必存在k a ，l a （n l k ≤≠≤1），使n S a k ≥，n
S a l ≤。

5、若021≥+++n a a a ，则必存在)1(0n k a k ≤≤≥；若021≤+++n a a a ，则必存在)1(0n k a k ≤≤≤。

6、若把无穷集合分成有限个集合，则必存在一个子集合含有无穷个元素。

7、若把[]1)1(210--++++n 个元素放进n 个集合，则至少有2个集合的元素一样多。

8、若把[]1)1(210--++++n k 个元素放进kn 个集合，则至少有1+k 个集合的元素一样多。

9、若把1-mn 个元素放进n 个集合，则必有一个集合至多含有1-m 个元素。

10、若把n 个面积为n S S S ,,,21 的平面图形放到面积为S 的平面图形上，并且S S S S n >+++ 21，则至少存在两个图形有公共点。

填数问题的数学原理解释：显然利用抽屉原理的原始形式就能对此给出正确结论。

三、例题精讲
例1、任给5个整数，证明必能从其中选出3个，使得它们的和能被3整除。

【分析】本问题属于数论方面的问题。

思路：利用整数关于模3的同余类进行情况分类与组合
【解答】任意一个整数a,关于模3同余有三种情况：0、1、2，假定任给的5个整数关于模3同余于,,,,,54321a a a a a 则{}2,1,0,,,,,54321∈a a a a a ；
情况一：,,,,,54321a a a a a 全相等。

若全为0，则5个整数都是3的倍数，所以任选三个，其和能被3整除；
若全为1，则任选三个其和关于模3同余为3，即和能被3整除；
若全为2，则任选三个其和关于模3同余为6，即和仍能被3整除。

情况二：,,,,,54321a a a a a 只出现两种不同的值，由抽屉原理可知，必然有三个取值相同，此时，不管同为0、1、2中的任何一个，以下的分析同于情况一。

情况三：,,,,,54321a a a a a 三种取值都出现，不妨设,2,1,0321===a a a 则,,,321a a a 所对应的整数其和关于模3同余为3，即和能被3整除。

【评注】该问题将数论问题利用抽屉原理来解决，既清晰又恰到好处。

例2、任何十个不同的两位数之集合必能选出两个不相交的子集，使每个子集的各数之和相等。

【分析】该问题属集合范畴，涉及子集及集合相交等基本概念，关于可数有限集合的子集问题，利用抽屉原理进行估数及分析子集之间的关系都是很好的途径。

思路：对可能出现的子集和情况数与子集总数进行对照，在比较选出的子集是否会有相交的情形出现。

【解答】显然由十个不同的两位数的集合所产生的子集个数为1024210=，除去空集与全集外，还有1022个子集。

在这1022个子集中，各数字之和最大为99+98+97+96+95+94+93+92+91=855，最小为10，所以，至多有855—10+1=846个不同的数字。

与子集数比较可知，必有两个子集的各数字之和相等。

不妨设为A 、B
若φ=⋂B A ，结论成立；若φ≠⋂B A ，作)(\),(\//B A B B B A A A ⋂=⋂=，显
然//,B A 为子集，并且各数字之和相等，φ=⋂//B A ，所以/
/,B A 为所求。

【评注】该问题用抽屉原理很容易得到子集A 、B ，但是接下来的对A 、B 的讨论分析就需要严密的逻辑思维，因此，通过这类型的例题可以进行这方面的培养与锻炼。

例3、证明：从52个正整数中，必可找出两数使之和或差可被100整除。

【分析】该问题仍属于数论方面的问题。

但比较例题1，就显得复杂多了。

首先关于模
100会出现100种同余类，但提供的却只有任意的52个正整数，其次结论要求选出两数进行和或者差运算，这些都增加了解题难度。

如果直接按所有余分类不太容易入手，我们可以尝试将所有余分组以后在分类。

【解答】把所有整数按模100的余数进行分组：{}{}{}{}{},50,51,49,,98,2,99,1,0 共51组，设这52个正整数为,,,,,52321a a a a 关于模100同余于,,,,,52321b b b b
若,,,,,52321b b b b 中有两数相同，不妨设为,21b b =则)(10021a a -；
若,,,,,52321b b b b 全不相同，由抽屉原理知必有两数同时落在{}{}{},51
,49,,98,2,99,1 之一中，不妨设,,21b b 落在{}99,1中，则)(10021a a +。

【评注】（1）本问题第一步把所有整数按模100的余数进行分组非常关键；
（2）本问题还可以进行重新改造。

变形：已知从n 个正整数中总能找出两数，使之和或差可被100整除，求n
的最小值。

提示：,51≤n 不行，比如，当51=n 时，选1、2、3、…、50、100，这样
的51个数便不符合要求。

四、课后作业
（1）一个棋手用11周时间参加一次比赛，每天至少比赛一局，但为免过于疲劳，他在每连续7天内比赛不超过12局，总共赛132局。

求证：必有连续若干天他恰好共赛了21局，是否必有连续若干天他恰好共赛了22局？
此问题可以有另外一种抽象的问法
变形；设 ,,,,21n x x x 是一个正整数列，满足12767≤++-l l x x （ ,2,1=l ），令i i x x x S +++= 21，求证：对任意正整数n ，一定有下标j 和k （其中)k j <，使地n S S j k =-成立。