资源描述
第四篇组合第23章组合计数23.1加法原理和乘法原理23.1.1有800名乒乓球选手参加淘汰赛，需要进行多少场比赛才能决出冠军？解析由于每场比赛淘汰一名选手，即比赛的场数与被淘汰的选手人数是相等的要决出冠军，需淘汰799名选手，所以需要进行799场比赛23.1.2一个小朋友有8块相同的巧克力（即不计顺序），他每天至少吃一块，直至吃完，问共有多少种不同的吃巧克力的方案？解析将8块巧克力排成一行如果第一天吃2块，第二天吃1块那么，就在第2块后面画一条竖线，这后面的第1块的后面（即第3块的后面）画一条竖线这样，吃巧克力的方案就与在8块巧克力的7个空隙里添加竖线对应起来由于每个空隙里加以加1根竖线，也可以不加，所以，由乘法原理知，加竖线的方法共有（种）从而吃巧克力的方案也就有128种23.1.3有多少个有序整数对(,)满足？解析我们把这个问题分成6种情况：，1，2，5当时，（，）（0，0）；当时，(,)=(0,)，(0,)，(1,0)，(,0)；当时，(,)=(,)，(,1)，(1,)，(1,1)；当时，不可能；当时，不可能；当时，(,)=(0,)，(0,2)，(,0)，(2,0)；当时，(,)=(,)，(,1)，(,)，(,2)，(,)，(1,2)，(2,)，(2,1)由加法原理知，满足题设的有序数对共有（个）23.1.4利用数字、2、3、4、5共可组成（1）多少个数字不重复的三位数？（2）多少个数字不重复的三位偶数？（3）多少个数字不重复的偶数？解析（1）百位数有5种选择；十位数有4种选择；个位数有3种选择，所以共有个数字不重复的三位数（2）先选个位数，共有两种选择：2或4在个位数选定后，十位数还有4种选择；百位数有3种选择所以共有个数字不重复的三位偶数（3）分为5种情况：一位偶数，只有两个：2和4二位偶数，共有8个：12，32，42，52，14，24，34，54三位偶数由上述（2）中求得的为24个四位偶数共有：个括号外面的2表示个位数有2种选择（2或4）五位偶数共有：个由加法原理，偶数的个数共有（个）23.1.5从1到300的正整数中，完全不不含有数字3的有多少个？解析1将符合要求的正整数分为以下三类：（1）一位数，有1、2、4、5、6、7、8、9共8个6、7、8、9八种情形，在个位上出现的数字除以上八个数字外还有0，共9种情形，故二位数有个（3）三位数，在百位上出现的数字有1，2两种情形，在十位、个位上出现的数字则有0、1、2、4、5、6、7、8、9九种情形，故三位数有个因此，从1到300的正整数中完全不含数字3的共有个解析2将0到299的整数都看成三位数，其中数字3不出现的，百位数字可以是0、1或2三种情况，十位数字与个位数均有九种，因此除去0共有个23.1.6一个班级有30名学生（1）从中选出2人，一个担任班长，一个担任副班长，共有多少种不同的选法？（2）从中选2个人去参加数学竞赛，有多少种不同的选法？解析（1）从30个人中选1个人担任班长，有30种选法，再从剩下的29个人中选1个人担任副班长，有29种选法，则由乘法原理知，共有不同的选法为（种）（2）从30个人中选两人有种选法，但由于选出甲、乙去比赛和选出乙、甲去比赛是相同的情况，因此不同的选法共有（种）23.1.7在小于10 000的正整数中，含有数字1的数有多少个？解析不妨将1至9999的正整数均看作四位数，凡位数不到四位的正整数在前面补0，使之成为四位数先求不含数字1的这样的四位数共有几个，即有0、2、3、4、5、6、7、8、9这九个数字所组成的四位数的个数，由于每一位都有9种写法，所以，根据乘法原理，由这九个数字组成的四位数个数为其中包括了一个0000，这不是正整数，所以比小的不含数字1的正整数有个，于是，小于10 000且含有数字1的正整数共有个23.1.8在1到9999中，有多少个整数与4567相加，至少在一个数位中发生进位？解析将0到9999这10 000个整数都看成四位数，即位数不中四位的，在左面添0补足四位考虑这些四位数中，有多少个在与4567相加时不发生进位这样的数，千位数字有0、1、2、3、4、5这6种可能；百位数字有0、1、2、3、4这5种可能；十位数字有0、1、2、3这4种可能；个位数字有0、1、2这3种可能所以这样的数共有（个）其中包括0所以，在到9999中，与4567相加产生进位的整数有（个）23.1.19在1到1999这1999个自然数中，取4的倍数与7的倍数各一个相加，一共可得到多少个不同的和解析在1到1999这1999个自然数中，有4的倍数499个，它们是4，8，12，1992，1996；有7的倍数285个，它们是7，14，21，1988，1995可得到的和最小为，最大为，介于11至3991之间的自然数，有一部分得不到例如：12、13、14、16、17、20、21、24、28不能得到，下面能依次得到，反过来，不能得到的数还有3990、3989、3988、3986、3985、3982、3981、3978、3974不能得到的数共有（个）所以可得到的不同的和共有（个）2.3.1.10600有多少个不同的正约数（包括1和600）?解析将600质因数分解，有一个正整数是600的约数的弃要条件是具有的形式，其中、是整数且，由于有种选择：0、1、2、3；有种选择：0、1；有种选择：0、1、2，故由乘法原理知，这样的有（个）评注一般地，若一个正整数的质因数分解式为其中，是互不相同的质数，是正整数，则的不同正约数的个数为23.1.11在20000与70000之间，有多少个数字不重复的偶数？解析设是满足要求的偶数，那么只能取2、3、4、5、6，只能取0、2、4、6、8（1）若取2、4、6之一，即有3种选法，此时有种选法，、分别有8、7、6种选法，由乘法原理知，不重复的偶数有（个）（2）若取3、5之一，则有2种选法，有5种选法，、分别有8、7、6种选法，由乘法原理知，此时不重复的偶数有（个）最后，由加法原理知，满足题意的偶数共有（个）评注在很多计数问题中，都是加法原理和乘法原理结合在一起用的23.1.12求至少出现一个数字6，而且是3的倍数的五位数的个数解析设满足要求的五位数为由于3整除的充要条件是，所以分情况讨论如下：（1）从左向右看，若最后一个6出现在第5位，即，则、可以从0，1，2，9这10个数字中任取1个，为了保证，只有3种可能（例如，则只能取2，5，8之一，等等），由乘法原理，五位数中最后一位是6，且是3的倍数的数有（个）（2）从左向右看，最后一个6出现在第4位，即，于是只有9种可能（因为），、各有10种可能，为了保证，只有3种可能，由乘法原理，这一类的五位数有（个）（3）从左向右看，最后一个6出现在第3位，即，则、均有9种可能，有10种可能，有3种可能，这类五位数有（个）（4）从左向右看，最后一个6出现在第2位，则、均有9种可能，有3种可能，所以这类五位数有（个）（5）从左向右看，最后一个6出现在第1位，即，则、均有9种可能，为了保证，只有3种可能，从而这类五位数有（个）最后，由加法原理知，五位数中至少出现一个6，且是3的倍数的数有（个）23.1.13将1，2，3，4，5这五个数字排成一排，最后一个数是奇数，且使得其中任意连续三个数之和都能被这三个数中的第一个数整除，问：满足要求的排法有多少种？解析设，是1，2，3，4，5的一个满足要求的排列首先，对于，不能有连续的两个都是偶数，否则，这两个之后都是偶数，与已知条件矛盾又如果是偶数，是奇数，则是奇数，这说明一个偶数后面一定要接两个或两个以上的奇数，除非接的这个奇数是最后一个数所以，只能是：偶，奇，奇，偶，奇，有如下5种情形满足条件：2，1，3，4，5；2，3，5，4，1；2，5，1，4，3；4，3，1，2，5；4，5，3，2，123.1.14由35个单位小正方形组成的长方形中，如图所示，有两个“*”，问包含两个“*”在内的小正方形组成的长方形（含正方形）共有多少个？解析含两个“*”的矩形，与第二、三两行有公共部分它们可能与第一行有公共部分，也可能没有公共部分，即分为两类：每一类中的矩形，可能与四、五两行都有公共部分，或都没有公共部分，或仅与第四行有公共部分而与第五行没有公共部分，即又分为三类，这样，从行考虑共有类同样，考虑列，矩形可能与第一、二列都有公共部分，或都没有公共部分，或仅与第二列有公共部分，共三类而与第五、六、七列的关系则有四列(都有公共部分，都没有公共部分，仅与第五列有公共部分，与第五、六列有公共部分而与第七列无公共部分)所以，由乘法原理，含两个“*”的矩形共有（个）23.1.15设有红、黑、白三种颜色的球各10个现将它们全部放入甲、乙两个袋子中，要求每个袋子里三种颜色球都有，且甲乙两个袋子中三种颜色球数之积相等，问共有多少种放法解析设甲袋中的红、黑、白三种颜色的球数为、，则有、，且，即，于是有因此，中必有一个取不妨设，代入（1）式，得到此时，可取1，2，8，9（相应地取9，8，2，1），共9种放法同理可得或者时，也各有9种放法，但有时两种放法重复因此可得共有种放法23.1.16设正整数和互质问：有多少个非负整数不能表示成（和是非负整数）的形式？解析首先，由于、互质，所以下面个数，除以所得的余数不同事实上，若，则，所以，矛盾所以这个数中一定有一个除以余数为0，设这个数为，于是可设，即恰有一组满足的整数解（，）设与数组（，）依上述规律对应，即，与的数组（，）春风一度的整数称为“好的”；否则称为“坏的”若与（，）对应，即，则因为，且与中恰有一个是非负的，所以，与（，）对应，且与中恰有一个是好的，一个是坏的所以在0，1，2，中好数与坏数一一对应，从而其中的坏数有（个）当，则是坏数（显然），故大于的数均为好数由此得坏数即不能表为（，为非负整数）的非负整数有个23.1.17把1，2，3，2012这2012个正整数随意放置在一个圆周上，统计所有相邻三个数的奇偶性得知：三个数全是奇数的600组，恰好两个奇数的有500组，问：恰好一个奇数的有几组？全部不是奇数的有几组？解析设恰好1个奇数的有组，则全部不是奇数的有将圆周上的数从某个数开始，依次计为，令则，再令其中，2，于是，解得恰好一个奇数的有218组，全部不是奇数的有组23.2几何计数23.2.1如图所示，数一数图中有多少条不同的线段？解析对于两条线段，只要有一个端点不同，就是不同的线段，我们以左端点为标准，将线段分5类分别计数；（1）以为左端点的线段有、共5条；（2）以为左端点的线段有、共4条；（3）以为左端点的线段有、共3条；（4）以为左端点的线段有、共2条；（5）以为左端点的线段只有一条所以，不同的一线段一共有（条）评注般地，如果一条线段上有个点（包括两个端点）那么这个点把这条线段一共分成的线段总数为23.2.2如果一条线段上有个点（不包括两个端点和）它们共有210条不同的线段，求的值解析线段上共有个点（包括端点），所以不同的线段有条所以，解得23.2.3图中有多少个三角形？解析以为一边的三角形有、共5个；以为一边的三角形还有4个（前面已计数过的不再数，下同），它们是、；以为一边的三角形有、共3个；以为一边的三角形有、共2个；以为一边的三角形有一个，所以，共有三角形（个）23.2.4图中一共有多少个长方形？解析图中长的一边有5个分点（包括端点），所以，长的一边上不同的线段共有（条），同样，宽的一边上没的线段也有10条所以，共有长方形（个）23.2.5图中所有长方形的面积和是多少？解析因为长的一边上的10条线段分别为5、17、25、26、12、20、21、8、9、1，宽的一边上的10条线段长分别为2、6、12、16、4、11、14、7、10、3，所以，所有长方形面积和为23.2.6图中有多少个三角形？解析把图中最小的三角形看作基础三角形，分类计数含1个基础三角形的三角形共有16个；含2个基础三角形的三角形共有16个；含4个基础三角形的三角形共有8个；含8个基础三角形的三角形共有4个；因此，图中共有三角形（个）23.2.7图中有多少个梯形？解析设图中的长为个单位先计算底与平行且上底小、下底大的梯形的个数下底长是5的梯形有（个）（即梯形，）下底长是4的梯形有（个），其中下底可为，对于每一个这样的下底、上底都有三种可能类似地，下底的长为3的梯形有（个）下底的长为2的梯形有（个）因此，底与平行且下底大于上底的梯形有（个）再计算底与平行且下底大于上底的梯形有（个）再计算底与平行且上底大于下底的梯形，易知有（个）底与平行，且左边底大于右边底的梯形有个；左边底小于右边底的梯形有个，因此共有（个）底与平行的梯形也有36个所以，图中共有梯形（个）评注本题“分类”要全，不要遗漏了底与或平行的梯形23.2.8图中共有多少个三角形？解析显然三角形可分为尖向上与尖向下两大类，两类中三角形的个数相等尖向上的三角形双可分为6类：最大的三角形1个（即）；第二大的三角形有（个）；第三大的三角形有（个）；第四大的三角形有（个）；第五大的三角形有（个）；最小的三角形有（个）注意在外面还有三个最小的尖向上的三角形（左、右、下各一个），所以最小的三角形不是21个而是24个于是尖向上的三角形共（个）图中共有三角形（个）23.29图中有多少个等腰直角三角形？解析图中有个点在每点标一个数，它等于以这点为直角顶点的等腰直角三角形的个数因此由对称性，共有等腰直角三角形（个）23.2.10（1）图（a）中有多少个三角形？（2）图（b）中又有多少个三角形？解析（1）图（a）中有6条直线一般来说，每3条直线能围成一个三角形，但是这3条直线如果相交于同一点，就不能围成三角形了从6条直线中选3条，有种选法，每次选出的3条直线围成一个三角形，但是在图（a）中，每个顶点处有3条直线通过，它们不能围成三角形，因此，共有个三角形（2）图（b）中有7条直线，从7条直线中选3条，有种选法每不过同点的3条直线构成一个三角形（b）中，有2个顶点处有3条直线通过，它们不能构成三角形，还有一个顶点有4条直线通过，因为4条直线中选3条有4种选法，即能构成4个三角形，现在这4个三角形没有了，所以，图（b）中的三角形个数是（个）评注从6条直线中选3条，第一条有6种选法，第二条5种选法，第三条有4种选法，共有种选法，但是每一种被重复计算了6次，例如，实际上是同一种，所以，不同的选法应为种23.2.11问8条直线最多能把平面分成多少部分？解析1条直线最多将平面分成2个部分；2条直线最多将平面分成4个部分；3条直线最多将平面分成7个部分；再在添上第4条直线，它与前面的3条直线最多有3个交点，这3个交点将第4条直线分成4段，其中每一段将原来所在平面部分一分为二，如图，所以4条直线最多将平面分成个部分完全类似地，5条直线最多将平面分成个部分；6条直线最多将平面分成个部分；7条直线最多将平面分成个部分；8条直线最多将平面分成个部分评注一般地，条直线最多将平面分成个部分23.2.12平面上5个圆最多把平面分成多少个部分？解析1个圆最多能把平面分成2个部分；2个圆最多能把平面分成4个部分；3个圆最多能把平面分成8个部分；现在加入第4个圆，为了使分成的部分最多，第4个圆必须与前面3个圆都有两个交点，如图所示因此得6个交点，这6个交点将第4个圆的圆周分成6段圆弧，而每一段圆弧将原来的部分一分为二，即增加了一个部分，于是，4个圆最多将平面分成个部分同样道理，5个圆最多将平面分成个部分所以，5个圆最多将平面分成22个部分说明用上面类似的方法，可以计算出个圆最多分平面的部分数为23.2.13平面上5个圆和一条直线，最多能把平面分成多少个部分？解析首先，由上题可知，平面上5个圆最多能把平面分成22个部分，现在加入一条直线，由于一条直线最多与一个圆有两个交点，所以一条直线与5个圆最多有10个交点10个点把这条直线分成了11段，其中9段在圆内，2条射线在圆外，9条在圆内的线段把原来的部分一分为二；圆外只增加了一个部分所以，总共增加了10个部分因此，5个圆和1条直线，最多将平面分成个部分23.2.14三角形内部有2008个点，以顶点、和这2008个点为顶点能把原三角形分割成多少个小三角形?解析设内部的个点能把原三角形分割成个小三角形，我们考虑新增加一个点之后的情况：(1)若点在某个小三角形的内部，如图(a)，则原小三角形的三个顶点连同将这个小三角形一分为三，即增加了两个小三角形；(2)若点在某两个小三角形公共边上，如图(b)则这两个小三角形的顶点连同点将这两个小三角形分别一分为二，即也增加了两个小三角形所以，内部的个点把原三角形分割成的小三角形个数为易知，于是，将上面这些式子相加，得所以，当时，三个顶点、D和这2008个内点能把原三角形分割成个小三角形23.2.15平面上有100条直线，其中有20条是互相平行的，问这100条直线最多能将平面分成多少部分？解析1首先，这20条平行线将平面分成21个部分设另加上条直线，连同这20条平行线最多可将平面分成个部分，则这是因为当再加入第条直线后，它与前条直线最多有个交点，从而这条直线被分成了段（其中有两段是射线），每一段将原来的部分一分为二，即增加了个部分所以，把上面的后个等式相加，得易知，故所以所以，这100条直线最多将平面分成了4861个部分解析2解法1是先从平行线入手，现在我们先从80条互不平行的直线入手一般地，设平面上条直线最多可将平面分成个部分，则（见题23.2.11）所以，80条直线最多将平面分成3241个部分现在再加入平行线每加入一条平行线，它与前面的直线最多有80个交点，从而增加81个部分，于是加入20条平行线后最多增加个部分因此，这100条直线最多将平面分成个部分23.2.16圆周上有个点，每两点连一条弦，如果没有三条弦交于圆内一点，问：这些弦在圆内一共有多少个交点？解析圆周上每4点构成一个凸四边形，它的两条对角线（弦）交于一点（如图），因此第4点对应于圆内一个交点由于没有三条弦交于圆内一点，所以不同的4点对应于圆内的不同交点反应过一，设点是弦与的交点，则与4点在、对应所以，交点的个数就是圆周上个点中取4点的不同的取法总数，即评注最后的答案中要除以，理由同题23.2.1023.2.17圆周上有8个点，如图所示（1）从出发将它们连结成一条在圆内不相交的折线（由7条线段组成，例如折线就是满足要求的一条），共可得多少条不同的折线？（2）如果可以从这8点中的任一点出发，共可得多少条不同的拆线？解析（1）从出发连第1条线段时，只有两种连法：或（否则，若连，则与、分布在两边，要每个顶点都连到，必定与相交）；接着连第2条线段时，也只有两种连法连第6条线段时，有两种连法，连最后一条线段时，只有一种连法，所以由乘法原理知，不同的折线共有（条）（2）由（1）知，从8个点中的每一点（，2，8）出发，可以有64条不同的折线，从而可得条折线，但是对其中的每一条折线，将它的起点和终点都作为出发点重复算了一次，所以应除以2，故不同的折线共有（条）23.2.18在平面上给出条直线，且它们中的任何两条不平行，任三条不共线，证明：这些直线把平面分成的各部分中，三角形个数不少于解析研究已知直线的所有交点我们证明，这些点都在不多于两条已知直线的同一旁假设所有这些交点都在三条已知直线的同一旁，这三条直线构成三角形，第四条直线不能仅与这个三角形的边相交，也就是它至少与一条边的延长线相交为了确定起见，设它与从点出发的边的延长线相交于某点这时点和在直线的两旁，得出矛盾因此至少有条直线，它的两旁都有交点如果我们在由直线所给出的半平面上选取邻近的交点，那么这个点是毗连直线的三角形的顶点这样一来，有不少于条直线，毗连它们每一条至少有两个三角形，并且有两条直线，毗连它们每一条至少有一个三角形，因为每个三角形恰毗连三条直线，所以有不少于个三角形15
展开阅读全文