西安电子科技大学版组合数学习题答案习题5

习 题 五 习题五（抽屉原理） 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。不妨设 ， 从而有 。 因为由 ，由抽屉原理可知，在 中应至少有两个元素取值相同，不妨设是 ，则 · 若 ，则有 ，满足结论； · 若 ，则有 ，满足结论。 综上所述，结论必成立。证毕。 · 证法二： 显然，每组 中，必有两数字相同，共有 种模式， 其值或为０或为１，故共有 种选择。 现在有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点构成的三角形(的面积 是整数。 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