当前位置:首页 >> 学科竞赛 >>

抽屉原理与高中数学竞赛






本论文首先讨论了抽屉原理的一般含义和它的两种推广形式;其次给出了抽屉原理在 整除问题、面积问题、染色问题、六人集会问题以及生日问题等高中数学竞赛问题中的应 用。 关键词:抽屉原理;染色问题;集会问题;生日问题

-i-

-ii-

ABSTRACT
T

his thesis first discuss the meaning of Drawer Principle and its’ two kinds of developing types; and then the practical application of this principle on five different kinds of problems, including the problem of dividing exactly, the problem of dimension, the problem of dyeing, the problem of six persons’ assembly and the problem of birthday, and other problems appeared in the High School Mathematical Contest were presented. Keywords: Drawer principle;Dyeing problem;Assembly problem;Birthday problem

-iii-

-iv-

湖南科技大学本科生毕业设计(论文)


第一章 第二章
2.1 2.2 2.3



前言……………………………………………………………………… 1 抽屉原理概念与基本形式 抽屉原理 概念与基本形式 ………………………………………… 3
抽屉原理的一般含义…………………………………………………………3 抽屉原理的基本形式……………………………………………………… 抽屉原理推广到一般情形的两种推广形式……………………………… 2.3.1 2.3.2 3 3

抽屉原理 1……………………………………………………………4 抽屉原理 2……………………………………………………………5

第三章
3.1 3.2 3.3 3.4 3.5 3.6

抽屉原理在高中数学竞赛中的应用 抽屉原理在高中数学竞赛中的应用…………………………………7 高中
整除问题……………………………………………………………7 面积问题……………………………………………………………8 染色问题…………… ………………………………… …………… 10 六人集会问题…………………………………………………………… 生日问题………………………………………………………………… 抽屉原理解题步骤小结……………………………………………… 12 14 15 17

第四章

结论……………………………………………………………………

参考文献…………………………………………………………………………… 19 致谢…………………………………………………………………………………
21

湖南科技大学本科生毕业设计(论文)

第一章

前言

数学竞赛,是一种智力的比赛.数学竞赛试题,大多出自名家之手,并且经过巧妙构 思、精心制作编撰出来的.因此,数学竞赛中试题中有许多令人击掌称赞的好题,求解或 求证一道数学竞赛题,往往既不需要冗长的推理论证,也不需要繁琐的演绎计算,但需要 “题感”,才能在“踏破铁鞋无觅处”时,有“得来全部费功夫”的顿悟。那些数学竞赛 优胜者就具备在考场上的顿悟,能立即抓住题目的本质联系,从而使问题迎刃而解,但 是,“题感”的到来,不仅需要具备一定的知识储备,而且需要具备一定的知识储备,而 且需要形象思维和逻辑思维能力的支持,对于数学竞赛的重要组成部分——抽屉原理—— 而言,则尤其需要“题感”. 抽屉原理是组合数学中的一部分,近几十年来,由于计算机科学的发展和日益增多的 组合问题的出现,丰富和发展了组合理论,这直接影响到数学竞赛的命题工作,求解竞赛 中出现的初等组合问题并不需要复杂的知识,然而在趣味命题的陈述下包含了高超的解题 技巧,无论是从智力训练的角度,还是从竞赛准备的角度考虑,理解和专研这些问题都是 十分有意义的.这些试题不少来源于前沿数学最新研究成果的简化,许多体现着精深的数 学内容、独到的数学思想和方法、精美巧妙的构思和趣味盎然的表述,由于组合知识的灵 活、多变以及高度的技巧性,可以说,一届数学竞赛题的“好坏”,有 70%取决与组合题 目 . 本文是在分析了历届高中数学竞赛的竞赛上,注意到抽屉原理是每次竞赛必考的,主 要讨论了抽屉原理在高中数学竞赛中的应用.有的学生对组合题很头疼.如果参赛者有一定 的知识储备,见的题目多样,再做题时就会有很好的心理素质,发现“题眼”、找到“题 感”,赛题迎刃而解.
[1]

-1-

湖南科技大学本科生毕业设计(论文)

-2-

湖南科技大学本科生毕业设计(论文)

第二章 抽屉原理简述
在数学问题中有一类与“存在性”有关的问题,例如:“13 个人中至少有两个人出 生在相同月份”;“某校 400 名学生中,一定存在两名学生,他们在同一天过生日”; “2003 个人任意分成 200 个小组,一定存在一组,其成员数不少于 11”;“把[0,1]内 的全部有理数放到 100 个集合中,一定存在一个集合,它里面有无限多个有理数”.这类 存在性问题中,“存在”的含义是“至少有一个”.在解决这类问题时,只要求指明存 在,一般并不需要指出哪一个,也不需要确定通过什么方式把这个存在的东西找出来.这 类问题相对来说涉及到的运算较少,依据的理论也不复杂,我们把这些理论称之为“抽屉 原理”.

2.1 抽屉原理的一般含义
抽屉原理有离散情形和连续情形两种.离散情形下的抽屉原理也称鸽巢原理,迪利克 雷建立的“迪力克雷抽样法”指出:“如果在 n 个抽样中,存在 n+1 个事件,那么至少在 一个抽样中包含两个或两个以上的事件.”这是首次以明确的语言来表述的抽屉原理.因 此,抽屉原理也称为迪利克雷原理. 离散情形的抽屉原理有两种形式,一种是有限形式,一种是无限形式.

2.2 抽屉原理的基本形式
定理 1[2] 证明 如果把 n + 1 个元素分成 n 个集合,那么不管怎么分,都存在一个集合,其 中至少有两个元素. 用反证法,若不存在至少有两个元素的集合,则每个集合至多 1 个元素,从 而 n 个集合至多有 n 个元素,这与共有 n + 1 个元素矛盾,故命题成立. 在定理 1 的叙述中,可以把“元素”改为“物件”,把“集合”改成“抽屉”,抽屉 原理正是由此得名. 同样,可以把“元素”改成“鸽子”,把“分成 n 个集合”改成“飞进 n 个鸽巢 中”,“鸽巢原理”由此得名.

2.3 抽屉原理推广到一般情形的两种推广形式
抽屉原理推广到一般情形的两种推广形式主要分为两种:有限形式的抽屉原理与无限 形式的抽屉原理.

-3-

湖南科技大学本科生毕业设计(论文)

2.3.1 抽屉原理 1 1(有限形式 有限形式) 抽屉原理 1(有限形式)[2] 证明 设 k 和 n 都是任意的正整数,若至少有 kn + 1 只鸽子分配在

n 个鸽巢,则至少存在一个鸽巢中有至少 k + 1 只鸽子.

用反证法.如果每个鸽巢中,至多有 k 只鸽子,那么放入 n 个鸽巢中的鸽子的

总数至多为 kn 只, kn < kn + 1 ,这与已知至少有 kn + 1 只鸽子相矛盾,故必有一个鸽巢内的 鸽子数不少于 k + 1 只. 推论 1[2]

? m ?1? m 只鸽子, n 个巢,则至少有个有一个鸽巢里不少于 ? + 1 只鸽子。其 ? n ? ?

中 ? a ? 为高斯函数. ? ? 证明
? m ? 1? 用反证法.如果每个鸽巢至多有 ? 只鸽子,那么放入 n 个鸽巢中的鸽子的 ? n ? ?

? m ? 1? ? m ?1? 总数至多为 n ? ? ≤ n ? n ? ≤ m ? 1 ,这与共有 m 个矛盾,故必有一个鸽巢内的鸽子数 ? n ? ? ? ? m ? 1? 不少于 ? + 1 只. ? n ? ?

推 论 2[3] 球. 推论 3[3]

若 取 n ( m ? 1) + 1 个 球 放 进 n 个 盒 子 , 则 至 少 有 1 个 盒 子 有 m 个
m1 + m2 + ... + mn > r ? 1 ,则 m1 , m2 ,..., mn n

若 m1 , m2 ,..., mn 是 n 个正整数,而且

中至少有 1 个数不小于 r . 证明 用反证法。如果 mi ≤ r ? 1, ( i = 1, 2,..., n ) , 那么

m1 + m2 + ... + mn n ( r ? 1) ≤ = r ?1, n n
这与已知 推论 4[4]

m1 + m2 + ... + mn > r ? 1 相矛盾,故 m1 , m2 ,..., mn 中至少有 1 个数不小于 r . n
?n? 把 n 个元素划分成 k 个集合,则必有一个集合中元素的个数 ≥ ? ? ,也必有 ?k ?

?n? 一个集合中元素的个数 ≤ ? ? . ?k ?

证明 用反证法.
-4-

湖南科技大学本科生毕业设计(论文)

(1)

?n? 如 果 集 合 中 的 元 素 个 数 ≤ ? ? ?1 , 那 么 k 个 集 合 中 总 的 元 素 的 个 数 ?k ?

??n? ? ≤ k ? ? ? ? 1? < n ,这与题目已知共有 n 个元素相矛盾,故必有一个集合中元素的个数 ??k ? ?

?n? ≥ ? ?; ?k ?

( 2)

?n? 如 果 集 合 中 的 元 素 个 数 ≥ ? ? +1 , 那 么 k 个 集 合 中 总 的 元 素 的 个 数 ?k ?

??n? ? ≥ k ? ? ? + 1? > n ,这与题目已知共有 n 个元素相矛盾,故必有一个集合中的元素的个数 ??k ? ? ?n? ≤ ? ?; ?k ? ?n? 综上可得,必有一个集合中元素的个数 ≥ ? ? ,也必有一个集合中的元素的个数 ?k ? ?n? ≤ ? ?. ?k ?
推论 5[4] 设 q + q + ... + + q ? n + 1 只鸽子,有标号分别为 1, 2,3,..., n 的鸽巢,则存在 1 2 n 至少一个标号为 j (1 ≤ j ≤ n ) 的鸽巢中至少有 q j 只鸽子, j = 1, 2,..., n . 证明 若对所有的 j (1 ≤ j ≤ n ) ,使得第 j 个鸽巢中至多有 q j ? 1 只鸽子,则 n 个鸽巢中 至多有: ( q1 ? 1) + ( q2 ? 1) + ... + ( qn ? 1) = ∑ q j ? n 个物品,与题设有
j =1 n

q1 + q2 + ... + + qn ? n + 1 = ∑ q j ? n + 1
j =1

n

相矛盾,故定理成立. 2.3.2 抽屉原理 2 无限形式) 抽屉原理 2(无限形式)[2] 无穷多个球. 证明 反证法.假设不存在放进无穷多个球的抽屉,即每个抽屉都放进了有限多个 球,又一直抽屉是有限多个,则球数也为有限多个。与已知相矛盾. 无穷多个球放到有限多只抽屉中,一定有一直抽屉放进了

-5-

湖南科技大学本科生毕业设计(论文)

-6-

湖南科技大学本科生毕业设计(论文)

第三章 抽屉原理在高中数学竞赛中的应用 抽屉原理在高中数学竞赛中的应用 高中数学竞赛中的应
在数学问题中有一类与“存在性”有关的问题:例如“某校 400 名学生中,一定存在 两名学生,他们同一天过生日”;“把 [0,1] 内的全部有理数放到 200 个集合中,一定存在 一个集合,它里边有无限多个有理数”,这类存在性问题中,“存在”的含义是“至少有 一个”.在解决这类问题时,只要求指明存在,一般并不需要指出哪一个,也不需要确定 通过什么方式把这个存在的东西找出来.这类问题相对来说涉及到的运算较少,依据理论 也不复杂,用抽屉原理往往是解决这类问题的一种有效途径.下面就抽屉原理在往届的数 学竞赛中出现的相关例题,把它分为五个方面,通过对题目的分析、解答来体会抽屉原理 的应用. 下面主要讲解抽屉原理在高中数学竞赛中五种问题的运用,其中包括:整除问题、面 积问题、染色问题、六人集会问题以及生日问题.

3.1 整除问题
例1 证明 种情况: 1. 某一类至少包含三个数; 任取 5 个整数,必然能够从中选出三个,使它们的和能够被 3 整除. 任意给一个整数,它被 3 整除,余数可能为 0,1,2,我们把被 3 除余数为

0,1,2 的整数各归入类 r0 , r1 , r2 。至少有一类包含所给 5 个数中的至少两个.因此可能出现两

2. 某两类各含两个数,第三类包含一个数.
若是第一种情况,就在至少包含三个数的那一类中任取三个数,其和一定能被 3 整 除; 若是第二种情况,在三类各取一个数,其和也能被 3 整除. 综上所述,原命题成立. 例 2[1] 分析 在任意给出的 100 个整数中,都可以找出若干个数来(可以是一个数),它 本题也似乎是茫无头绪,无从下手,其关键何在?仔细审题,它们的“和”能 们的和可被 100 整除. “被 100 整除”应是做文章的地方.如果把这 100 个数排成一个数列,用 S m 记其前 m 项的 和,则其可构造 S1 , S 2 ,..., S100 共 100 个"和"数.讨论这些“和数”被 100 除所得的余数.注 意到 S1 , S 2 ,..., S100 共有 100 个数,一个数被 100 除所得的余数有 0,1, 2,...,99 共 100 种可能 性。“苹果”数与“抽屉”数一样多,如何排除“故障”?

-7-

湖南科技大学本科生毕业设计(论文)

证明

设 已 知 的整 数为 a1 , a2 ,..., a100 考 察 数 列 a1 , a2 ,..., a100 . 的 前 n 项 和 构 成 的 数 列

S1 , S 2 ,..., S100 .

如果 S1 , S 2 ,..., S100 中有某个数可被 100 整除,则命题得证.否则,即 S1 , S 2 ,..., S100 均不能 被 100 整除,这样,它们被 100 除后余数必是 {1, 2,...,99} 中的元素.由抽屉原理 I 知,
S1 , S 2 ,..., S100 中 必 有 两 个 数 , 它 们 被 100 除 后 具 有 相 同 的 余 数 . 不 妨 设 这 两 个 数 为

Si , S j ( i < j ) ,则 100 S j ? Si ,即 100 ( ai +1 , ai + 2 ,..., a j ) .命题得证.
说明 有时候直接对所给对象作某种划分,是很难构造出恰当的抽屉的.这时候,我 们需要对所给对象先作一些变换,然后对变换得到的对象进行分类,就可以构造出恰当的 抽屉.本题直接对 {an } 进行分类是很难奏效的.但由 {an } 构造出 {Sn } 后,再对 {Sn } 进行分类 就容易得多. 另外,对 {Sn } 按模 100 的剩余类划分时,只能分成 100 个集合,而 {Sn } 只有 100 项, 似乎不能应用抽屉原则.但注意到余数为 0 的类恰使结论成立,于是通过分别情况讨论 后,就可去掉余数为 0 的类,从而转化为 100 个数分配在剩下的 99 个类中. 最后,本例的结论及证明可以推广到一般情形(而且有加强的环节): 在任意给定的 n 个整数中,都可以找出若干个数来(可以是一个数),它们的和可被

n 整除,而且,在任意给定的排定顺序的 n 个整数中,都可以找出若干个连续的项(可以
是一项),它们的和可被 n 整除.

3.2 3.2 面积问题
例 1[5] 边长为 1 的正方形中,任意放入 9 个点,求证这 9 个点中任取 3 个点组成的 三角形中,至少有一个的面积不超过 1 8 .
1 解 将边长为 1 的正方形等分成边长为 的四个小正方形,视这四个正方形为抽屉, 2

9 个点任意放入这四个正方形中,据形式 2,必有三点落入同一个正方形内.现特别取出 这个正方形来加以讨论. 把落在这个正方形中的三点记为 D 、 E 、 F .通过这三点中的任意一点(如 E)作平 行线,

-8-

湖南科技大学本科生毕业设计(论文)

E

D

G F

图1

由图 1 可知 S△DEF=S△DEG+S△EFG 1 1 1 1 ?1 ? ≤ × ×h + × ×? ? h? 2 2 2 2 ?2 ? h 1 h = + ? 4 8 4 1 = . 8 在边长为 1 的正方形内任意放入九个点,求证:存在三个点,以这三个点为

例 2[6]

1 顶点的三角形的面积不超过 (1963 年北京市数学竞赛题). 8

A1 A2 A3 A4 图2

h C A A' 1/4

B
图3

-9-

湖南科技大学本科生毕业设计(论文)



如图 2,四等分正方形,得到 A1 , A2 , A3 , A4 四个矩形.在正方形内任意放入九个

?9? 点,则至少有一个矩形 Ai 内存在 ? ? + 1 = 3 个或 3 个以上的点,设 ?4?

三点为 A, B, C ,具体考察 A1 (如图 3 所示),过 A, B, C 三点分别作矩形长边的平行线,

1? ? 过 A 点的平行线交 BC 于 A′ 点, A 点到矩形长边的距离为 h ? 0 ≤ h ≤ ? ,则△ABC 的面积 4? ? 1 1 ?1 ? 1 1 1 S?ABC = S?AA′C +S?AA′B ≤ × 1× h + × 1× ? ? h ? = × = 2 2 ?4 ? 2 4 8
说明 把正方形分成四个区域,可以得出“至少有一个区域内有 3 个点”的结论,这 就为确定三角形面积的取值范围打下了基础.本题构造“抽屉”的办法不是唯一的,还可 以将正方形等分成边长为
1 的四个小正方形等.但是如将正方形等分成四个全等的小三角 2

形却是不可行的(想一想为什么?).所以适当地构造“抽屉”,正是应用抽屉原则解决 问题的关键所在.

3.3

染色问题
例 1[7] 把 1 到 10 的自然数摆成一个圆圈,证明一定存在三个相邻的数,它们的和数

大于 17. 证明 设 a1 , a2 , a3 ,..., a9 , a10 分别代表不超过 10 的十个自然数,它们围成一个圈,它们 三个相邻的数的组成是

( a1 , a2 , a3 ) , ( a2 , a3 , a4 ) , ( a3 , a4 , a5 ) ,..., ( a9 .a10 , a1 ) , ( a10 , a1 , a2 )
共十组,现在把他们看成是十个抽屉,每个抽屉的物体数是

a1 + a2 + a3 , a2 + a3 + a4 , a3 + a4 + a5 ,..., a9 + a10 + a1 , a10 + a1 + a2 ,
由于

(a1 + a2 + a3 ) + (a2 + a3 + a4 ) + ... + (a9 + a10 + a1 ) + (a10 + a1 + a2 )
= 3 ( a1 + a2 + ...a9 + a10 ) = 3 × (1 + 2 + ... + 9 + 10 ) = 3×

(10 + 1) ×10
2

= 165 = 16 ×10 + 5 根据推论 2,至少有一个括号内的三数和不少于 17,即至少有三个相邻的数的和不少 于 17.
- 10 -

湖南科技大学本科生毕业设计(论文)

例 2[6] 同色.

(1995 年全国高中数学联赛试题)将平面上每个点以红蓝两色之一着色,证

明:存在这样的两个相似三角形,它们的相似比为 1995,并且每一个三角形的三个顶点

B3 B2 B4 B1

A3 A4

A2 A1

A9 A8 A5 A6 A7 B8 B5 B6 图4 B7 B9

证明 如图 4,作两个半径分别为 1 和 1995 的同心圆. 在内圆上任取 9 个点,必有 5 点同色,记为 A1 , A2 , A3 , A4 , A5 .连半径 OA1 交大圆于

Bi ( i = 1, 2,3, 4,5, 6, 7,8,9 ) ,对 B1 , B2 , B3 , B4 , B5 必有 3 点同色,记为 Bi , B j , Bk 则△ Bi B j Bk 与△
Ai A j Ak 为三项点同色的位似三角形,位似比等于 1995,满足题设条件.

说明

这里连续用了两次抽屉原理(以染色作抽屉).也可以一开始就取位似比为

1995 的 9 个位似点组 ( Ai , Bi )( i = 1, 2,3, 4,5, 6, 7,8,9 ) ,对 4 个抽屉(红,红),(红, 蓝),(蓝,红),(蓝,蓝)应用抽屉原理,得出必有 3 个位似点属于同一抽屉,从题 目的证明过程中可以看出,位似比 1995 可以改换成另外一个任意的正整数、正实数.当 然,不用同心圆也可证得,如在平面上取任三点都不共线的 9 点,由抽屉原理必有 5 点同 色,设为 A 、 B 、 C 、 D 、E;以 A 为位似中心(如图 5),以 1995 为位似比作 ABCDE 的 位似形 A′B′C ′D′E ′ ,则 5 点 A 、 B′ 、 C ′ 、 D′ 、 E ′ 中必有 3 点同色,设为 B′ 、 D′ 、 E ′ , 则即为所求.

- 11 -

湖南科技大学本科生毕业设计(论文)



C4


C3

B CE B' A 图5 DE

B A

EE



C1 图6

C2

更一般地可以证明,在这个二染色的平面上存在无数个内角为 30° , 60° , 90° 的直角 三角形三顶点同色:任取 a ∈ R + ,以 a 为边作等边三角形,则必有两点同色,记为 A, B 同 红色,以 AB 为直径作一圆,再作圆内接正六边形 AC1C2 BC3C4 (如图 6),当 C1 中有红点时 △ AC1B 即为所求;当 C1 中无红点即 C1 全为蓝色时, Rt △ C1C2C3 即为所求。再由 a 的任意 性知,这样的三角形有无数个. 更进一步还可得到:对任何 a ∈ R + ,可得到两个相似比为 a 的顶点同色的相似三角形. 对于多染色的情形,还可以得出多个相似三角形的结论:用红、黄、蓝三种颜色对平面上 的点染色,对任意的 a, b ∈ R + ,必存在三个三角形,它们彼此相似,相似比为 1: a : b ,且 每个三角形的三顶点同色.

3.4 六人集会问题
例 1 任意六个人中至少存在三个人或是互相认识,或者是互相不认识. 证明 在这六个人中任意取定一个人 x ,则其余五个人可以分为两类: A = {与 x 认识 的人}, B ={与 x 不认识的人}.根据抽屉原理, A 和 B 至少有 1 个集合有 3 个人.不妨设此 集合为 A ,且对于集合 A 中的 3 个人 a, b, c 来说,若他们彼此不认识,则问题已得证明, 否则有两个人互相认识,不妨设这两个人是 a, b ,则 x, a, b 三个人互相认识. 若集合 B 中至少有三个人,用同样的方法也可得到证明. 例 2[8] (第 6 届国际中学生数学奥林匹克试题)17 名科学家中每两名科学家都和其 他科学家通信,在他们通信时,只讨论三个题目,而且任意两名科学家通信时只讨论一个 题目,证明:其中至少有三名科学家,他们相互通信时讨论的是同一个题目.
- 12 -

湖南科技大学本科生毕业设计(论文)

证明 视 17 个科学家为 17 个点,每两个点之间连一条线表示这两个科学家在讨论同 一个问题,如果讨论第一个问题则在相应两点连红线,如果讨论第 2 个问题则在相应两点 连条黄线,如果讨论第 3 个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转 化为找到一个三边同颜色的三角形. 考虑科学家 A ,他要与另外的 16 位科学家每人通信讨论一个问题,相应于从 A 出发 引出 16 条线段,将它们染成 3 种颜色,而 16 = 3 × 5 + 1 ,因而必有 6 = 5 + 1 条同色,不妨记 为 AB1 , AB2 , AB3 , AB4 , AB5 , AB6 同红色,若 Bi ( i = 1, 2,3, 4,5, 6 ) 之间有红线,则出现红色三角 线,命题已成立;否则 B1 , B2 , B3 , B4 , B5 , B6 之间的连线只染有黄蓝两色. 考 虑 从 B1 引 出 的 5 条 线 , B1 B2 , B1 B3 , B1B4 , B1B5 , B1 B6 , 用 两 种 颜 色 染 色 , 因 为
5 = 2 × 2 + 1 ,故必有 3 = 2 + 1 条线段同色,假设为黄色,并记它们为 B1 B2 , B1 B3 , B1 B4 .这时若

B2 , B3 , B4 之间有黄线,则有黄色三角形,命题也成立,若 B2 , B3 , B4 ,之间无黄线,则 △ B2 B3 B4 必为蓝色三角形,命题仍然成立. 说明(1) 说明 (2) 本题源于一个古典问题--世界上任意 6 个人中必有 3 人互相认识,或互相 不认识(美国普特南数学竞赛题). 将互相认识用红色表示,将互相不认识用蓝色表示,这样题目将化为一个染色 问题,成为一个图论问题:空间六个点,任何三点不共线,四点不共面,每两点之间连线 都涂上红色或蓝色.求证:存在三点,它们所成的三角形三边同色. (3) 问题(2)可以往两个方向推广:其一是颜色的种数,其二是点数. 本例便是方向一的进展,其证明已知上述.如果继续沿此方向前进,可有下题: 在 66 个科学家中,每个科学家都和其他科学家通信,在他们的通信中仅仅讨论四个 题目,而任何两个科学家之间仅仅讨论一个题目.证明至少有三个科学家,他们互相之间 讨论同一个题目. (4)回顾上面证明过程,对于 17 点染 3 色问题可归结为 6 点染 2 色问题,又可归结 为 3 点染一色问题. 反过来,我们可以继续推广.从以上 ( 3,1) → ( 6, 2 ) → (17,3) 的过程,易发现

6 = ( 3 ? 1) × 2 + 2,17 = ( 6 ? 1) × 3 + 2, 66 = (17 ? 1) × 4 + 2 ,
同理可得 ( 66 ? 1) × 5 + 2 = 327, ( 327 ? 1) × 6 + 2 = 1958... 记为 r1 = 3, r2 = 6, r3 = 17, r4 = 66, r5 = 327, r6 = 1958,... . 我们可以得到递推关系式 rn = n ( rn ?1 ? 1) + 2, n = 2,3, 4,... .

- 13 -

湖南科技大学本科生毕业设计(论文)

这样就可以构造出 327 点染 5 色问题,1958 点染 6 色问题,都必出现一个同色三角 形.

3.5 生日问题 3.5
例 1[9] 从 1 ? 100 的自然数中,任意的取出 51 个数,证明其中一定有两个数,它们中 的一个是另一个的整数倍. 分析 本题似乎茫无头绪,从何入手?其关键何在?其实就在“两个数”,其中一个 是另一个的整数倍.我们要构造“抽屉”,使得每个抽屉里任取两个数,都有一个是另一 个的整数倍,这只有把公比是正整数的整个等比数列都放进去同一个抽屉才行,这里用得 到一个自然数分类的基本知识:任何一个正整数都可以表示成一个奇数与 2 的方幂的积,
+ + 即 若 m ∈ N , K ∈ N , n ∈ N , 则 m = ( 2k ? 1) ? 2n , 并 且 这 种 表 示 方 式 是 唯 一 的 , 如

1 = 1× 20 , 2 = 1× 21 ,3 = 3 × 20 ,...... .

证明 因为任何一个正整数都能表示成一个奇数乘 2 的方幂,并且这种表示方法是唯 一的,所以我们可把 1 ? 100 的正整数分成如下 50 个抽屉(因为 1 ? 100 中共有 50 个奇 数):

(1) {1,1× 2,1× 22 ,1× 23 ,1× 24 ,1× 25 ,1× 26 } ; ( 2 ) {3,3 × 2,3 × 22 ,3 × 23 ,3 × 24 ,3 × 25 } ; ( 3) {5,5 × 2,5 × 22 ,5 × 23 ,5 × 24 } ; ( 4 ) {7, 7 × 2, 7 × 22 , 7 × 23 } ; ( 5) {9,9 × 2,9 × 22 ,9 × 23 } ; ( 6 ) {11,11× 2,11× 22 ,11× 23 } ;
......

( 25){49, 49 × 2} ; ( 26 ){51} ;
......

( 50 ){99} .
这样, 1 ? 100 的正整数就无重复,无遗漏地放进这 50 个抽屉内了。从这 100 个数中 任取 51 个数,也即从这 50 个抽屉内任取 51 个数,根据抽屉原则,其中必定至少有两个 数属于同一个抽屉,即属于 (1) ? ( 25 ) 号中的某一个抽屉,显然,在这 25 个抽屉中的任何 同一个抽屉内的两个数中,一个是另一个的整数倍.
- 14 -

湖南科技大学本科生毕业设计(论文)

说明

从上面的证明中可以看出,本题能够推广到一般情形:从 1 ? 2n 的自然数中,

任意取出 n + 1 个数,则其中必有两个数,它们中的一个是另一个的整数倍.想一想,为什 么?因为 1 ? 2n 中共含 1,3,..., 2n ? 1 这 n 个奇数,因此可以制造 n 个抽屉,而 n + 1 > n ,由抽 屉原则,结论就是必然的了.给 n 以具体值,就可以构造出不同的题目. 例 2[10] 已给一个由 10 个互不相等的两位十进制正整数组成的集合. 求证:这个集合必有两个无公共元素的子集合,使子集合中各数之和相等(第 14 届
IMO 试题) .

分析

求证中的“必有”也就是“一定存在”.对于找出任意给定元素的相关存在

性,是不必也无法找到其具体构成的子集的个数之和的,不妨考虑用抽屉原理,通过构造 适当的抽屉,整除存在性. 本题涉及两件事情:一是 10 个元素的非空子集,二是非空子集中的各数之和(显 然,这样的数是有界的),自然会想到从这两方面制作“球”和“抽屉”,为此,必然要 问两个问题:10 个元素的非空子集总共有多少个?对于这些非空子集中的个数之和,其 上界与下界各是多少? 证明 一个有着 10 个元素的集合共有 210 = 1024 个不同的子集,包括空集和全集在内. 空集与全集显然不是考虑的对象,所以剩下 1024 ? 2 = 1022 个非空真子集. 再来看各个真子集中一切数字之和.用 N 来记这个和数,显然:
10 ≤ N ≤ 91 + 92 + 93 + 94 + 95 + 96 + 97 + 98 + 99 = 855

这表明 N 至多只有 855-9=846 种不同的情况.由于非空真子集的个数是 1022,
1022 > 846 ,所以一定存在两个子集 A 与 B ,使得 A 中各数之和 = B 中各数之和.

若 A ∩ B = ? ,则命题得证,若 A ∩ B = C ≠ ? ,即 A 与 B 有公共元素,这时只要剔除
A 与 B 中的一切公有元素,得出两个不相交的子集 A1 与 B1 ,很显然 , A1 中各元素之和

= B1 中各元素之和,因此 A1 与 B1 就是符合题目要求的子集.

3.6 3.6 总结应用抽屉原理解题的步骤
在应用抽屉原理进行解题的过程中,我们把解题步骤分为三步. 第一步: 分析题意.分清什么是“东西”,什么是“抽屉”,也就是把什么看作“东 西”,把什么看作“抽屉”. 第二步:制造抽屉.这是关键的一步.这一步就是如何设计抽屉, 根据题目条件和结 论,结合有关的数学知识,抓住最基本的数量关系,设计和确定解决问题所需的抽屉及其 个数,为使用抽屉原理铺平道路.

- 15 -

湖南科技大学本科生毕业设计(论文)

第三步:运用抽屉原理.观察题设条件,结合第二步,恰当应用各个原则或综合运用 几个原则,以求问题之解决.

- 16 -

湖南科技大学本科生毕业设计(论文)

第四章 结论
数学竞赛中不乏好题,而许多的经典好题出现在组合数学中,在解决有关抽屉原理的 问题时,只要证明存在,一般并不需要指出哪一个,也不需要确定通过什么方式把这个存 在的东西找出来,这类问题相对来说涉及的运算较少,依据的理论也很浅显。抽屉原理是 一个非常简单但又是应用广泛的原理,它是证明存在性问题的有效方法。在解一些数学竞 赛试题中常有用武之地。抽屉原理的运用比较灵活,在竞赛辅导中交给学生一些简单的思 想方法有助于培养学生的构造法解题意思,使学生的思维能力得到一定的提高,不仅有利 于高中学习,也可以为将来的高等数学学习带来一定的帮助。

- 17 -

湖南科技大学本科生毕业设计(论文)

- 18 -

湖南科技大学本科生毕业设计(论文)

参考文献
[1]刘诗雄,熊 斌.高中竞赛数学教程(第二卷)[M].湖北:武汉大学出版社,2003. [2]卢开澄,卢华明.组合数学[M].北京:清华大学出版社,2005. [3]朱华伟,符开广.抽屉原理[J].数学通讯,2006,19:42-44. [4]牛保才.抽屉原理的几点注记[J].长治医学院学报,1995,2:183-186. [5]庞国萍.抽屉原理的抽屉构造法[J].玉林师范高等专科学校学报(自学),2000,3:10-13. [6]熊 斌,冯志刚.数学竞赛之窗[J].数学通讯,2004,17:46-47. [7]庞晓丽.用“抽屉”原理解决逻辑问题[J].保定师专学报,20014,2:52-53. [8]李成章.世界数学奥林匹克解题大题典[M].河北:河北少年儿童出版社,2002. [9]柳柏濂,吴 康.竞赛数学的原理与方法[M].广州:广东高等教育出版社,2002. [10]刘培杰.历届 TMO 试题集(1995-2005)[M].哈尔滨:哈尔滨工业大学出版社,2006.

- 19 -

湖南科技大学本科生毕业设计(论文)

- 20 -

湖南科技大学本科生毕业设计(论文)





从论文选题到搜集资料,从提纲的完成到正文的反复修改,我经历了喜悦、聒噪、痛 苦和彷徨,在写作论文的过程中,心情是如此复杂。如今,伴随着这篇毕业论文的最终成 稿,复杂的心情烟消云散,自己甚至还有一点成就感。 论文的顺利完成首先最需要感谢我的指导老师吕胜祥老师.本文从开题到定稿都倾注 了老师的心血,耗费了大量的时间与精力.本论文自始至终都是在老师的悉心指导下完成 的.老师时时关心我所写论文的进程,不仅为我提供了许多宝贵意见,而且不顾工作的辛 劳,经常抽出时间与我探讨所遇到的各种问题.老师严谨的治学态度、渊博的专业知识、 精益求精的工作作风和平易近人的人格魅力对我影响深远,为我以后的学术道路打下了坚 实的基础.老师的谆谆教导、耐心教诲都给了我深深的启迪.在此向他表示衷心的感谢. 其次我还要感谢帮助我的老师和同学,感谢他们能为我提供一些论文资料和参考数据 的寻找途径,感谢他们能及时通知我关于论文完成过程中指导老师提出的各项要求,使我 能按时完成. 同时衷心感谢在百忙之中抽出时间给我评阅论文和参加答辩的老师!

学生签名: 日 期: 年 月 日

- 21 -


相关文章:
浅谈抽屉原理在高中数学竞赛中的运用
浅谈抽屉原理高中数学竞赛中的运用 浅谈抽屉原理高中数学竞赛中的运用 抽屉原理在数学问题中有一类与“存在性”有关的问题,例如:“13 个人中至少有两个人出生...
抽屉原理与高中数学竞赛
摘 要 本论文首先讨论了抽屉原理的一般含义和它的两种推广形式;其次给出了抽屉原理在 整除问题、面积问题、染色问题、六人集会问题以及生日问题等高中数学竞赛问题中...
高中数学竞赛讲义-抽屉原理
数学教育网---数学试题-数学教案-数学课件-数学论文-竞赛试题-中高考试题信息 http://www.qyjzs.cn 抽屉原理数学问题中有一类与“存在性”有关的问题,例如:...
浅谈抽屉原理在高中数学竞赛中的运用 在数学问题中有一类
浅谈抽屉原理高中数学竞赛中的运用在数学问题中有一类与“存在性”有关的问题,例如:“13 个人中至少有两个人出生 在相同月份”;“某校 400 名学生中,一定存在...
04【数学】高中数学竞赛讲义-抽屉原理
高中数学联赛 奥林匹克竞赛 讲义高中数学联赛 奥林匹克竞赛 讲义隐藏>> 书利华教育网 www.shulihua.net 精心打造一流新课标资料 §23 抽屉原理在数学问题中有一类...
05【数学】高中数学竞赛讲义-抽屉原理(练习题)
05【数学】高中数学竞赛讲义-抽屉原理(练习题)_高三数学_数学_高中教育_教育专区。高中数学联赛 奥林匹克竞赛 讲义 书利华教育网 www.shulihua.net 精心打造一流...
【江苏省数学竞赛《提优教程》】第10讲 抽屉原理
【江苏省数学竞赛《提优教程》】第10讲 抽屉原理_高二数学_数学_高中教育_教育专区。【江苏省数学竞赛《提优教程》 】第 10 讲 抽屉原理 抽屉原理又叫鸽笼原理...
北京数学竞赛培训第13讲 抽屉原理
北京数学竞赛培训第13讲 抽屉原理_数学_高中教育_教育专区。第 13 讲 抽屉原理 把 5 个苹果放到 4 个抽屉中,必然有一个抽屉中至少有 2 个苹果,这 是抽屉原...
高中数学联赛二试概念集锦
高中数学联赛二试概念集锦_学科竞赛_高中教育_教育专区。1、平面几何 基本要求:...抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。 容斥原理。 ...
初一数学竞赛讲义15(抽屉原理)
初一数学竞赛辅导资料 第 15 讲一、知识要点 1、抽屉原理 1 抽屉原理初步(2 个课时) 2006-12-9 把 n+1 个东西,任意地分放到 n 个抽屉里,那么必有一个...
更多相关标签:
小学数学抽屉原理 | 数学抽屉原理 | 高中数学竞赛 | 高中数学竞赛培优教程 | 高中数学竞赛专题讲座 | 全国高中数学联合竞赛 | 高中数学竞赛辅导书 | 2016全国高中数学竞赛 |