tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

高二数学竞赛班讲义 第六讲 组合问题


高二数学竞赛班二试 第六讲 组合问题
班级 姓名

一、知识要点:
组合数学是一个既古老又年轻的离散数学分支, 竞赛中的组合问题主要包括组合计数问 题、组合极值问题、存在性问题、操作变换问题、组合几何问题以及图论中的问题,求解竞 赛中的组合问题并不是需要复杂的数学知识, 然而在趣味性命题的陈述下包含了高超的解题 技巧,无论是从智力训练的角度

,还是从竞赛准备的角度考虑,理解和钻研这些问题都是十 分有意义的. 在解决组合问题时,有时会用到以下几个原理. 1、极端原理 原理 1 设 M 是自然数集的一个非空子集,则 M 中必有最小数. 原理 2 设 M 是实数集的一个有限的非空子集,则 M 中必有最小数. 2、抽屉原理 把 5 个苹果放到 4 个抽屉中, 必然有一个抽屉中至少有 2 个苹果, 这是抽屉原理的通俗 解释。一般地,我们将它表述为:把(mn+1)个物体放入 n 个抽屉,其中必有一个抽屉中 至少有(m+1)个物体。 使用抽屉原理解题,关键是构造抽屉。一般说来,数的奇偶性、剩余类、数的分组、染 色、线段与平面图形的划分等,都可作为构造抽屉的依据。 第一抽屉原理 小球. 第二抽屉原理 若将 m 个小球放入 n 个抽屉中,则必有一个抽屉内至多有 ? 若将 m 个小球放入 n 个抽屉中,则必有一个抽屉 内至少有 ? ? ?1个 ? n ?

? m ? 1?

?m? ? 个小球. ?n?

3、算两次原理 所谓算两次原理(又称富比尼原理)就是对同一个量,如果用两种不同的方法去计算, 所得的结果应相等.

二、经典例题
例 1. (2008 年山西省预赛试题)设 M={1,2,…,2008}是前 2008 个正整数组成 的集合,A={ a1 , a2 ,… a30 }是 M 的一个 30 元子集,已知 A 中的元素两两互质,证
1

明 A 中至少一半元素是质数. 分析 考查集合 A 中的合数 a,设 p 是 a 的最小质因数,则 p≤ a .又 a≤2008,于是

p≤45,再由 A 中的元素两两互质,可以证明 A 中 16 个元素中必有一个是质数,进而可以 导出结论. 证明 先证明:A 中 16 个元素中必有一个是质数. 为此,任取 16 个元素,不妨设为 a1 , a2 ,…, a16 ,若其中没有质数,则它们中至 多一个为 1,其余 15 个皆为合数.设 a1 , a2 ,…, a15 都是合数,则每个数皆可分解成 至少两个质因数的乘积,若 pi 是 ai 的最小质因数,则 pi ≤

ai (i=1,2,…,15) .由

于 A 中的数两两互质,则 p1 , p2 ,…, p15 互不相同,而将全体质数自小到大排列,第 15 个质数是 47,所以,若 p1 是 p1 , p2 ,…, p15 中的最大数,即有 p1 ≥47,于是 a1 ≥ p1 ≥ 47 >2008,即 a1 ? M,矛盾!
2 2

因此, a1 , a2 ,…, a15 中必有质数,不妨设 a1 为质数,今从集合 A 中去掉 a1 , 在剩下的 29 个元素中,再次进行同样的讨论,可知其中的 16 个元素中也必有一个是质数, 设为 a2 .如此下去,可以连续进行 15 次,每次都可从 A 中取到一个新的质数, 因此 A 中 至少有 15 个质数. 说明 本题利用极端原理,通过对合数的最小质因数的考查,获取集合 A 中元素的

性质,进而完成了证明,这种方法也是数论中研究合数的一种重要策略. 例 2.已知 A 与 B 是集合{1,2,3,…,100}的两个子集,满足:A 与 B 的元素个 数相同, A∩B 为空集, n ? A 时总有 2n+2 ? B, 且 若 则集合 A∪B 的元素个数最多为多少? 分析 该问题是组合构造,由条件“A 与 B 的元素个数相同且若 n∈A 时总有 2n+2∈B”

知|A|=|B|,且 2n+2≤100,从而可知 A 中的元素不超过 49 个,为此需要进行分类考虑. 解 首先证明|A∪B|≤66,只需要证明|A|≤33,由分析知需要证明:若 A 是{1,2,

3,…,49}的任何一个 34 元子集,则必存在 n ? A,使得 2n+2 ? A. 证明如下: 将{1,2,3,…,49}分成如下 33 个集合: {1,4}{3,8}{5,12} , , ,?, {23,48} ,共 12 个; {2,6}{10,22}{14,30} , , , {18,38} ,共 4 个; {25}{27}{29} , , ,…, {49} ,共 13 个; {26}{34}{42}{46} , , , , 共 4 个.

2

若 A 是{1,2,3,…,49}的任何一个 34 元的子集,则由抽屉原理可知上述 33 个集 合中至少有一个 2 元集合中的两个数均属于 A,即存在 n∈A,2n+2∈A. 所以|A|≤33. 事实上,如取 A={1,3,5,…,23,2,10,14,18,25,27,29,…,49,26,34, 42,46} ,B={2n+2|n∈A} ,则 A,B 满足题中要求,且|A∪B|=66. 所以集合 A∪B 的元素个数最多为 66. 说明 将集合中的元素进行适当分会组, 并结合抽屉原理使问题得以解决, 这是解决

类问题的常用手段. 例 3. (2007 年浙江省预赛试题)设 M={1,2,…,65} ? M 为子集,若|A|=33, ,A

且存在 x ,y∈A,x<y,x | y,则称 A 为“好集”,求最大的 a∈M,使含 a 的任意 33 元子集 为好集. 分析 首先要准确理解“好集”的含义,搞清楚“好集”中元素的构成规律,再来分析 a

的可能的取值. 解 33. 显然对任意 1≤i<j≤44,不存在 n≥3,使得 21+j = n (21 +i )成立,故 P 是非好集. 因此 a≤21,下面证明:包含 21 的任意一个 33 元子集 A 一定为好集. 设 A ={ a1 , a2 ,…, a32 ,21} . 若 1,3,7,42,63 中之一为集合 A 的元素,显然 A 为好集 现考虑 1,3,7,42,63 都不属于集合 A.构造集合: 令 P={21 + i | i =1,2,…,44}— {2(21 + i)| i = 1,2,…,11} p | = ,|

A1 ={2,4,8,16,32,64} , A2 ={5,10,20,40} ,

A3 ={6,12,24,48} A4 ={9,18,36} , , A5 ={11,22,44} A6 ={13,26,52} , , A7 ={14,28,56} A8 ={15,30,60} , , A9 ={17,34} A10 ={19,38} , ,
A11 ={23,36} A12 ={25,50} , ,
3

A13 ={27,54} A14 ={29,58} , , A15 ={31,62} , A' ={33,35,37,…,61,65} ,
由上可见, A1 , A2 ,…, A15 每个集合中两个元素都是倍数关系,考虑最不利的情
' ' 况,即 A ? A,也即 A 中 16 个元素全部选作 A 的元素,A 中剩下 16 个元素必须从 A1 ,

A2 ,…, A15 这 15 个集合中选取,根据抽屉原理,至少有一个集合有两个元素被选,即
集合 A 中至少有两个元素存在倍数关系. 综上所述,包含 21 的任意一个 33 元子集 A 一定为好集,即 a 的最大值为 21. 说明 对于这一类型的集合问题,一般都需要通过适当的方式构造出符合某种要求的

集合,抽屉原理是解决集合构造问题的常用工具. 例 4. (2008 年甘肃省预赛试题)一个 20 行若干列的 0、1 数阵满足:各列互不相同 且任意两列同一行都取 1 的行数不超过 2.求当列数最多时,数阵中 1 的个数的最小值. 分析 由题设,对于数阵中 1 的个数超过 3 的列,保留其中任意 3 个 1,而将其

余的都变成 0,得到的新数阵仍然满足要求,于是可知当列数最多时,数阵中至多包含 1 的 个数不超过 3 的所有的列.这样可得列数最大值,进而求得此时数阵中 1 的个数的最小值. 解 对于满足条件的列数最大的一个数阵, 如果这个数阵中某一列 1 的个数超过 3

个,那么就保留其中任意 3 个 1,其余的都改变成 0,这样就会得到一个列数相同并有仍然 满足要求的一个新数阵,如果这个新数阵中还有 1 的个数超过 3 的列,则重复上述过程, 最后可以得到一个列数最多,且每列中 1 的个数最多为 3 的满足要求的数列,它的列数最 多为 1+ C 20 + C 20 + C 20 . 另一方面,构造一个满足要求的数阵如下:它包括没有 1 的列以及所有互不相同的只 有一个 1 的列,2 个 1 的列和 3 个 1 的列,由上所说,可知这个数阵的列数是最多的,同时 在满足要求的列数最多的所有数阵中所有数阵中,该数阵中的 1 是最少的,此数阵的列数 为 1+ C 20 + C 20 + C 20 ,此数列中 1 的个数是 C 20 + 2C 20 + 3 C 20 =20+380+3420=3820 说明 本题中求数阵的列数的最大值的方法叫做局部整法,它是解决最值问题的一种
1 2 3 1 2 1 2 3

3

行之有效的方法,尤其是离散变量最值问题常常需要用到这种方法. 例 5. (2008 年浙江省预赛试题)将 3k(k 为正整数)个石子分成五堆,如果通过每
4

次从其中 3 堆中各取走一个石子,而最后取完,则称这样的分法是“和谐的”,试给出和谐分 法的充分必要条件,并加以证明. 分析 从整体上看,就是从 3k 个石子中每次取 3 个,恰好 k 次取完,于是和谐的分法

就是要求每堆石子的个数不超过 k,再用数学归纳法证明,最多一堆石子的个数不超过 k 的 分法是和谐的. 解 分析是和谐的充分必要条件是最多一堆石子的个数不超过 k.

下面设五堆石子的个数分别为 a、b、c、d、e(其中 a≥b≥c≥d≥e) . “必要性”的证明:若分法是和谐的,则把 a 所对应的石子取完至少要取 a 次,这 a 次每 次都要取走 3 个石子,如果 a>k,则 3a>3k,即把 a 所对应的一堆取完时,需取走的石子 多于五堆石子的总数,矛盾,因此最多一堆石子的个数不能超过 k. “充分性”的证明: (数学归纳法) (1)当 k = 1 时,满足 a≤k 的分法只能是 1、1、1、0、0.显然这样的分法是和谐 的. (2)假设 k≤n 时,若 a≤k 的分法是和谐的. 当 k = n+1 时,若 a≤n+1,且分法 a、b、c、d、e 是不和谐的,则分法 a-1、b-1、 c-1、d、e 也是不和谐的.由(2)及必要性的证明,可知 max{a-1,b-1,c-1,d,e}>n. 因为 a≥b≥c≥d≥e,所以 max{a-1,b-1,c-1,d,e} =max{a-1,d}>n. 若 a-1≥d,则有 a-1>n.这与 a≤n+1 矛盾. 若 a-1<d,则有 n < d ≤ c ≤b ≤ a ≤ n+1, 从而有 a = b = c = d = n+1,于是有 3(n+1)= a + b + c + d + e = 4 (n+1) + e, 这是不可能的. 因此,当 a≤n+1 时,分法 a、b、c、d、e 是和谐的 说明 本题充分性的证明采用的是数学归纳法,这是一种归纳构造,它是利用构造

思想解决存在性问题的一种重要手段
5

例 6. (1988 年全国联赛试题)在坐标平面上是否存在一个含有无穷多条直线 l1 ,

l2 ,…, l n ,…的直线族,满足条件:
(1)点(1,1)∈ l n ,n =1,2,3,…; (2) k n ?1 = an - bn ,其 k n ?1 中是 l n ?1 的斜率, an 和 bn 分别是 l n 在 x 轴和 y 轴上 的截距, k1 是 l1 的斜率,n = 1,2,3,…; (3) k n k n ?1 ≥0,n = 1,2,3,… 并证明你的结论 分析 假设这样的直线族存在,先利用直线 l n 的方程求出 an 与 bn ,即可得到{ k n }

的递推关系,再结合条件(3)求解 解 题中给出的是以点(1,1)为公共点的中心直线族,若这样的直线族存在,则 l n

的方程为 y-1 =

k n ?x ? 1?
1 kn

当 y = 0 时,-1= k n ?a n ? 1? , an = 1-

当 x = 0 时, bn -1= - k n , bn = 1- k n 因为 l n 存在,所以 an 和 bn 都存在,从而 k n ≠0,n = 1,2,3,…,利用条件(2) 有

k n ?1 = an - bn = k n -
继续有

1 kn

k n = k n ?1 -
……

1 k n ?1

k 2 = k1 -

1 k1

以上诸式相加得到

k n ?1 = k1 -(

1 1 1 + +…+ ) kn k1 k2



由 k n ≠0 及条件(3)得 k n k n ?1 >0,故所有的 k i (i = 1,2,3,…)同号,不妨设 k i
6

>0,则 k n ?1 = k n -

1 1 1 < k n ,即数列{ k n }是正项递减数列,从而 > ,于是 kn k n ?1 k n

1 1 1 n + +…+ > kn k1 k2 k1
这样,由?式得

k n ?1 < k1 -
2

k12 ? n n = k1 k1

?

当 n > k1 时,由?式推出 k n ?1 <0.由假设 k n >0,得 k n k n ?1 <0,与己知矛盾 同理可证,当 k n <0 时,也导致矛盾 所以,同时满足条件(1)(2)(3)的直线族不存在 , , 说明 本题是探索性质的存在性问题,解决问题时,常常需要先作出判断,明确解题

方法,再求解,这对学生的能力提出了更高的要求 例 7. (2007 年吉林省预赛试题)一个空间中的点组成的集合S满足性质:S中任意两 点之间的距离互不相同,假设S中的点的坐标(x,y,z)都是整数,并且1≤ x,y,z ≤ n,证明:集合 S 的元素个数小于 min{ (n+2)· 证明 都有

n ,n 6 } 3

记 | S | = t ,则对任意( x1, y1, z1, )( x2, y2, z2, )∈S, ,

?x1 ? x2 ?2 + ? y1 ? y2 ?2 + ?z1 ? z2 ?2 ≤3 ?n ? 1?2
(因为满足 1≤x,y,z≤n 的整点之间的距离不超过(1,1,1)与(n,n,n)之间的 距离) 并且依题意,S 中任意两点之间的距离互不相同,故 Ct ≤3 ?n ? 1? ,
2

2

得 t -t ≤ 6 ?n ? 1? ,于是
2
2

t≤

1 1 + 2 2

1 ? 24 ?n ? 1? < n 6
2

(最后一个不等式价于 1+24 ?n ? 1? < 2n 6 ? 1 ,展开后移项即可得到)
2
2

?

?

另一方面,对 S 中的任意两点( xi , y i , z i , )( xi , yi , zi , ) 、 ,考虑集合{a,b,c}(允许 出现重复元素),这里 a = | xi ? x j |,b =| y i ? y j |,c = | z i ? z j |,依题意,所得的{a, b,c}两两不同,且 0 ≤ a,b,c≤n -1,a、b、c 不全为 0,于是,我们有
7

3 2 1 C t2 ≤ Cn ? 2Cn ? Cn ? 1




3 2 1 C t2 < Cn ? 2Cn ? Cn

解得 t<

1 1 1 ? ? n?n ? 1??n ? 2? . 2 4 3 n . 3

当 n≥3 时,有 t< ?n ? 2? 这只需证明

1 ? 2
等价于

1 1 ? n?n ? 1??n ? 2 ? ≤ ?n ? 2 ? 4 3
2

n , 3

? 1 1 n 1? ? n?n ? 1??n ? 2?≤ ??n ? 2? ? ? , 4 3 3 2? ?
展开后移项即可知此不等式在 n≥3 时成立) . 于是,当 n≥3 时,总有 t≤ min ??n ? 2?

? ?

? n , n 6? 3 ?



而当 n=1 时,t=1;当 n=2 时,由①知 t≤3,这时②都成立,命题获证. 说明:本题从两个不同的角度,分别得到了 Ct 的上界,从而完成了证明.这种思想的 实质是算两次原理.它是研究跟计算有关的组合问题的一种重要策略. 例 8. (2009 年山西省预赛试题)有七种颜色的珍珠,共计 14 颗,其中每种颜色的珍珠 各两颗;今把这珍珠分装于七个珠盒中,使得每个珠盒中各有一对不同颜色的珍珠. (1)证明:不论各盒中的珍珠怎样搭配,总可以将这七个珠盒分别放置于一个正七边 形的七个顶点之上,使得七边形的任两个相邻顶点处所放置的盒中的四颗珍珠互不同色. (2)如将以上条件与待证结论中的“七”一律改为“五”,“14”改为“10”,则情况如何? 分析:本题的文字叙述难以找出一般规律,把文字语言首先转化为图论语言,再借助图 的性质找出问题的解决思路. 解: (1)用点 v1,v2,…,v7 分别表示这七种颜色,如果一个 vi 色的珍珠和一个 v j 色的 珍珠装在同一盒中(i≠j) ,则在点 vi 与 v j 间连一条边,这样就得到一个图 G(点 vi 与 v j 之
2

8

间有可能连出两条边) ,由于同一色的珍珠有两颗,每颗珍珠都需与一颗其他颜色的珍珠共 盒,则图 G 的每点恰好发出两条边;从 G 的任一点 A 出发,沿一条边走到点 B,再由 B 沿 另一条边走到 C,…,如此下去,最后必定回到出发点 A(这是由于,途中经过的每个点 P 都有两条边,若参沿一条边进入点 P,则必沿另一条边可离开点 P,而由点 P 不能再加到途 中已经过的点,因为这种点所发出的两条边都已走过,因此只能到达新点或回到出发点, 而新点终将逐渐耗尽,最后必定回到出发点 A) ,这样就得到一个圈. 去掉这个圈,若剩下还有点,依上述方法,又将得到新的圈,若称两点的的圈为“两边 形”,则图 G 的结构只有如下四种情况: 1° 一个七边形

2° 一个五边形和一个两边形

3° 一个四边形和一个三角形

4° 一个三角形和两个两边形

9

对于每种情况, 我们都对相应的边作出适当编号, 并将这些边所对应的珠盒放置于七边 形的顶点之上,如图 5 所示.

因此所证结论成立. (2)当 14 颗七以珍珠改为 10 颗五色珍珠后,结论不成立.例如,对于五色

v1 , v2 , v3 , v4 , v5 ,我们若将 10 颗珍珠这样装盒: e1 ? ?v1 , v2 ?, e2 ? ?v2 , v3 ? , e3 ? ?v3 , v1 ? , e4 ? ?v4 , v5 ? , e5 ? ?v4 , v5 ? ,则无论怎样摆放于正五边形的顶点上,都不能满足条件(因为
e1 、e2 、e3 中,任两盒都有同色的珠,无论怎样摆放于正五边形的顶点上,必有两盒相邻) .
第 13 讲 抽屉原理 例 1 从 1,2,3,?,100 这 100 个数中任意挑出 51 个数来,证明在这 51 个 数中,一定: (1)有 2 个数互质; (2)有 2 个数的差为 50; (3)有 8 个数,它们的最大公约数大于 1。 证明:(1)将 100 个数分成 50 组: {1,2},{3,4},?,{99,100}。
10

在选出的 51 个数中,必有 2 个数属于同一组,这一组中的 2 个数是两个相邻的 整数,它们一定是互质的。 (2)将 100 个数分成 50 组: {1,51},{2,52},?,{50,100}。 在选出的 51 个数中,必有 2 个数属于同一组,这一组的 2 个数的差为 50。 (3)将 100 个数分成 5 组(一个数可以在不同的组内): 第一组:2 的倍数,即{2,4,?,100}; 第二组:3 的倍数,即{3,6,?,99}; 第三组:5 的倍数,即{5,10,?,100}; 第四组:7 的倍数,即{7,14,?,98}; 第五组:1 和大于 7 的质数即{1,11,13,?,97}。 第五组中有 22 个数,故选出的 51 个数至少有 29 个数在第一组到第四组中,根 据抽屉原理,总有 8 个数在第一组到第四组的某一组中,这 8 个数的最大公约数大 于 1。 例 2 求证:可以找到一个各位数字都是 4 的自然数,它是 1996 的倍数。 证明:因 1996÷4=499,故只需证明可以找到一个各位数字都是 1 的自然数, 它是 499 的倍数就可以了。

得到 500 个余数 r1,r2,?,r500。由于余数只能取 0,1,2,?,499 这 499 个值,所以根据抽屉原理,必有 2 个余数是相同的,这 2 个数的差就是 499 的倍数, 这个差的前若干位是 1,后若干位是 0:11?100?0,又 499 和 10 是互质的,故它 的前若干位由 1 组成的自然数是 499 的倍数,将它乘以 4,就得到一个各位数字都 是 4 的自然数,它是 1996 的倍数。 例 3 在一个礼堂中有 99 名学生,如果他们中的每个人都与其中的 66 人相识, 那么可能出现这种情况:他们中的任何 4 人中都一定有 2 人不相识(假定相识是互 相的)。 分析:注意到题中的说法“可能出现??”,说明题的结论并非是条件的必然 结果,而仅仅是一种可能性,因此只需要设法构造出一种情况使之出现题目中所说 的结论即可。
11

解:将礼堂中的 99 人记为 a1,a2,?,a99,将 99 人分为 3 组: (a1,a2,?,a33),(a34,a35,?,a66),(a67,a68,?,a99),将 3 组学生作为 3 个抽屉,分别记为 A,B,C,并约定 A 中的学生所认识的 66 人只在 B,C 中,同时,B,C 中的学生所认识的 66 人也只在 A,C 和 A,B 中。如果出现这 种局面,那么题目中所说情况就可能出现。 因为礼堂中任意 4 人可看做 4 个苹果,放入 A,B,C 三个抽屉中,必有 2 人在 同一抽屉,即必有 2 人来自同一组,那么他们认识的人只在另 2 组中,因此他们两 人不相识。

例 4 如右图,分别标有数字 1,2,?,8 的滚珠两组,放在内外两个圆环上, 开始时相对的滚珠所标数字都不相同。当两个圆环按不同方向转动时,必有某一时 刻,内外两环中至少有两对数字相同的滚珠相对。 分析:此题中没有直接提供我们用以构造抽屉和苹果的数量关系,需要转换一 下看问题的角度。 解:内外两环对转可看成一环静止,只有一个环转动。一个环转动一周后,每 个滚珠都会有一次与标有相同数字的滚珠相对的局面出现,那么这种局面共要出现 8 次。将这 8 次局面看做苹果,再需构造出少于 8 个抽屉。 注意到一环每转动 45°角就有一次滚珠相对的局面出现,转动一周共有 8 次滚 珠相对的局面,而最初的 8 对滚珠所标数字都不相同,所以数字相同的滚珠相对的 情况只出现在以后的 7 次转动中,将 7 次转动看做 7 个抽屉,8 次相同数字滚珠相 对的局面看做 8 个苹果,则至少有 2 次数字相对的局面出现在同一次转动中,即必 有某一时刻,内外两环中至少有两对数字相同的滚珠相对。 例 5 有一个生产天平上用的铁盘的车间,由于工艺上的原因,只能控制盘的重 量在指定的 20 克到 20.1 克之间。现在需要重量相差不超过 0.005 克的两只铁盘来 装配一架天平,问:最少要生产多少个盘子,才能保证一定能从中挑出符合要求的 两只盘子? 解:把 20~20.1 克之间的盘子依重量分成 20 组: 第 1 组:从 20.000 克到 20.005 克; 第 2 组:从 20.005 克到 20.010 克;

12

?? 第 20 组:从 20.095 克到 20.100 克。 这样,只要有 21 个盘子,就一定可以从中找到两个盘子属于同一组,这 2 个盘 子就符合要求。 例 6 在圆周上放着 100 个筹码,其中有 41 个红的和 59 个蓝的。那么总可以找 到两个红筹码,在它们之间刚好放有 19 个筹码,为什么? 分析:此题需要研究“红筹码”的放置情况,因而涉及到“苹果”的具体放置 方法, 由此我们可以在构造抽屉时, 使每个抽屉中的相邻 “苹果” 之间有 19 个筹码。 解:依顺时针方向将筹码依次编上号码:1,2,?,100。然后依照以下规律将 100 个筹码分为 20 组: (1,21,41,61,81); (2,22,42,62,82); ?? (20,40,60,80,100)。 将 41 个红筹码看做苹果,放入以上 20 个抽屉中,因为 41=2×20+1,所以至 少有一个抽屉中有 2+1=3(个)苹果,也就是说必有一组 5 个筹码中有 3 个红色筹 码,而每组的 5 个筹码在圆周上可看做两两等距,且每 2 个相邻筹码之间都有 19 个筹码,那么 3 个红色筹码中必有 2 个相邻(这将在下一个内容——第二抽屉原理 中说明),即有 2 个红色筹码之间有 19 个筹码。 下面我们来考虑另外一种情况:若把 5 个苹果放到 6 个抽屉中,则必然有一个 抽屉空着。这种情况一般可以表述为: 第二抽屉原理: (mn-1) 把 个物体放入 n 个抽屉, 其中必有一个抽屉中至多有 (m-1) 个物体。 例 7 在例 6 中留有一个疑问,现改述如下:在圆周上放有 5 个筹码,其中有 3 个是同色的,那么这 3 个同色的筹码必有 2 个相邻。 分析:将这个问题加以转化:

13

如右图,将同色的 3 个筹码 A,B,C 置于圆周上,看是否能用另外 2 个筹码将 其隔开。 解:如图,将同色的 3 个筹码放置在圆周上,将每 2 个筹码之间的间隔看做抽 屉,将其余 2 个筹码看做苹果,将 2 个苹果放入 3 个抽屉中,则必有 1 个抽屉中没 有苹果,即有 2 个同色筹码之间没有其它筹码,那么这 2 个筹码必相邻。 例 8 甲、乙二人为一个正方形的 12 条棱涂红和绿 2 种颜色。首先,甲任选 3 条棱并把它们涂上红色;然后,乙任选另外 3 条棱并涂上绿色;接着甲将剩下的 6 条棱都涂上红色。问:甲是否一定能将某一面的 4 条棱全部涂上红色? 解:不能。 如右图将 12 条棱分成四组:

第一组:{A1B1,B2B3,A3A4}, 第二组:{A2B2,B3B4,A4A1}, 第三组:{A3B3,B4B1,A1A2}, 第四组:{A4B4,B1B2,A2A3}。 无论甲第一次将哪 3 条棱涂红,由抽屉原理知四组中必有一组的 3 条棱全未涂 红,而乙只要将这组中的 3 条棱涂绿,甲就无法将某一面的 4 条棱全部涂红了。 下面我们讨论抽屉原理的一个变形——平均值原理。 我们知道 n 个数 a1,a2,?,an 的和与 n 的商是 a1,a2,?,an 这 n 个数的 平均值。 平均值原理:如果 n 个数的平均值为 a,那么其中至少有一个数不大于 a,也至少 有一个不小于 a。 例 9 圆周上有 2000 个点,在其上任意地标上 0,1,2,?,1999(每一点只标 一个数,不同的点标上不同的数)。求证:必然存在一点,与它紧相邻的两个点和 这点上所标的三个数之和不小于 2999。

14

解:设圆周上各点的值依次是 a1,a2,?,a2000,则其和 a1+a2+?+a2000=0+1+2+?+1999=1999000。 下面考虑一切相邻三数组之和: (a1+a2+a3)+(a2+a3+a4)+?+(a1998+a1999+a2000)+(a1999+ a2000+a1)+(a2000+a1+a2) =3(a1+a2+?+a2000) =3×1999000。

这 2000 组和中必至少有一组和大于或等于 但因每一个和都是整数, 故有一组相邻三数之和不小于 2999, 亦即存在一个点, 与它紧相邻的两点和这点上所标的三数之和不小于 2999。 例 10 一家旅馆有 90 个房间,住有 100 名旅客,如果每次都恰有 90 名旅客同 时回来,那么至少要准备多少把钥匙分给这 100 名旅客,才能使得每次客人回来时, 每个客人都能用自己分到的钥匙打开一个房门住进去,并且避免发生两人同时住进 一个房间? 解:如果钥匙数小于 990,那么 90 个房间中至少有一个房间的钥匙数少

房间就打不开,因此 90 个人就无法按题述的条件住下来。 另一方面,990 把钥匙已经足够了,这只要将 90 把不同的钥匙分给 90 个人, 而其余的 10 名旅客,每人各 90 把钥匙(每个房间一把),那么任何 90 名旅客返回 时,都能按要求住进房间。 最后,我们要指出,解决某些较复杂的问题时,往往要多次反复地运用抽屉原 理,请看下面两道例题。 例 11 设有 4×28 的方格棋盘,将每一格涂上红、蓝、黄三种颜色中的任意一 种。试证明:无论怎样涂法,至少存在一个四角同色的长方形。 证明:我们先考察第一行中 28 个小方格涂色情况,用三种颜色涂 28 个小方格, 由抽屉原理知,至少有 10 个小方格是同色的,不妨设其为红色,还可设这 10 个小 方格就在第一行的前 10 列。 下面考察第二、三、四行中前面 10 个小方格可能出现的涂色情况。这有两种可 能:
15

(1)这三行中,至少有一行,其前面 10 个小方格中,至少有 2 个小方格是涂 有红色的,那么这 2 个小方格和第一行中与其对应的 2 个小方格,便是一个长方形 的四个角,这个长方形就是一个四角同是红色的长方形。 (2)这三行中每一行前面的 10 格中,都至多有一个红色的小方格,不妨设它 们分别出现在前三列中,那么其余的 3×7 个小方格便只能涂上黄、蓝两种颜色了。 我们先考虑这个 3×7 的长方形的第一行。根据抽屉原理,至少有 4 个小方格是 涂上同一颜色的,不妨设其为蓝色,且在第 1 至 4 列。 再考虑第二行的前四列,这时也有两种可能: (1)这 4 格中,至少有 2 格被涂上蓝色,那么这 2 个涂上蓝色的小方格和第一 行中与其对应的 2 个小方格便是一个长方形的四个角,这个长方形四角同是蓝色。 (2)这 4 格中,至多有 1 格被涂上蓝色,那么,至少有 3 格被涂上黄色。不妨 设这 3 个小方格就在第二行的前面 3 格。 下面继续考虑第三行前面 3 格的情况。用蓝、黄两色涂 3 个小方格,由抽屉原 理知,至少有 2 个方格是同色的,无论是同为蓝色或是同为黄色,都可以得到一个 四角同色的长方形。 总之,对于各种可能的情况,都能找到一个四角同色的长方形。 例 12 试卷上共有 4 道选择题,每题有 3 个可供选择的答案。一群学生参加考 试,结果是对于其中任何 3 人,都有一道题目的答案互不相同。问:参加考试的学 生最多有多少人? 解:设每题的三个选择分别为 a,b,c。 (1)若参加考试的学生有 10 人,则由第二抽屉原理知,第一题答案分别为 a, b,c 的三组学生中,必有一组不超过 3 人。去掉这组学生,在余下的学生中,定有 7 人对第一题的答案只有两种。对于这 7 人关于第二题应用第二抽屉原理知,其中 必可选出 5 人,他们关于第二题的答案只有两种可能。对于这 5 人关于第三题应用 第二抽屉原理知,可以选出 4 人,他们关于第三题的答案只有两种可能。最后,对 于这 4 人关于第四题应用第二抽屉原理知,必可选出 3 人,他们关于第四题的答案 也只有两种。于是,对于这 3 人来说,没有一道题目的答案是互不相同的,这不符 合题目的要求。可见,所求的最多人数不超过 9 人。 另一方面,若 9 个人的答案如下表所示,则每 3 人都至少有一个问题的答案互 不相同。

16

所以,所求的最多人数为 9 人。 练习 13 1.六(1)班有 49 名学生。数学王老师了解到在期中考试中该班英文成绩除 3 人外均在 86 分以上后就说:“我可以断定,本班同学至少有 4 人成绩相同。”请问 王老师说得对吗?为什么? 2.现有 64 只乒乓球,18 个乒乓球盒,每个盒子里最多可以放 6 只乒乓球,至 少有几个乒乓球盒子里的乒乓球数目相同? 3.某校初二年级学生身高的厘米数都为整数, 且都不大于 160 厘米, 不小于 150 厘米。问:在至少多少个初二学生中一定能有 4 个人身高相同? 4.从 1,2,?,100 这 100 个数中任意选出 51 个数,证明在这 51 个数中,一 定: (1)有两个数的和为 101; (2)有一个数是另一个数的倍数; (3)有一个数或若干个数的和是 51 的倍数。 5.在 3×7 的方格表中,有 11 个白格,证明 (1)若仅含一个白格的列只有 3 列,则在其余的 4 列中每列都恰有两个白格; (2)只有一个白格的列只有 3 列。 6.某个委员会开了 40 次会议,每次会议有 10 人出席。已知任何两个委员不会 同时开两次或更多的会议。问:这个委员会的人数能够多于 60 人吗?为什么? 7.一个车间有一条生产流水线,由 5 台机器组成,只有每台机器都开动时,这 条流水线才能工作。总共有 8 个工人在这条流水线上工作。在每一个工作日内,这 些工人中只有 5 名到场。为了保证生产,要对这 8 名工人进行培训,每人学一种机

17

器的操作方法称为一轮。问:最少要进行多少轮培训,才能使任意 5 个工人上班而 流水线总能工作? 8.有 9 名数学家,每人至多能讲 3 种语言,每 3 人中至少有 2 人能通话。求证: 在这 9 名中至少有 3 名用同一种语言通话。

练习 13 1.对。解:因为 49-3=3×(100-86+1)+1,即 46=3×15+1,也就是说,把从 100 分至 86 分的 15 个分数当做抽屉,49-3=46(人)的成绩当做物体,根据第二抽屉原 理,至少有 4 人的分数在同一抽屉中,即成绩相同。 2.4 个。解:18 个乒乓球盒,每个盒子里至多可以放 6 只乒乓球。为使相同乒 乓球个数的盒子尽可能少, 可以这样放: 先把盒子分成 6 份, 每份有 18÷6=3 (只) , 分别在每一份的 3 个盒子中放入 1 只、2 只、3 只、4 只、5 只、6 只乒乓球,即 3 个盒子中放了 1 只乒乓球, 个盒中放了 2 只乒乓球??3 个盒子中放了 6 只乒乓球。 3 这样,18 个盒子中共放了乒乓球 (1+2+3+4+5+6)×3=63(只)。 把以上 6 种不同的放法当做抽屉,这样剩下 64-63=1(只)乒乓球不管放入哪 一个抽屉里的任何一个盒子里(除已放满 6 只乒乓球的抽屉外),都将使该盒子中 的乒乓球数增加 1 只,这时与比该抽屉每盒乒乓数多 1 的抽屉中的 3 个盒子里的乒 乓球数相等。例如剩下的 1 只乒乓球放进原来有 2 只乒乓球的一个盒子里,该盒乒 乓球就成了 3 只,再加上原来装有 3 只乒乓球的 3 个盒子,这样就有 4 个盒子里装 有 3 个乒乓球。所以至少有 4 个乒乓球盒里的乒乓球数目相同。 3.34 个。 解:把初二学生的身高厘米数作为抽屉,共有抽屉 160-150+1=11(个)。 根据抽屉原理,要保证有 4 个人身高相同,至少要有初二学生 3×11+1=34(个)。 4.证:(1)将 100 个数分成 50 组: {1,100},{2,99},?,{50,51}。
18

在选出的 51 个数中,必有两数属于同一组,这一组的两数之和为 101。 (2)将 100 个数分成 10 组: {1,2,4,8,16,32,64}, {3,6,12,24,48,96}, {5,10,20,40,80}, {7,14,28,56}, {9,18,36,72}, {11,22,44,88}, {13,26,52}, {15,30,60},?, {49,98}, {其余数}。 其中第 10 组中有 41 个数。在选出的 51 个数中,第 10 组的 41 个数全部选中, 还有 10 个数从前 9 组中选,必有两数属于同一组,这一组中的任意两个数,一个是 另一个的倍数。 (3)将选出的 51 个数排成一列: a1,a2,a3,?,a51。 考虑下面的 51 个和: a1,a1+a2,a1+a2+a3,?, a1+a2+a3+?+a51。 若这 51 个和中有一个是 51 的倍数,则结论显然成立;若这 51 个和中没有一个 是 51 的倍数,则将它们除以 51,余数只能是 1,2,?,50 中的一个,故必然有两 个的余数是相同的,这两个和的差是 51 的倍数,而这个差显然是这 51 个数(a1, a2, a3,?,a51)中的一个数或若干个数的和。 5.证:(1)在其余 4 列中如有一列含有 3 个白格,则剩下的 5 个白格要放入 3 列中, 3 列表格看做 3 个抽屉, 个白格看做 5 个苹果, 将 5 根据第二抽屉原理,(=2 5 ×3-1)个苹果放入 3 个抽屉,则必有 1 个抽屉至多只有(2-1)个苹果,即必有 1 列只含 1 个白格,也就是说除了原来 3 列只含一个白格外还有 1 列含 1 个白格,这 与题设只有 1 个白格的列只有 3 列矛盾。所以不会有 1 列有 3 个白格,当然也不能 再有 1 列只有 1 个白格。推知其余 4 列每列恰好有 2 个白格。 (2)假设只含 1 个白格的列有 2 列,那么剩下的 9 个白格要放入 5 列中,而 9=2×5-1,由第二抽屉原理知,必有 1 列至多只有 2-1=1(个)白格,与假设只有 2 列每列只 1 个白格矛盾。所以只有 1 个白格的列至少有 3 列。 6.能。

19

解:开会的“人次”有 40×10=400(人次)。设委员人数为 N,将“人次”看 做苹果,以委员人数作为抽屉。 若 N≤60,则由抽屉原理知至少有一个委员开了 7 次(或更多次)会。但由已 知条件知没有一个人与这位委员同开过两次(或更多次)的会,故他所参加的每一 次会的另外 9 个人是不相同的,从而至少有 7×9=63(个)委员,这与 N≤60 的假 定矛盾。所以,N 应大于 60。 7.20 轮。 解:如果培训的总轮数少于 20,那么在每一台机器上可进行工作的工人

果这 3 个工人某一天都没有到车间来,那么这台机器就不能开动,整个流水线就不 能工作。故培训的总轮数不能少于 20。 另一方面,只要进行 20 轮培训就够了。对 3 名工人进行全能性培训,训练他们 会开每一台机器;而对其余 5 名工人,每人只培训一轮,让他们每人能开动一台机 器。这个方案实施后,不论哪 5 名工人上班,流水线总能工作。 8.证:以平面上 9 个点 A1,A2,?,A9 表示 9 个数学家,如果两人能通话, 就把表示他们的两点联线,并涂上一种颜色(不同的语言涂上不同颜色)。此时有 两种情况: (1)9 点中有任意 2 点都有联线,并涂了相应的颜色。于是从某一点 A1 出发, 分别与 A2,A3,?,A9 联线,又据题意,每人至多能讲 3 种语言,因此 A1A2, A1A3,?,A1A9 中至多只能涂 3 种不同的颜色,由抽屉原理知,这 8 条线段中至 少有 2 条同色的线段。不妨设 A1A2 与 A1A3 是同色线段,因此 A1,A2,A3 这 3 点表示的 3 名数学家可用同一种语言通话。 (2)9 点中至少有 2 点不联线,不妨设是 A1 与 A2 不联线。由于每 3 人中至 少有两人能通话,因此从 A1 与 A2 出发至少有 7 条联线。再由抽屉原理知,其中必 有 4 条联线从 A1 或 A2 出发。不妨设从 A1 出发,又因 A1 至多能讲 3 种语言,所 以这 4 条联线中,至少有 2 条联线是同色的。若 A1A3 与 A1A4 同色,则 A1,A3, A4 这 3 点表示的 3 名数学家可用同一种语言通话。

20


推荐相关:

高中数学竞赛讲义第六讲 数列

高中数学竞赛讲义第六讲 数列_学科竞赛_高中教育_教育专区。高中数学竞赛辅导讲义...不等式恒成立等问题组合在一起,构思巧妙 错解分析 本题学生很容易求 f(n)的...


高中数学奥赛辅导 第六讲 集合与映射

高中数学奥赛辅导 第六讲 集合与映射_学科竞赛_高中教育_教育专区。数学奥赛辅导...175. 在许多问题中,计数对象的特征不明显或混乱复杂难以直接计数,这时可以通过...


数学奥赛辅导 第六讲 集合与映射

数学奥赛辅导 第九讲 组合... 数学奥赛辅导 第十...高中数学奥赛系列辅导资料... 暂无评价 6页 2财富...这些在与计数有关的数学竞赛问题 中应用极广,是...


=竞赛班第六讲+还原问题和巧填算符

=竞赛班第六讲+还原问题和巧填算符_学科竞赛_小学...某次数学竞赛,共 20 题,每做对一题得 5 分,做错...氧化还原反应竞赛讲义 37页 免费 第十二讲 巧填算...


第六讲 简单的推理

第六讲 简单的推理_学科竞赛_小学教育_教育专区。...下面我们要学习用简单推理解决一些实际问题。 例1 ...例3 二年级有三个班举行数学竞赛,分别从三个班中...


第六讲____四边形尖子班讲义

百度文库 教育专区 小学教育 学科竞赛上传文档文档...第六讲___四边形尖子班讲义 暂无评价|0人阅读|0...例 2.(2009 临沂)数学课上,张老师出示了问题:...


数学奥赛辅导 第八讲 组合计数

关键词:数学奥赛学习资料 1/2 同系列文档 数学奥赛辅导 第一讲 奇数... 数学...高中数学奥赛辅导教材第一... 64页 免费 高中数学奥赛辅导教材第六... 8页 ...


高中数学竞赛 第24讲 三角不等式教案

高中数学竞赛辅导第六讲不... 9页 免费 高中数学竞赛辅导讲义第九... 暂无评价...如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处...


第六讲 相遇问题

第六讲 相遇问题_五年级数学_数学_小学教育_教育专区。教育中心 让优秀成为习惯...某校参加六一杯小学数学竞赛,原定考场若干个。如果增加2个考场,每个考场正好坐...


第六讲:添加辅助线的技巧(春季A班)

辅导资料:全等三角形问... 8页 1下载券第...第六讲:添加辅助线的技巧(春季 A 班) 添加辅助线...竞赛介绍: 1981 年,中国数学会开始举办“全国高中...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com