组合数学(西安电子科技大学(第二版))习题5.doc

习 题 五
习题五（抽屉原理）
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。不妨设，
从而有。
因为由，由抽屉原理可知，在中应至少有两个元素取值相同，不妨设是，则
u 若，则有，满足结论；
u 若，则有，满足结论。
综上所述，结论必成立。证毕。

¨ 证法二：
显然，每组中，必有两数字相同，共有种模式，
其值或为０或为１，故共有种选择。
现在有7组，因为，由抽屉原理可知，必有２组数在相同的两行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点构成的三角形D的面积

是整数。

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）就构成一个同色三角形。

第11页（共11页）