习 题 五
习题五(抽屉原理)
1.证明:在边长为2的等边三角形中任取5点,至少有两个点相距不超过1。
证明:如图所示,将正三角形分成4个边长为1的小等边三角形,现在取5点,有4个小等边三角形,
根据抽屉原理,则至少有两点落在同一个小等边三角形中,其距离不超过1。
2.在一个边长为1的正方形内任取9个点,证明以这些点为顶点的各个三角形中,至少有一个三角形的面积不大于
。
证明:如图所示,将正方形分为4个边长为
的小正方形,现取9个点,则至少有三个点落在同一个小正方形中,以这三点为顶点的三角形的面积不大于
。
3.把从1到326的326个正整数任意分成5组,试证明其中必有1组,该组中至少有一个数是同组中某两个数之和,或是同组中某个数的两倍。
证明:用反证法。
设任何一组中的每一个数,它既不等于同组中另外两数之和,也不等于同组中另一数的两倍。即任何一组数中任意两个数之差总不在该组中。
(1)由抽屉原理知,五组中必有一组其中至少有66个数,设为A组。
从中取66个数,记为
,不妨设
最大,
令
,显然
,
由假设知
,故这65个数必在另外四组B、C、D、E中。
(2)由抽屉原理知,B、C、D、E四组中必有一组至少含有17个
,
设为B组,从中取17个
,记为
,同理不妨设
最大,
令
,显然
,且由假设知,
,
又
,
所以这16个数
必在C、D、E中。
(3)由抽屉原理知,C、D、E三组中必有一组至少含有6个
,设为C组,
从中取6个
,记为
,同理不妨设
最大,
令
,
,显然
,且由假设知
,
又
所以这五个数必在D、E组中。
(4)由抽屉原理知,D、E两组中必有一组至少含有3个
,设为D组,
从中取3个
,记为
,同理不妨设
最大,
令
,显然
,且由假设知
,
同理可得
,故
。
(5)不妨设
,令
,则
,且由假设知
,
同理可知,
,
即e不在A、B、C、D、E任一组中,又
,与题设矛盾。
所以,命题成立。证毕。
4.任意一个由数字1,2,3组成的30位数,从中任意截取相邻的三位,证明在各种不同位置的截取中,至少有两个三位数是相同的。数的位数30还可以再减少吗?为什么?
解:设由数字1,2,3组成的30位数为:
,
则任意截取相邻的三位,可能的截法有28种:
,
而由1,2,3组成的三位数最多有
个,
则根据抽屉原理,这28个数中必至少有2个是相同的。
由证明过程可以知道,数的位数30不可以再减少了。
因为若改为29个,则可得到27个三位数,就不能保证有2个是相同的。
· 若改为截取相邻的5位,首先可知元素1、2、3的5-可重排列共有
个。其次,由问题的性质可知至少要能截取出不同的244段才能保证结论成立,从而知该数至少应该有248位。
· 问题的一般描述是:任意一个由数字1,2,…,m组成的n=
位数,从中任意截取相邻的k位,则在各种不同位置的截取中,至少有两个k位数是相同的。若希望至少有r个k位数是相同的,则应有n=
。
5.任取11个整数,求证其中至少有两个数的差是10的倍数。
证明:设这11个整数为:
,不妨设
,
令
,则
,
由抽屉原理知,必存在
,
,使得
,
则
。证毕。
· 问题的一般描述:任取n+1个整数,其中至少存在两数,其差是n的倍数。
6.一次考试采用百分制,所有考生的总分为10101,证明如果考生人数不少于202,则必有三人得分相同。
证明:采用百分制,则所有可能的分数为
,共101个分数,现人数不少于202,则平均每个分数有两个人得分相同。分情况讨论:
(1)若有某些分数没有考生得该分数,则202名考生,可能的考生成绩最多100种,根据抽屉原理,必有三个的得分相同。
(2)若有1个考生的分数与其他人都不同,则其余201名考试可能的分数
只有100种,则必有三人的得分相同。
(3)若每个分数线都有两个人,则所有考生的总分为:
,与题目矛盾。所以这种情况不可能存在。
综上所述,必有三人得分相同。证毕。
· 方法二:反证法。
假设没有三个考生考试成绩相同,因为分数的分布为0~100分,共101种分数,若考生人数大于202人,则根据抽屉原理必然有三人考试成绩相同,矛盾;
若考生人数恰好202个,要求没有三个考生考试成绩相同,则所有考生必然恰好两两得分相同。
而此时所有考生的总分为:
,矛盾。
故结论成立。
· 方法三:
此题的另一种理解是将10101个物品放入202个盒子,每个盒子最多放100个,也可以不放,则至少有三个盒子中所放物品个数相同。如若不然,至多有两个盒子的物品一样多,则只能恰好用去10100个物品,剩下一个物品,就无法处理,一旦将其放入某个有k个物品的盒子,那么,就有3个盒子放了k+1个物品
。
· 此问题的一般提法是:所有考生的总分为5050r+t
,如果考生人数不多于101r人,则至少有r+1人得分相同。
7.将n个球放入m个盒子中,
,试证其中必有两个盒子有相同的球数。
证明:(反证法)。
假设m个盒子中的球数均不相同,则m个盒子中球的总数至少为:
,矛盾,
故必然有两个盒子的球数是相同的。
8.设有三个7位二进制数:
、
和
,试证存在整数i和j,
,使得下列等式中至少有一个成立:
,
,
证明:因为二进制数只有0,1两种数位,
从而有
只有两种状态,又
,
根据抽屉原理可知,在
这7个元素中,至少有四个元素的取值相同,或均为1,或均为0。不妨设这四个元素为
,且设
(同理可讨论
的情况),
因为
,由抽屉原理可知,在
这四个元素中,必至少有两个元素取值相同,或均为1,或均为0。不妨设这两个元素为:
,
(1) 若
,则得
,满足结论,
(2)若
,则
① 若
,则
,满足结论;
② 否则,
中至少有一个取0。不妨设
,
从而有
。
因为由
,由抽屉原理可知,在
中应至少有两个元素取值相同,不妨设是
,则
· 若
,则有
,满足结论;
· 若
,则有
,满足结论。
综上所述,结论必成立。证毕。
· 证法二:
显然,每组
中,必有两数字相同,共有
种模式,
其值或为0或为1,故共有
种选择。
现在有7组,因为
,由抽屉原理可知,必有2组数在相同的两行i、j上选择相同的数字,即存在整数i和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(a),设第一列的前两行为红色,后一行为蓝色,则后6列中的任何一列的前两行都不能再为红色,否则即会出现4个同色格子构成长方形的情形,即结论成立。由此看出,两个红色方格同列的情形最多只能有
=3列。而图5.2.3(b)的染法,只能使得这样的列数最多为1列,其后每列最多只能有一个红格子,且各列红格子所处的行还不能相同。
总之,对每种颜色,在某列中被用了两次的列最多为
列。当颜色数为2时,这样的列最多只有2·
=6个,现在总列数为7,故由抽屉原理,必有某两列中相同的两行的4个格子所染颜色相同。
9.证明:把1~10这10个数随机地写成一个圆圈,则必有某3个相邻数之和大于或等于17。若改为1~26,则相邻数之和应大于或等于41。
证明:设这10个数围成的圆圈为
,
令
,
,
,
则
,
现在有10个数,故必存在某个
。证毕。
同理,若是1~26,则同样可构造出3个相邻数之和
,
且有
,
故必存在某个
。
· 一般情形: 已知n个正整数数
,将其随机地写成一个圆圈,则必有某k个相邻数之和大于或等于M,那么,M≤
10.某学生准备恰好用11个星期时间做完数学复习题,每天至少做一题,一个星期最多做12题,试证必有连续几天内该学生共做了21道题。
证明:11个星期总共有77天,每天做的题数设为
,
则
,
,
构造序列
,则
,
若存在某个
,则问题得证。
否则,所有的
,令集合
,
则有
,
集合A中共有154个数,每个数的取值在1~153之间,
由抽屉原理知,必有两个数相等。又
时,
,从而
,
所以,相等的两个数必为
,显然
,
故
。证毕。
11.
行
列的格子用m种颜色着色,每格着一种色,证明其中必有一个4角的格子同色的矩形。
证明:每列有
行,只有m种颜色,
因此,根据抽屉原理,一列中必有两格同色。
一列中同色的两个格子的行号有
种取法,故有
种同色模式。
现有
列,所以,根据抽屉原理,必有两列的同色模式相同。
因此,这两列对应于同色模式的两行上有4个格子同色,
它们正好是一个矩形的4个角上的格子。证毕。
12.证明:(1)平面上任取5个整点(坐标为整数的点),其中至少有两个点,
由它们所连线段的中点也是整点。
(2)从三维空间任取9个整点中至少有两个点,其连线的中点为整点。
证明:平面上的整点的坐标为
,而x、y只可能为奇数或偶数,
故可能的坐标只有四种:(奇,奇)、(奇、偶)、(偶,奇)、(偶,偶),
现在取5个整点,则必有两个整点的奇偶性是一样的,
设这两个整点为
,
,则
奇偶性相同,
奇偶性相同,
而这两个点的连线中点的坐标为:
,
因为
奇偶性相同,
奇偶性相同,所以
,
均为偶数,
所以
为整点。
(2)三维空间的点的坐标为
,
根据x,y,z的奇偶性可将坐标分为8类:(奇,奇,奇)、(奇,奇,偶)、
(奇,偶,奇)、(奇,偶,偶)、(偶,奇,奇)、(偶,奇,偶)、(偶,偶,奇)、(偶,偶,偶),
现在取9个点,则必有2个点的类型相同,
设这两个整点为:
,
,
则
奇偶性相同,
奇偶性相同,
奇偶性相同,
而这两个点的连线中点的坐标为:
,
因为
,
,
均为偶数,所以该点为整点。
(0,0)
(0,1)
(0,2)
(1,0)
(1,1)
(1,2)
(2,0)
(2,1)
(2,2)
13.在平面直角坐标系中至少任取多少个整点,才能保证其中存在3个点构成的三角形的重心是整点。
解: 设三角形三个顶点的坐标为:
,
,
,
则其重心坐标为:
,
因为平面直角坐标系中的整点
的坐标模3后只有如表所示的9种可能;而满足3点重心是整点的条件类型有以下4种情况:
(1)3点在同一格子中;
(2)3点占满一行的格子;
(3)3点占满一列的格子;
(4)3点均匀分布,不同行也不同列,由下面四种模式:
(0,0),(1,1),(2,2)( )(主对角线);(1,0),(2,1),(0,2)( );
(0,2),(1,1),(2,0)( )(副对角线);(0,1),(1,2),(2,0)( );
因而任取9个点中,必至少存在着3个点,其重心是整点。下面证明。
(反证法)假设任取9个点,不存在3个点构成的三角形的重心是整点。
则每个格子最多有2个点,否则有三个点在同一格子中,满足(1),其重心是整点,与假设矛盾。
因为
格,根据抽屉原理,则9个点至少落入5个格子中,
若5个格子中有三个在同一行,即满足(2),则与假设矛盾,故每行最多有占2格,又
行,根据抽屉原理,则每行都有点;
同理,若5个格子中有三个在同一列,即满足(3),与假设矛盾,故每列最多占2格,同理
列,根据抽屉原理可知,每列都有点;
由证明过程知,每行每列都有点,又不满足(1)(2)(3),
则必是(4)的情况,这与假设矛盾。
因此,因而任取9个点中,必至少存在着3个点,其重心是整点。
但是8个点中不能保证其中存在着3个点其重心一定是整点。
因为存在着一种情况:8个点分布在表1的4个格子中,每格2个点,而不满足3点重心是整点的条件类型的4种情况。例如若8个点落在表1的左上角(0,0),(0,1),(1,0),(1,1)这4个格子中,每格2个点,则显然不满足3点重心是整点的条件类型的4种情况。
因此,在平面直角坐标系中,最少需任取9个整点,才能保证其中存在3个点构成的三角形的重心是整点。
第二版新增部分习题:
11.求证在任意给的11个整数中,一定存在6个整数,它们的和是6的倍数。
证明:设这11个数为
,
令
,则
的可能取值为0,1,2(看为3个抽屉),
根据抽屉原理,至少有3个整数的
相同,不妨设这3个整数为
,
令
,则
,
剩下8个整数中,根据抽屉原理,至少有3个整数的
相同,不妨设为
,令
,则
,
剩下5个整数中,若有3个整数的
相同,则它们之和必然被3整除,
否则
相同的整数最多2个,则必存在三个整数,其
取值都不相同,则它们之和也是3的倍数,因此从5个数中,必然可以找到3个数,其和是3的倍数,不妨设这三个数为
,令
,则
,
对于
这三个数而言,令
,
则根据抽屉原理,至少有2个数的ti相同,不妨设这两个数为
,
则
,而又有
,
,故
。
证毕。
12.证明任意给定的52个整数中,总存在两个数它们的和或差能被100整除。
证明:设52个整数为
,
令
,则
的可能取值为0,1,2,……,99。
现将
分为51类:{0},{1,99},{2,98},……,{49,51},{50}(看为51个抽屉),
则根据抽屉原理,至少有2个
属于同一类,
假设
属于同一类,则或者
或者
,
若
,则
能被100整除,
若
,则
能被100整除。
证毕。
13.证明:(1)每年至少有一个13日是星期五。
(2)每年至多有三个13日是星期五。
证明:(假设1年365天)
(1)每年中共有12个13日,它们是1.13,2.13,3.13,…,12.13。
(反证法)假设它们都不是星期五,则是星期一、星期二、星期三、星期四、星期六、星期日之一(用mi表示)
因为2.13和3.13相差28天,3.13和11.13相差245天,都是7的倍数,因此这3天星期几相同,用m1表示星期几(星期天用7表示);
而1.13和10.13相差274天属于同一个星期几,用m2表示;
同理,4.13和7.13相差91天,同属于一个星期几,用m3表示;
9.13和12.13相差91天,同属于1个星期几,用m4表示;
且
(它们相差不是7的倍数,因此不会相等),
则剩下的3天5.13,6.13,8.13的星期几只能在剩下的两个mi中选,
根据抽屉原理,至少有2个的星期几相同,但是这时不可能的,因为这3天相隔都不是7的倍数,产生矛盾,因此必有一个13日是星期五。
(2)从(1)的讨论可知,至多只有3个月,它们两两之间的间隔天数都是7的整数倍,因此只有2.13,3.13,11.13可能同时为星期五,不可能有4个月的13日全为星期五。
14.设
是整数
的任意一个排列,证明:当n是奇数时,乘积
肯定是偶数。
证明:n为奇数时,
中有
个奇数,
个偶数,
则
这
个数中,必至少有1个是奇数,
从而
中,必至少有1个是偶数,
因此乘积
肯定是偶数。证毕。
17.在平面直角坐标系中任取5个整点(两个坐标都是整数),证明其中一定存在3个点,由其构成的三角形(包含3点在一条直线上)的面积是整数(可以为0)。
解:任一整点(a,b)的坐标只有如下4种可能:
(奇数,偶数),(奇数,奇数),(偶数,奇数),(偶数,偶数)。
根据抽屉原理,5个点中必至少有2个点的奇偶模式相同,
设(x1,y1),(x2,y2)是5个点中奇偶模式相同的那2个点,
则有2((x1-x2),2((y1-y2),故可设x1-x2=2k,y1-y2=2m。
再在剩下的3个点中任取一点(x3,y3),则这3点构成的三角形(的面积
是整数。
18.用4种颜色给平面上的完全图
(66个顶点,每个顶点间都有边连接)的边染色,每个边选一种颜色。证明,染色后必存在一个同色的
(即三角形)。
证明:就图中某个端点v0而言,跟其他的65个顶点联结,有65条边;
现在用4个颜色进行染色(看为4个抽屉),
则至少有17条边染同一种颜色,设该颜色为c1,
设这17条边对应的顶点为v1, v2, …, v17。
若v1, v2, …, v17中有两个顶点vi,vj,它们的连边(vi, vj)也染颜色c1,则这时(v0, vi, vj)就构成一个同色的三角形,
否则,v1, v2, …, v17中所有顶点的连边只能用剩下的3种颜色染之。
就v1而言,与其余16个顶点的16条连边用3种颜色染色,
则至少有6条边染同一种颜色,设为c2,
假设这6个顶点为v2,v3,v4,v5,v6,v7,
若v2,v3,v4,v5,v6,v7中有两个顶点vi,vj,它们的连边(vi, vj)也染颜色c2,则这时(v1, vi, vj)就构成一个同色的三角形,显然,若(vi, vj)染c1,则(v0, vi, vj)也构成一个同色三角形;
否则v2,v3,v4,v5,v6,v7中的连边只能用剩下的2种颜色染之,
就v2而言,与其余5个顶点的5条连边用2种颜色染色,
则至少有3条边染同一种颜色,设为c3,假设这3个顶点为v3,v4,v5,
若v2,v3,v4中有两个顶点vi,vj,它们的连边(vi, vj)也染颜色c3,则这时(v2, vi, vj)就构成一个同色的三角形,
否则v2,v3,v4的连边只能染最后一种颜色c4,这时(v2, v3, v4)就构成一个同色三角形。
� EMBED Visio.Drawing.11 ���
� EMBED Visio.Drawing.11 ���
第4页(共11页)
_1216418951.unknown
_1217535935.unknown
_1260390260.unknown
_1260398460.unknown
_1260398744.unknown
_1260398824.unknown
_1260399026.unknown
_1260399027.unknown
_1260398908.unknown
_1260398765.unknown
_1260398713.unknown
_1260398726.unknown
_1260398487.unknown
_1260393981.unknown
_1260398199.unknown
_1260398276.unknown
_1260398416.unknown
_1260398266.unknown
_1260394155.unknown
_1260398029.unknown
_1260398054.unknown
_1260394249.unknown
_1260394272.unknown
_1260394343.unknown
_1260394171.unknown
_1260394086.unknown
_1260394122.unknown
_1260394028.unknown
_1260390346.unknown
_1260392480.unknown
_1260393960.unknown
_1260392479.unknown
_1260390300.unknown
_1260390323.unknown
_1260390275.unknown
_1217539481.unknown
_1260389983.unknown
_1260390157.unknown
_1260390185.unknown
_1260390008.unknown
_1260389852.unknown
_1260389940.unknown
_1217539513.unknown
_1260389298.unknown
_1217536260.unknown
_1217537168.unknown
_1217537211.unknown
_1217539376.unknown
_1217536294.unknown
_1217535995.unknown
_1217536150.unknown
_1217535974.unknown
_1217535019.unknown
_1217535569.unknown
_1217535791.unknown
_1217535872.unknown
_1217535904.unknown
_1217535842.unknown
_1217535680.unknown
_1217535772.unknown
_1217535652.unknown
_1217535307.unknown
_1217535443.unknown
_1217535530.unknown
_1217535350.unknown
_1217535195.unknown
_1217535285.unknown
_1217535166.unknown
_1216419586.unknown
_1216420080.unknown
_1217534827.unknown
_1217534979.unknown
_1217535002.unknown
_1217534864.unknown
_1217530947.vsd
_1217532557.unknown
_1217534726.unknown
_1217532556.unknown
_1217531208.vsd
_1216420124.unknown
_1216420228.unknown
_1216420114.unknown
_1216419838.unknown
_1216420074.unknown
_1216419744.unknown
_1216419757.unknown
_1216419668.unknown
_1216419601.unknown
_1216419141.unknown
_1216419220.unknown
_1216419563.unknown
_1216419574.unknown
_1216419418.unknown
_1216419182.unknown
_1216419083.unknown
_1216419116.unknown
_1216419069.unknown
_1216415299.unknown
_1216417119.unknown
_1216418133.unknown
_1216418565.unknown
_1216418653.unknown
_1216418796.unknown
_1216418610.unknown
_1216418454.unknown
_1216418465.unknown
_1216418246.unknown
_1216418356.unknown
_1216417762.unknown
_1216418039.unknown
_1216418055.unknown
_1216417916.unknown
_1216417966.unknown
_1216417667.unknown
_1216417731.unknown
_1216417641.unknown
_1216415997.unknown
_1216416170.unknown
_1216416222.unknown
_1216416508.unknown
_1216416199.unknown
_1216416040.unknown
_1216416076.unknown
_1216416085.unknown
_1216416020.unknown
_1216415375.unknown
_1216415668.unknown
_1216415698.unknown
_1216415572.unknown
_1216415317.unknown
_1216415355.unknown
_1216415308.unknown
_1216414861.unknown
_1216415087.unknown
_1216415210.unknown
_1216415253.unknown
_1216415291.unknown
_1216415233.unknown
_1216415137.unknown
_1216415189.unknown
_1216415119.unknown
_1216414938.unknown
_1216415058.unknown
_1216415078.unknown
_1216414960.unknown
_1216414888.unknown
_1216414923.unknown
_1216414869.unknown
_1216414682.unknown
_1216414773.unknown
_1216414790.unknown
_1216414849.unknown
_1216414782.unknown
_1216414755.unknown
_1216414761.unknown
_1216414694.unknown
_1215672788.unknown
_1216414398.unknown
_1216414667.unknown
_1216414674.unknown
_1216414515.unknown
_1216022941.unknown
_1216023033.unknown
_1216023141.unknown
_1216023261.unknown
_1216023271.unknown
_1216023140.unknown
_1216023032.unknown
_1216023031.unknown
_1216022892.unknown
_1216022906.unknown
_1216022573.unknown
_1215672264.unknown
_1215672564.unknown
_1215672598.unknown
_1215672398.unknown
_1155273523.unknown
_1215672118.unknown
_1215672206.unknown
_1155446765.unknown
_1159906069.unknown
_1155413588.unknown
_1155414178.unknown
_1155274071.unknown
_1126985365.unknown
_1155272940.unknown
_1100720837.unknown
_1126963865.unknown
_1126963851.unknown
_1099318874.unknown