由莲山课件提供http://www.5ykj.com/ 资源全部免费
第四篇 组 合
第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种选择,所以共有个数字不重复的三位数.
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
(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种可能.所以这样的数共有
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
(个).
其中包括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.10★600有多少个不同的正约数(包括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种选法,由乘法原理知,不重复的偶数有
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
(个).
(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这五个数字排成一排,最后一个数是奇数,且使得其中任意连续三个数之和都能被这三个数中的第一个数整除,问:满足要求的排法有多少种?
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
解析 设,,,,是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,1.
23.1.14★★★由35个单位小正方形组成的长方形中,如图所示,有两个“*”,问包含两个“*”在内的小正方形组成的长方形(含正方形)共有多少个?
解析 含两个“*”的矩形,与第二、三两行有公共部分.它们可能与第一行有公共部分,也可能没有公共部分,即分为两类:
每一类中的矩形,可能与四、五两行都有公共部分,或都没有公共部分,或仅与第四行有公共部分而与第五行没有公共部分,即又分为三类,这样,从行考虑共有类.
同样,考虑列,矩形可能与第一、二列都有公共部分,或都没有公共部分,或仅与第二列有公共部分,共三类.而与第五、六、七列的关系则有四列(都有公共部分,都没有公共部分,仅与第五列有公共部分,与第五、六列有公共部分而与第七列无公共部分).
所以,由乘法原理,含两个“*”的矩形共有(个).
23.1.15★★设有红、黑、白三种颜色的球各10个.现将它们全部放入甲、乙两个袋子中,要求每个袋子里三种颜色球都有,且甲乙两个袋子中三种颜色球数之积相等,问共有多少种放法.
解析 设甲袋中的红、黑、白三种颜色的球数为、、,则有、、,且
, ①
即
, ②
于是有.因此,,中必有一个取.不妨设,代入(1)式,得到.
此时,可取1,2,…,8,9(相应地取9,8,…,2,1),共9种放法.同理可得
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
或者时,也各有9种放法,但有时两种放法重复.因此可得共有种放法.
23.1.16★★★★设正整数和互质.问:有多少个非负整数不能表示成(和是非负整数)的形式?
解析 首先,由于、互质,所以下面个数
,,,…,
除以所得的余数不同.
事实上,若,,则,,所以,矛盾.
所以这个数中一定有一个除以余数为0,设这个数为,,于是可设,即恰有一组满足的整数解(,).
设与数组(,)依上述规律对应,即,.与的数组(,)春风一度的整数称为“好的”;否则称为“坏的”.
若与(,)对应,即,,则
.
因为 ,
且与中恰有一个是非负的,所以,与(,)对应,且与中恰有一个是好的,一个是坏的.所以在0,1,2,…,中好数与坏数一一对应,从而其中的坏数有
(个).
当,则是坏数(显然),故大于的数均为好数.由此得坏数即不能表为(,为非负整数)的非负整数有个.
23.1.17★★★把1,2,3,…
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
,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条不同的线段,求的值.
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
解析 线段上共有个点(包括端点),所以不同的线段有条.所以
,
解得.
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★★图中有多少个三角形?
解析 把图中最小的三角形看作基础三角形,分类计数.
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
含1个基础三角形的三角形共有16个;
含2个基础三角形的三角形共有16个;
含4个基础三角形的三角形共有8个;
含8个基础三角形的三角形共有4个;
因此,图中共有三角形
(个).
23.2.7★★★图中有多少个梯形?
解析 设图中的长为个单位.先计算底与平行且上底小、下底大的梯形的个数.
下底长是5的梯形有(个)(即梯形,,,).
下底长是4的梯形有(个),其中下底可为,,,对于每一个这样的下底、上底都有三种可能.
类似地,下底的长为3的梯形有
(个).
下底的长为2的梯形有
(个).
因此,底与平行且下底大于上底的梯形有
(个).
再计算底与平行且下底大于上底的梯形有(个).
再计算底与平行且上底大于下底的梯形,易知有
(个).
底与平行,且左边底大于右边底的梯形有个;左边底小于右边底的梯形有个,因此共有
(个).
底与平行的梯形也有36个.
所以,图中共有梯形
(个).
评注 本题“分类”要全,不要遗漏了底与或平行的梯形.
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
23.2.8★★★图中共有多少个三角形?
解析 显然三角形可分为尖向上与尖向下两大类,两类中三角形的个数相等.尖向上的三角形双可分为6类:
最大的三角形1个(即);
第二大的三角形有(个);
第三大的三角形有(个);
第四大的三角形有(个);
第五大的三角形有(个);
最小的三角形有
(个).
注意在外面还有三个最小的尖向上的三角形(左、右、下各一个),所以最小的三角形不是21个而是24个.
于是尖向上的三角形共
(个).
图中共有三角形
(个).
23.29★★★图中有多少个等腰直角三角形?
解析 图中有
个点.在每点标一个数,它等于以这点为直角顶点的等腰直角三角形的个数.因此由对称性,共有等腰直角三角形
(个).
23.2.10★★★(1)图(a)中有多少个三角形?
(2)图(b)中又有多少个三角形?
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
解析 (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个圆最多把平面分成多少个部分?
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
解析 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).则这两个小三角形的顶点连同点将这两个小三角形分别一分为二,即也增加了两个小三角形.所以,内部的
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
个点把原三角形分割成的小三角形个数为
.
易知,于是
,,…,.
将上面这些式子相加,得
.
所以,当时,三个顶点、、D和这2008个内点能把原三角形分割成个小三角形.
23.2.15★★★平面上有100条直线,其中有20条是互相平行的,问这100条直线最多能将平面分成多少部分?
解析1 首先,这20条平行线将平面分成21个部分.
设另加上条直线,连同这20条平行线最多可将平面分成个部分,则
.
这是因为当再加入第条直线后,它与前条直线最多有个交点,从而这条直线被分成了段(其中有两段是射线),每一段将原来的部分一分为二,即增加了个部分.
所以
,
……
,
把上面的后个等式相加,得
.
易知,故
.
所以.
所以,这100条直线最多将平面分成了4861个部分.
解析2 解法1是先从平行线入手,现在我们先从80条互不平行的直线入手.一般地,设平面上条直线最多可将平面分成个部分,则(见题23.2.11)
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
.
所以,80条直线最多将平面分成3241个部分.现在再加入平行线.
每加入一条平行线,它与前面的直线最多有80个交点,从而增加81个部分,于是加入20条平行线后最多增加个部分.
因此,这100条直线最多将平面分成
个部分.
23.2.16★★★圆周上有个点,每两点连一条弦,如果没有三条弦交于圆内一点,问:这些弦在圆内一共有多少个交点?
解析 圆周上每4点构成一个凸四边形,它的两条对角线(弦)交于一点(如图),因此第4点对应于圆内一个交点.由于没有三条弦交于圆内一点,所以不同的4点对应于圆内的不同交点.反应过一,设点是弦与的交点,则与4点在、、、对应.所以,交点的个数就是圆周上个点中取4点的不同的取法总数,即
.
评注 最后的答案中要除以,理由同题23.2.10..
23.2.17★★★圆周上有8个点,,…,,如图所示.
(1)从出发将它们连结成一条在圆内不相交的折线(由7条线段组成,例如折线就是满足要求的一条),共可得多少条不同的折线?
(2)如果可以从这8点中的任一点出发,共可得多少条不同的拆线?
解析 (1)从出发连第1条线段时,只有两种连法:或(否则,若连,则与、、、、分布在两边,要每个顶点都连到,必定与
由莲山课件提供http://www.5ykj.com/ 资源全部免费
由莲山课件提供http://www.5ykj.com/ 资源全部免费
相交);接着连第2条线段时,也只有两种连法……连第6条线段时,有两种连法,连最后一条线段时,只有一种连法,所以由乘法原理知,不同的折线共有
(条).
(2)由(1)知,从8个点中的每一点(,2,…,8)出发,可以有64条不同的折线,从而可得条折线,但是对其中的每一条折线,将它的起点和终点都作为出发点重复算了一次,所以应除以2,故不同的折线共有
(条).
23.2.18★★★★在平面上给出条直线,且它们中的任何两条不平行,任三条不共线,证明:这些直线把平面分成的各部分中,三角形个数不少于.
解析 研究已知直线的所有交点.我们证明,这些点都在不多于两条已知直线的同一旁.假设所有这些交点都在三条已知直线的同一旁,这三条直线构成三角形,第四条直线不能仅与这个三角形的边相交,也就是它至少与一条边的延长线相交.为了确定起见,设它与从点出发的边的延长线相交于某点.这时点和在直线的两旁,得出矛盾.因此至少有条直线,它的两旁都有交点.
如果我们在由直线所给出的半平面上选取邻近的交点,那么这个点是毗连直线的三角形的顶点.这样一来,有不少于条直线,毗连它们每一条至少有两个三角形,并且有两条直线,毗连它们每一条至少有一个三角形,因为每个三角形恰毗连三条直线,所以有不少于个三角形.
由莲山课件提供http://www.5ykj.com/ 资源全部免费