初中数学竞赛专题复习 第四篇 组合 第24章 抽屉原理和容斥原理试题 新人教版

我带领班子成员及全体职工，积极参加县委、政府和农牧局组织的政治理论学习，同时认真学习业务知识，全面提高了自身素质，增强职工工作积极性，杜绝了纪律松散第24章抽屉原理和容斥原理24.1抽屉原理24.1.1在任意的61个人中，至少有6个人的属相相同解析因为一共有12种属相，把它看作12个抽屉，根据抽屉原理知，至少有6个人的属相相同评注抽屉原理又称鸽笼原理或狄里克雷原理这一简单的思维方式在解题过程中却可以有很多颇具匠心的运用抽屉原理常常结合几何、整除、数列和染色等问题出现许多有关存在性的证明都可用它来解决抽屉原理1 如果把件东西任意放入个抽屉，那么必定有一个抽屉里至少有两件东西抽屉原理2如果把件东西任意放人个抽屉，那么必定有一个抽屉里至少有女件东西，这里其中表示不超过的最大整数 ，例如，等等24.1.2从2，4，6，30这15个偶数中任取9个数，证明：其中一定有两个数之和是34解析把2，4，6，30这15个数分成如下8组（8个抽屉）；（2）（4，30），（6，28），（8，26），（10，24），（12，22），（14，20），（16，18）从2，4，6，30这15个数中任取9个数，即是从上面8组数中取出9个数抽屉原理知，其中一定有两个数取自同一组，这两个数的和就是3424.1.3在1，2，3， ，100这100个正整数中任取11个数，证明其中一定有两个数的比值不超过；，2，3，4，5，6，7，8，9，10，11，12，16，17，18，25，26，27，39，40，41，6061，62，91，92，93，100从1，2，100中任取11个数，即是从上面10组中任取11个数，由抽屉原理知，其中一定有两个数取自同一组，这两个数的比值不超过24.1.4求证：任给五个整数，必能从中选出三个，使得它们的和能被3整除解析任何数除以3所得余数只能是0、1、2，分别构造3个抽屉：0、1、2（1）若这五个自然数除以3后所得余数分别分布在这3个抽屉中，从这三个抽屉中各取1个，其和必能被3整除（2）若这5个余数分布在其中的两个抽屉中，根据抽屉原理，其中一个抽屉必包含有个余数，而这三个余数之和或为0，或为3，或为6，故所对应的3个整数之和是3的倍数（3）若这5个余数都能分布在其中的一个抽屉中，易知必有3个整数之和能被3整除24.1.5从1，2，3，20中，至少任取多少个数，才能使得其中一定有两个数，大的数是小的数的倍数解析从1，2，20中取11，12，20这10个数，其中没有一个数是另一个数的倍数把1，2，20分成如下10组：1，2，3，5，7，11，13，13，15，17，19，从中任取11个数，一定有两数取自同一组，于是大数便是小数的倍数所以，至少任取11个数才能满足题意24.1.6在不超过100的正整数中任取55个不同的数，在这55个数中：（1）是否一定有两个数的差等于11？（2）是否一定有两个数的差等于9？解析（1）不一定，例如，这55个数中，任意两数的差都不等于11（2）一定把1，2，100分成如下54组：1，10，2，11，9，18，19，28，81，90，91，100，92，93，99从中任取55个数，一定有两个数取自同一组，它们的差等于924.1.7证明：在任意的52个正整数中，一定可以找到两个数、，使得或能被100整除解析把这52个正整数都除以100，考虑52个余数，若其中有两个相同，则它们的差能被10整除，若其中任意两个都不相同，则它们的差能被100整除，若其中任意两个都不相同，把0，1，99分成如下51组：1，99，2，98，49，51，0，50从中任取52个数，车琮有两数（的余数）取自同一给，这两数的和或差能被100整除24.1.8某学校的初三年组的同学要从8名候选人中投票选举三好学生，规定每人必须从这8名候选人中任意选两名，那么至少有多少人参加投票，才能保证必有不少于5名同学投了相同的两个候选人的票？解析从8个人中任意选2人，不同的选法共有（种），即有28个抽屉由抽屉原理，当投票的人不少于人时，就能保证必有不少于5名同学投了相同两个候选人的票而当112个人投票时，不一定有不少于5名同学投了相同两个候选人的票所以，到少有113人投票时，能保证必有不少于5名同学投了相同两个候选人的票24.1.9在1，11，111，中，是否有2007的倍数？解析答案是肯定的考虑以下2007个数：1，11，111，若它们都不是2007的倍数，则它们除以2007所得的余数中一定有两个是相同的，不妨设为和，于是，而（2007，）=1，所以，这与1，11，111，都不是2007的倍数矛盾所以，在1，11，111，中，一定有2007的倍数24.1.10从任意给定的1999 个自然数中总可以找到个数，使得它们的和能被1999整除解析设1999个自然数为，且构造下列2000个和：0，因为任意一个自然数被1999除后，所得的余数可能是0，1，2，1998，共1999种所以可将上述2000个和按照被1999除后所得不同的余数分成1999个集合由抽屉原理可知，至少有两个和，不妨设为，它们属于同一个集合，即它们分别被1999除后所得的余数相同，那么它们的差能被1999整除从而本题得证24.1.11把圆周分成12段，将l，2，3，11，12这12个数任意写在每一段内，使每一段恰好有一个数字证明：一定存在连续的三段，它们的数字和至少是20解析如果记第1小段内填写的数是，第2小段内填写的数是第12小段内填写的数是，那么三个相邻小段填写的数字和可以有，这12种，并且12种情况中出现的所有数字和为由抽屉原理可知，至少有某个相邻的三段，它们的数字和至少是值得注意：本题中的三个相邻小段也可分成，这4种情况，这时它们的数字和为由抽屉原理可知，至少有某个相邻的三段，它们的数字和至少是24.1.12在个连续自然数1，2，3，中，任取出个数证明：在这个数中，一定有两个数，其中一个是另一个的倍数解析将这个连续自然数分成集合：1，3，5，A由此可见，这个数没有遗漏地被放在个集合中，并且同一个数决不会出现在两个不同的集合中因此，根据抽屉原理可知，不论用何种方式从中取出个数时，必定有至少两个数是出自同一个集合的，而同一个集合的两个数，大数必定是小数的倍数24.1.13从1，2，这个正整数中任取个数，证明其中一定存在两个数是互质的解析把1，2，这个焉整数分成如下组：1，2，3，4，从这组中任取个数，由抽屉原理知，其中一定有两个数取自同一组，同一组中的两个数是相邻的正整数，从而它们是互质的24.1.14把1，2，10按任意次序排成一个圆圈(1)证明：一定可以找到三个相邻的数，它们的和不小于18；(2)证明：一定可以找到三个相邻的数，它们的和不大于15解析 (1)设这10个数在圆周上排列为1，如图（a）由于，所以、这三个数中一定有一个数不小于（2）设这10个数在圆周上排列为，如图（b）由于，所以，、这三个数中一定有一个数不大于24.1.15在边长为1的正三角形中，任取7个点，其中任意三点不共线证明：其中必有三点构成的三角形的面积不超过解析如图所示，将正三角形的中心与三个顶点连起来把正三角形分成三个小三角形(3个抽屉)由抽屉原理知，必定有一个小三角形的内部或边界上至少有个点这三个点构成的三角形面积不超过该小三角形的面积，即不超过24.1.16在的长方形中，任意放置6个点，证明：一定可以找到两个点，它们的距离不大于解析我们要设法把的长方形分成5个部分(5个抽屉)，而且每部分中任意两点的距离不大于如图所示，把的矩形分成5个部分由勾股定理可以算得每个部分的任两点之间的距离不大于从而命题得证24.1.17求证：在任何凸边形中，总有一条对角线不与任何一条边平行解析凡是与某条边平行的对角线，称之为“好对角线”，由于对每一条边，最多有条对角线与之平行，因此凸边形的“好对角线”至多有条，但凸边形的对角线总数为于是由抽屉原理，知必定有某条对角线不与任何边平行对于凸边形，不难构造例子使所有对角线均为“好对角线”24.1.18证明：在任意6个人的集会上，或者有3个人以前彼此相识，或者有3个人以前彼此不相识解析在平面上用6个点、分别代表参加集会的6个人如果两人以前彼此认识，就在代表他们的两点间连一条实线；否则连一条虚线考虑点与其余各点连线，它们的线形不超过2种根据抽屉原理，可知其中至少有条连线同为实线，或同为虚线不妨设、均为实线如果、三条连线中有一条(不妨设为)也是实线，那么三角形三边均为实线，说明、代表的3个人以前彼此相识：如果、三条连线均为虚线，那么三角形三边均为虚线说明、代表的3个人以前彼此不相识不论哪种情形发生，都符合问题的结论24.1.19空间有6点，任何3点都是一个不等边三角形的顶点，求证：这些三角形中的一个三角形的最短边同时是另一个三角形的最大边解析设，是空间中6个已知点在每个三角形中，把最短边涂成红色，于是，每个三角形中必有一条边为红色，其余的边未涂色从每个点可作5条线段与其余已知点相连按抽屉原理，这5条线段中，或者至少有3条线段已被涂色，或者至少有3条线段还未涂色如果经过点的5条线段中至少有3条(例如，设为线段、)涂红，那么，在由这3条线段的另一顶点为顶点的中至少须有一边(最短边)涂红，设是边，那么的3边就都被涂红了如果经过点的线段中至少有3条未被涂红（例如设为线段、），由于、中每个都至少有一边是红的因此，只能是线段、全是红的，即的各边都是红色的24.1.20将正十三边形的每个顶点染成黑色或染成白色，每顶点染一色求证：存在三个同色顶点，它们刚好成为一个等腰三角形的顶点解析设13个顶点依次为，若13个顶点都染成黑色或都染成白色，则结论显然成立故只需考虑13个顶点中有染黑色也有染白色的情形这时必有相邻两顶点同色，不妨设、同色，现考虑、这五个顶点，由抽屉原理知其中必有三顶点同色，这又分为下列三种情形：（1）、中有三点同色，又、同色，故、同色或、同色这时或为三顶点同色的等腰三角形（2）、同色，这时为三顶点同色的等腰三角形（3）、同色，这时为三顶点同色的等腰三角形24.1.2115个席位同等地围绕着圆桌安排，席上有15个客人的名片，客人们没有注意这些名片，直到他们坐下来，才发觉没有一个人坐在他自己的名片前面证明：可以转动圆桌使得至少有两个客人同时对号入座解析对于每个客人，都有一种转动圆桌的方式，使他对上自己的名片现在先把席位按逆时针方向依次由1到15编号，每按逆时针方向转动一次圆桌，使名片对到下一个席位上，即1号上的名片对到2号席位，2号上的名片对到3号席位15号上的名片对到1号席位那么按这种方式转动15次后，所有的名片又对到初始的席位上所以，一共有14种有效的转动，因为有15个客人，根据抽屉原理，必定有某种转动至少可容许有两个客人对上号24122在52张扑克牌上任意写上互不相同的正整数证明：一定存在四张扑克牌，将其上的四个数仅用减号、乘号和括号适当组合成一个式子，其值是1989的倍数解析因为而对任给的52个互异的正整数中，至少有两个数被51除后的余数相同，设这两个数为、，且，那么 （为整数）在取出、后的50个互异的正整数中，又至少有两个数，不妨设、，且，它们分别被39除后的余数相同，即（为整数）因此，在给出的52个互异的正整数中，一定有四个整数、组成一个式子：24.1.23证明在任意11个无穷小数中，一定可以找到两个小数，它们的差或者含有无穷多个数字0，或者含有无穷多个数字9解析由于每一个数位上的数字只有0，1，2，9这10种情况，因此11个数中必有两个数在这个数位上有相同的数字记11个无穷小数为，把这11个数分成如下55个二元组(每两个一组)：，这55个二元组作为55个抽屉，现将无穷多个数1，2，3，放进这些抽屉，规则是：若小数点后第位上与相同，则数就放入中例如，与的第7位上的数相同，则7就放入这个抽屉里由抽屉原理知，这55个(有限个)抽屉中必有一个抽屉，它含有无穷多个数，不妨设(，)这个抽屉里含有无穷多个数，这就说明，这两个无穷小数有无穷多位相同考虑与的差，在数字相同的数位上，差的数字为0或9由于0与9的总个数有无穷多个，因此至少有一个出现无穷多次，从而与的差中，或者有无穷多个数字0，或者有无穷多个数字9评注 本题先后三次用了抽屉原理，请读者仔细玩味24124一个书架有五层，从下到上依次称为第1层，第2层，第5层今把15册图书分放到书架的各层上，有些层可不放证明：无论怎样放法，书架每层上的图书册数，以及相邻两层上图书册数之和，这些数中至少有两个是相等的解析用表示第层所放的图书册数，2，3，4，5如果有某个，那么结论显然成立因此可设，2，5考虑下面两种情况：(1)，中有两个数相等，则结论已经成立（2），各不相等，因，所以，必各取1、2、3、4、5之一但是，这4个数不可能同时包含7、8、9这三个数事实上，若7、8、9都出现，则只可能是，或，前者表示放5册书的那一层与放2、3、4册的各层均相邻，不可能后者表示放4、5册书的两层既要相邻又要不相邻，也不可能因此，下面9个数：，至多能取8个不同的值由抽屉原理知，其中必有两个是相等的，从而命题得证24.1.25一个由个方格组成的正方形表格，其中填满1，2，3，等数，且在任一行、任一列都能遇到所有这些数字若表格中的数字关于对角线是对称的，求证：当是奇数时，在对角线上的那些方格中将会遇到所有的1，2，这些数字解析如图，由于在表格的每一行、每一列都出现l，2，各数，所以任一行(或列)中，每个数只出现一次，于是表格中有个1，个2，个又由于整个表格关于对称，因此除对角线上的数外，任何一个数都将在其对称位置出现，如图中，等数因此除对角线外表格中1，2，等数各有偶数个当为奇数时，表格中共有奇数个1，奇数个2，奇数个所以对角线上出现1，2，且1到个数都必将出现，但对角线上只有个格子，因此，所有的数在对角线上都恰好出现一次24126一个半径为1的圆内或边界上有6个点，求证：必定有两点之间距离不大于1解析不妨设6个点为、如图，设、将六等分，且可让落在上（旋转可达）对于六个扇形（圆心角，半径为1），其中一个内有两点（包括边界）、，则这是因为，（这里不妨设）于是由前知，、已不能落在扇形与上，于是这五个点均落在剩下的四个扇形中，由抽屉原理，知必有两点落在同一扇形内或边界上，因此仍有距离不大于1，结论成立24.1.27一个棋手为参加一次锦标赛将进行77天的集训，他每天至少下一盘棋，而每周至多下12盘棋证明一定存在一个正整数，使得他在这77天里有连续的一天恰好下了21盘棋解析用表示这位棋手从第1天到第天(包括第天)下棋的总盘数，2，77由于每天至少下一盘棋，所以又因为每周至多下12盘棋，所以，所以考虑下面154个正整数：，其中最小的是，最大的不超过因此这154个正整数中必定有两个是相等的由于，所以必定存在，使得令，那么该棋手在第，这连续的天中恰好下了21盘棋24.2容斥原理24.2.1一个班有45个学生，参加数学课外小组的有30人，参加语文课外小组的有25人，并且每一个人都至少参加了一个课外小组问：这个班中参加了两个课外小组的同学有多少个?解析我们画一个图帮助思考，如图所示，画两个相交的圆，其中一个圆表示参加数学课外小组的同学，另一个圆表示参数学课外小组语文课外小组加语文课外小组的同学，那么，两个圆的内部共有45个同学，两个圆的公共部分就是参加了两个课外小组的同学因为参加数学课外小组的同学有30人，参加语文课外小组的25人，但，这是因为两个课外小组都参加的同学被重复计算了两次，所以，两个课外小组都参加的同学有（人）所以，这个班中参加了两个课外小组的同学有10个评注本题用的方法是容斥原理1容斥原理1：或的元素个数的元素个数的元素个数一既是又是的元素个数2422在1，2，100这100个正整数中，不是5的倍数，也不是7的倍数的数有多少个?解析 在1，2，100中，5的倍数有5，10，15，100共20个，7的倍数有7，14，21，98共14个，其中既是5的倍数又是7的倍数的数有35，70共2个根据容斥原理1得，在1，2，100中，5或者7的倍数有（个）从而，在l，2，100这100个正整数中，不是5的倍数，也不是7的倍数的数有（个）242.3某班40位同学在一次数学测验中，答对第一题的有23人，答对第二题的有27人，这两题都答对的有17人，问有多少个同学这两题都不对?解析根据容斥原理l得：这两题都不对的同学有（人）2424某校对五年级100名同学进行学习兴趣调查，结果有58人喜欢语文，有38人喜欢数学，有52人喜欢外语而且喜欢语文和数学(但不喜欢外语)的有6人，喜欢数学和外语(但不喜欢语文)的有4人，三科都喜欢的有12人，而且每人至少喜欢一科问有多少同学只喜欢语文?有多少同学喜欢语文和外语(但不喜欢数学)?解析如图所示，设喜欢语文和外语(但不喜欢数学)的有人于是，喜欢数学和语文的有个人，喜欢数学和外语的有个人，喜欢语文和外语的有个人所以，解得即喜欢语文和外语(但不喜欢数学)的有14人所以，只喜欢语文的同学有（人）所以，有26个同学只喜欢语文，有14个同学喜欢语文和外语(但不喜欢数学)评注本题用的方法是容斥原理2容斥原理2：或或的元素个数的元素个数的元素个数的元素个数既是又是的元素个数一既是又是的元素个数一既是又是的元素个数+既是又是又是的元素个数24.2.5全班有25个学生，其中17人会骑自行车，13人会游泳，8人会滑冰，这三项运动项目没有人全会至少会这三项运动之一的学生数学成绩都及格了，但又都不是优秀如果全班有6个人数学不及格，问：(1)全班数学成绩优秀的有几名?(2)全班有几个人既会游泳又会滑冰?解析(1)至少会一项运动的人有人，因为没有人会全部三项运动，因此至少会三项运动之一的人假使每人都会两项，也要(人)，这些人数学都及格了，再加上数学不及格的6人，正好是25人，所以没有人数学优秀(2)如图所示：根据题意可得，；其中表示既会骑自行车又会游泳的学生人数，表示既会骑自行车又会滑冰的同学的人数，表示既会游泳又会滑冰的同学的人数所以，故没有人数学优秀；全班有2人既会游泳又会滑冰2426在1到100个自然数中，既非3的倍数也不是4与5的倍数的数有多