-
习
题
五
习题五（抽屉原理）
1
．证明 ：在边长为
2
的等边三角形中任取
5
点，至少有两 个点相距不超过
1
。
证明：如图所示，
将正三角形分成
4
个边长为
1
的小等
边三角形，现在取
5
点，有
4
个小等边 三角形，
根据抽屉原理，则至少有两点落在同一个小
< br>等边三角形中，其距离不超过
1
。
2
．在一个边长为
1
的正方形内任取
9
个点，证明以这些点为顶点的各个三角形
中，至少有一个三角形的面积不大于
1
8
。
证明：
如图所示，
将正方形分为< /p>
4
个边长为
1
2
的
小正方形，
现取
9
个点，则至少有三个点落在同一个小正 方形
中
，
以
这
三
点
为
顶
点
的
三
角
形
的
面
积
不
大
于
1
2
?
长
?
高
?
1
2
?
1
2
?
1
2
?
。
1
8
3
．把从
1
到
326
的
326
个正整数任意分成
5
组，试证 明其中必有
1
组，该组中
至少有一个数是同组中某两个数
之和，或是同组中某个数的两倍。
证明：用反证法。
设任何一组中的每一个数，
它既不等于同组中另外两数之和，
< p>也不等于同
组中另一数的两倍。即任何一组数中任意两个数之差总不在该组中。
（
1
）由抽屉原理知，五组中必有一组其中 至少有
66
个数，设为
A
组。
< /p>
从中取
66
个数，记为
a
1
,
a
2
,
?
,
a
66
，不妨设
a
66
最大，
令
a
i
(
1
)
?
a
66
?
a
i
,
i
?
1
,2,< /p>
?
,65
，显然
1
?
a
i
(1)
?
326
，
由假设知
a
i
(1)
?
A
，故这
65
个数必在另外四组
B
、
C
、
D
、
E
中。
（
2
）由抽屉原理知，
B
、
C
、
D
、
E
四组中必有一组至少含有
17
< p>个
a
i
(1)
，
设为
B
组，从中取
17
个
a
i
(1)<
/p>
，记为
b
1
,<
/p>
b
2
,
?
,
b
17
，同理不妨设
b
17
最大，
令
b
i
(
1
)
?
b
17
?
b
i
i
?
1
,2,
?< /p>
,16
，
显然
1
?
b
i
(1)
?
326
，
且由假设知，
b
i
(1)
?
B
，
又
b
i
(1)
?
b
17
?
b
i
?
(
a
66
?
a
j
)
?
(
a
66<
/p>
?
a
k
)
?
a
k
?
a
j
?
A
，
所以这
16
个数
b
i
(1)
必在
C
< p>、D
、
E
中。
（
3
）由抽屉原理知，
C
、
< p>D、
E
三组中必有一组至少含有
6
< p>个
b
i
(1)
，设为
C
组，
从中取
6
个
b
i
(1)
，
记为
c
1
,
c
2
,
?
,
c
6
，同理不妨设
c
6
最大，
令
c
i
(1)
?
c
6
?
c
i
，
i
?
1,2,
?
,5
，显然
1
?
c
i
(1)
?
326
，且由假设
知
c
i
(1)
?
C
，
又
c
i
(
1
)
?
c
(
1
b
7
?
b
)
?
(
1
b
7
?
k
b
)
?
k
b
?
j
b
?
B
6
?
c
i
?
j
第
1
页（共
11
页）
习
题
五
c
i
(1)
?
b
k
?
b
j
?
(
a
66
?
a
n
)
?
(
a
66
?
a
m
)
?
a
m
?
a
n
?
A
所以这五个数必在
D
、
E
组中。
（
4
）由抽屉原理知，
D
、
E
两组中必有一组至少含有
3
个
c
i
(1)
，设为
D< /p>
组，
从中取
3
个
c
i
(1)
，
记为
d
1
,
d
2
,
d
3
，同理不妨设
d
3
最大，
令
d
i
(1)
?
d
3
?
d
i
,
i
?
1
,2
，显然
1
?
d
i
(1)
?
326
，且由假设知
d
i
(1)
?
D
，
同理可得
d
i
(1)
?
A
,
B
,
C
，故
d
i
(1)
?
E
。
(1)
(1)
（
5
）不妨设
d
1
(1
)
?
d
2
，令
e
?
d
1
(1)
?
d
2
，则
1
?
e
?
326< /p>
，且由假设知
e
?
E
，
同理可知，
e
?
A
,
B
,
C
,
D
，
即
e
不在
A
、
B
、
C
、
D
、
E
任一组中，又
< br>1
?
e
?
326
，
与题设矛盾。
所以，命题成立。证毕。
4
．任意一个由数字
1
，
2
，
3
组成的
30
位数，从中任意截取相邻的三位，证明在
各种不同位置的截取中，
数的位数
30
还可以再
减少吗？为什么？
解：设由数字
1
，
2
，
3
组成的
30< /p>
位数为：
a
1
a
2
?
a
30
，
则任意截取相邻的三位，可能的截法有
28
种：
a
1
a
2
a
3
,
a
2
a
3
a
4
,
?
< p>,a
27
a
28<
/p>
a
29
,
a
28
a
29
a
30
，
而由
1
，
2
，
3
组成的三位数最多有
3
3
?
27
个，
则根据抽屉原理，这
28
个数 中必至少有
2
个是相同的。
由证明过程可以知道，数的位数
< p>30不可以再减少了。
因为若改为
29
个，则可得到
27
个三位数，就不能保证有
2
个是相同的。
?
若改 为截取相邻的
5
位
，
首先可知元素
1
、
2
、
3
的
5< /p>
－可重排列共有
3
5
?<
/p>
243
个。其次，由问题的性质可知至少要能截取出不同的
244
段才能保证结论成
立，从而知该数至少应该有
24 8
位。
?
问题的一般 描述是
：任意一个由数字
1
，
2
， …，
m
组成的
n
＝
m
k
?
k
位数，
从中任意截取相邻的
k
位，则在各种不同位置的截取中，至少有两个< /p>
k
位数
是相同的。若希望至少有
r
个
k
位数是相同的，则应有
n
＝
< p>?
r
?
1
?
m
k
?
k
。
5
．任取
< p>11个整数，求证其中至少有两个数的差是
10
的倍数。
证明：设这
11
个整数为：
a
i
(
i
?
< p>1,2,
?
,11)
，不妨设
a
1
?
a
2
?
?
?
a
11
，
令
r
i
?
a
i
mod10
，则
0
?
r
i
?
10
，
由抽屉原理知，必存在
i
,
j< /p>
，
i
?
j
，使得
r
i
?
r
j
，
则
< /p>
10|
(
a
j
?
a
i
)
。证毕。
?
问题的一般描述
： 任取
n
＋
1
个整数，其中至少存在两数，其差是< /p>
n
的倍数。
第
2
页（共
11
页）
习
题
五
6
．一次考试采用百分制，所有考生 的总分为
10101
，证明如果考生人数不少于
202<
/p>
，则必有三人得分相同。
证明：采用百分制，则所有可能
的分数为
0
~
100
，共
101
个分数，现人数不少
于
202
< p>，则平均每个分数有两个人得分相同。分情况讨论：
（
）
若有某些分数没有考生得该分数，
则
20 2
名考生，
可能的考生成绩最
多
100< /p>
种，根据抽屉原理，必有三个的得分相同。
（
）
若有
1
个考生的分数与其他人都不同，< /p>
则其余
201
名考试可能的分数
只有
100
种，则必有三人的得分相同。
（
3
）若每个分数线都有两个人，则所有考生的总分为：
2(1
?
2
?
?
?
100)
?
10100
，与题目矛盾
。所以这种情况不可能存在。
综上所述，必有三人得分相同。证毕。
?
方法二：反证法。
假设没有三个考生考试成绩相同，
因为分数的分布为
0
～
100
分，
共
101
种分
数，若考生人数大于
202
人，则根据抽屉原理必然有三人考试成 绩相同，矛盾；
若考生人数恰好
202
个，要求没有三个考生考试成绩相同，则所有考生必然
恰好两两得分相同。
而此时所有考生的总分为：
2(0
?
1
?
2
?
?
?
< p>100)?
10100
，矛盾。
故结论成立。
?
方法三：
此题的另一种理解是将
101 01
个物品放入
202
个盒子，
每个盒子最多放< /p>
100
个，也可以不放，则至少有三个盒子中所放物品个数相同。如若不然
，至多有两
个盒子的物品一样多，
则只能恰好用去
101 00
个物品，
剩下一个物品，
就无法处
理
，一旦将其放入某个有
k
个物品的盒子，那么，就有
3
< p>个盒子放了k
＋
1
个物
品
?
k
?
0
,
1
,
2
,
?
,
99
?
。
?
此问题的一般提法是
：
所有考生的总分为
5050r
＋
t
?
1
?
t
?
5050
?
，
如果考生
人数不多于
101
r
人，则至少有
r
＋
< p>1人得分相同。
7
．将
n
个球放入
m
个盒子中，
n
?
m
(
m
?
1)
，试证其中必有两个盒子有相同的
2
球数。
证明：
（反证法）
。
假设
m
个盒子中的球数均不相同，则
m
个盒子中 球的总数至少为：
m
(
m
?
1
)
?
?
3
?
?
m
(
?
?
1
)
?
n
，矛盾，
0
?
1
?
2
2
故必然有两个盒子的球数是相同的。
第
3
页（共
11
页）
习
题
五
8
．设有三个
7
位二进制数：
(
a
1
a
2
a
3
a
4
a
5
a
6
a
7
)<
/p>
、
(
bb
1
2
b
3
b
4
b
5
b
6
b
7
)
和
(
c
1
c
2
c
3
c
4
c
5
c
6
c
7
)
，
试证存在整数
i
和
j
，
< p>1
?
i
?
j
?
7
，使得下列等式中至少有一个成立：
a
i
?
a
j
?
b
i
?
b
，
j
b
i
?
b
j
?
c
i
?
c
j
，
c
i
?
c
j
?
a
i
?
a
j
证明：因为二进制数只有
0,1
两种数位，
< br>从而有
a
k
,
b
k
,
c
k
(
k
?
1
,2,
?
,7)
只有两种状态，又
7
?
3
?
2
?
1
，<
/p>
根据抽屉原理可知，在
a
1
,
a
2
,
a
3
,
a
4
,
a
5
,
a
6
,
a
7
这
7
个元素中，至少有四个元
素的取值相同，
或均为
1
，或均为
0
。不妨设这四个元素为
a
1
,
a
2
,
a
3
,
a
4
，且设
，
a
1
?
a
2
?
a
3
?
a
4
?
1
（同理可讨论
a
1
?
a
2
?
a
3
?
a
4
?
0
的情况）
?
4
?
因为
?
?
?
2
，由抽屉原理可知，在
b
1
,
b
2
,
b
3
,
b
4
< br>这四个元素中，必至少有两
?
2
?
个元素取值相同，或均为
1
，或均为
0
。不妨设这两个元素为：
b
1
< br>,
b
2
，
（
1
）
若
b
1
?
b
2
?
1
，则得
< br>a
1
?
a
2
?
b
1
?
b
2
?
1
，满足结论，<
/p>
（
2
）若
b
1
?
b
2
< br>?
0
，则
①
若
b
3
?
b
4
?
1
，则
a
3
?
a
4
?
b
3
?
b
4
?<
/p>
1
，满足结论；
②
否则，
b
< br>3
,
b
4
中至少
有一个取
0
。不妨设
b
3
?
0
，
从而
有
b
1
?
b
< p>2
?
b
3
?
0
。
?
3
?
因为由
?
?< /p>
?
2
，
由抽屉原理可知，
在
c
1
,
c
2
,
c
3
< br>中应至少有两个元素
?
2
?
取值相同，不妨设是
c
1
< br>,
c
2
，则
?
若
c
1
?
c
2
?
1
，则有
a
1
< br>?
a
2
?
c
1
?
c
2
?
1
，满足结论；
?
若
c
1
?
c
2
?
0
，则有
b
1
< br>?
b
2
?
c
1
?
c
2
?
0
，满足结论。
综上所述，结论必成立。证毕。
?
证法二：
?
3
?
显然，每组
(
a
i
,
b
i
,
c
i
)<
/p>
(
i
?
1
,2,
?< /p>
,7)
中，必有两数字相同，共有
?
?
2
?
?
< br>种模式，
?
?
?
3
?
其值或为０或为１，故共有
2
?
?
?
?
6
种选择。
?
2
?
?
7
?<
/p>
现在有
7
组，
因为
?
?
?
2
，
由抽 屉原理可知，
必有２组数在相同的两行
i
、
?
6
?
第
4
页（共
11
页）
习
题
五
j
上选择相同的数字，即存在整数< /p>
i
和
j
，
1
?
i
?
j
?
7
，使得下式之一必然成立：
a
i
?
a
j
?
b
< br>i
?
b
，
j
b
i
?
b
< br>j
?
c
i
?
c
j
，
c
< br>i
?
c
j
?
a
i
?
a
j
?
证法三：
考虑将
3
个
7
位二进制数 视为一个
3
×
7
的方格棋盘，用红、蓝两色（分别
用
0
、
1
表示）之一对每 个方格进行染色，则问题变成：证明至少有
4
个格子同
色
，
且此
4
个格子位于由若干个小方格组成的某个长方形的
4
个角上。
也就是说
必存在两行两列，其交叉处的
4
个格子同色
0
0
1
1
1
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
0
0
1
1
0
1
1
0
由于颜色数比行数少一，故对每列而言，至少有两格同色。如图
5.2.3< /p>
（
a
）
，
设第一列的前两行
为红色，
后一行为蓝色，
则后
6
列中的任何一列的 前两行都不
能再为红色，
否则即会出现
4
个同色格子构成长方形的情形，
即结论成立。
由此
看出，
两个红色方格同列的情形最多只能有
C
3
＝
3
列。而图
5.2.3
（
b< /p>
）的染法，
只能使得这样的列数最多为
1
列 ，
其后每列最多只能有一个红格子，
且各列红格
子所处的
行还不能相同。
总之，对每种颜色，在某列中被用了两次的列最多为<
/p>
C
3
2
列。当颜
色数为
2
时，这样的列最多只有
2
·
C
3
＝
6
个 ，现在总列数为
7
，故由抽屉原理，必有某
两列中相同的
两行的
4
个格子所染颜色相同。
9
．
证明：
把
1
～
10
这
10
个数随机地写成一个圆圈，
则必有某
3
个相邻数之和大
于或等于
。若改为
1
～
26
，则相 邻数之和应大于或等于
41
。
证明：设
这
10
个数围成的圆圈为
a
1<
/p>
a
2
?
a
9
a
10
a
< br>1
，
令
A
i
?
a
i
?
a
i
?
1
?
a
i
?
2
< br>,
i
?
1
,2,
?
,8
，
A
9
?
a
9
?
a
10
?
a
1
，
A
10
?
a
< p>10
?
a
1
?
a
2
，
则
A
1
?
A
2
?
?
?
A
10
?
3
?< /p>
(1
?
2
?
?
?
10)
?
165
?
16
?
10
?
5
，
现在有
10
个数，故必存在某个
A
i
?
17
。
证毕。
同理，若是
1
～
26
，则同样可构造出
3
个相邻数之和
B
k
(
k
?
1< /p>
,2,
?
26)
，
且有
B
1
?
B
2
?
?
?
B
26
?
3
?
(1
?
2
?
?
?< /p>
26)
?
1053
?
40
< p>?26
?
13
，
故必存在某个
B
k
?
41
。
?
一般情形
：
已知
n
个正整数数
a
1
,
a
2
,
?
,
a
n
，将其随机地写成一
个圆圈，则
2
2
?
?
a
?
a
2
?
?
?
a
n<
/p>
?
k
?
必有某<
/p>
k
个相邻数之和大于或等于
M
，那么，
M
≤
?
1
?
n
?
?
第
5
页（共
11
页）