组合数学(西安电子科技大学(第二版))习题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个整数为：，不妨设，令，则，由抽屉原理知，必存在，使得，则 。证毕。 问题的一般描述：任取n1个整数，其中至少存在两数，其差是n的倍数。6一次考试采用百分制，所有考生的总分为10101，证明如果考生人数不少于202，则必有三人得分相同。证明：采用百分制，则所有可能的分数为，共101个分数，现人数不少于202，则平均每个分数有两个人得分相同。分情况讨论：（1）若有某些分数没有考生得该分数，则202名考生，可能的考生成绩最多100种，根据抽屉原理，必有三个的得分相同。（2）若有1个考生的分数与其他人都不同，则其余201名考试可能的分数只有100种，则必有三人的得分相同。 （3）若每个分数线都有两个人，则所有考生的总分为：，与题目矛盾。所以这种情况不可能存在。综上所述，必有三人得分相同。证毕。 方法二：反证法。假设没有三个考生考试成绩相同，因为分数的分布为0100分，共101种分数，若考生人数大于202人，则根据抽屉原理必然有三人考试成绩相同，矛盾；若考生人数恰好202个，要求没有三个考生考试成绩相同，则所有考生必然恰好两两得分相同。而此时所有考生的总分为：，矛盾。故结论成立。 方法三：此题的另一种理解是将10101个物品放入202个盒子，每个盒子最多放100个，也可以不放，则至少有三个盒子中所放物品个数相同。如若不然，至多有两个盒子的物品一样多，则只能恰好用去10100个物品，剩下一个物品，就无法处理，一旦将其放入某个有k个物品的盒子，那么，就有3个盒子放了k1个物品。 此问题的一般提法是：所有考生的总分为5050rt ，如果考生人数不多于101r人，则至少有r1人得分相同。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位二进制数视为一个37的方格棋盘，用红、蓝两色（分别用0、1表示）之一对每个方格进行染色，则问题变成：证明至少有4个格子同色，且此4个格子位于由若干个小方格组成的某个长方形的4个角上。也就是说必存在两行两列，其交叉处的4个格子同色001110001101010101011000110110由于颜色数比行数少一，故对每列而言，至少有两格同色。如图5.2.3（a），设第一列的前两行为红色，后一行为蓝色，则后6列中的任何一列的前两行都不能再为红色，否则即会出现4个同色格子构成长方形的情形，即结论成立。由此看出，两个红色方格同列的情形最多只能有3列。而图5.2.3（b）的染法，只能使得这样的列数最多为1列，其后每列最多只能有一个红格子，且各列红格子所处的行还不能相同。总之，对每种颜色，在某列中被用了两次的列最多为列。当颜色数为2时，这样的列最多只有26个，现在总列数为7，故由抽屉原理，必有某两列中相同的两行的4个格子所染颜色相同。9证明：把110这10个数随机地写成一个圆圈，则必有某3个相邻数之和大于或等于17。若改为126，则相邻数之和应大于或等于41。证明：设这10个数围成的圆圈为， 令， 则， 现在有10个数，故必存在某个。证毕。 同理，若是126，则同样可构造出3个相邻数之和， 且有， 故必存在某个。 一般情形： 已知n个正整数数，将其随机地写成一个圆圈，则必有某k个相邻数之和大于或等于M，那么，M10某学生准备恰好用11个星期时间做完数学复习题，每天至少做一题，一个星期最多做12题，试证必有连续几天内该学生共做了21道题。证明：11个星期总共有77天，每天做的题数设为， 则， 构造序列，则， 若存在某个，则问题得证。 否则，所有的，令集合， 则有， 集合A中共有154个数，每个数的取值在1153之间，由抽屉原理知，必有两个数相等。又时，从而，所以，相等的两个数必为，显然，故 。证毕。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个顶点，每个顶点间