《第15讲 计数综合1.doc》由会员分享，可在线阅读，更多相关《第15讲 计数综合1.doc（5页珍藏版）》请在金锄头文库上搜索。
1、15讲 计数综合1内容概述 将关键的已知数据看作变量，得到一类结构相同的计数问题，通过建立这些问题的结果所构成数列的递推关系，逐步地求得原问题的答案与分数、几何等相关联的计数综合题典型问题 1一个长方形把平面分成两部分，那么3个长方形最多把平面分成多少部分? 【分析与解】 一个长方形把平面分成两部分第二个长方形的每一条边至多把第一个长方形的内部分成2部分，这样第一个长方形的内部至多被第二个长方形分成五部分 同理，第二个长方形的内部至少被第一个长方形分成五部分这两个长方形有公共部分(如下图，标有数字9的部分)还有一个区域位于两个长方形外面，所以两个长方形至多把平面分成10部分 第三个长方形的每一
2、条边至多与前两个长方形中的每一个的两条边相交，故第一条边被隔成五条小线段，其中间的三条小线段中的每一条线段都把前两个长方形内部的某一部分一分为二，所以至多增加34=12个部分而第三个长方形的4个顶点都在前两个长方形的外面，至多能增加4个部分 所以三个长方形最多能将平面分成10+12+4=26 2一个楼梯共有10级台阶，规定每步可以迈1级台阶或2级台阶，最多可以迈3级台阶从地面到最上面1级台阶，一共可以有多少种不同的走法? 【分析与解】 我们知道最后一步可以迈1级台阶、2级台阶或3级台阶，也就是说可以从倒数第1、2或3级台阶直接迈入最后一级台阶 即最后一级台阶的走法等于倒数第1、2和3级台阶的走
3、法和而倒数第l级台阶的走法等于倒数第2、3和4级台阶的走法和， 如果将1、2、3级台阶的走法依次排成一个数列，那么从第4项开始，每一项等于前3项的和有1，2，3级台阶的走法有1，2，4种走法，所以4，5，6，7，8，9，10级台阶的走法有7，13，24，44，81，149，274种走法 3一个圆上有12个点A1，A2，A3，A11，A12以它们为顶点连三角形，使每个点恰好是一个三角形的顶点，且各个三角形的边都不相交问共有多少种不同的连法? 【分析与解】我们采用递推的方法 I如果圆上只有3个点，那么只有一种连法 如果圆上有6个点，除A1点所在三角形的三顶点外，剩下的三个点一定只能在A1所在三角形
4、的一条边所对应的圆弧上，表1给出这时有可能的连法 如果圆上有9个点，考虑A1所在的三角形此时，其余的6个点可能分布在： A1所在三角形的一个边所对的弧上； 也可能三个点在一个边所对应的弧上，另三个点在另一边所对的弧上 在表2中用“+”号表示它们分布在不同的边所对的弧 如果是情形，则由，这六个点有三种连法； 如果是情形，则由，每三个点都只能有一种连法 共有12种连法 最后考虑圆周上有12个点同样考虑A1所在三角形，剩下9个点的分布有三种可能： 9个点都在同一段弧上： 有6个点是在一段弧上，另三点在另一段弧上； 每三个点在A1所在三角形的一条边对应的弧上得到表3共有123+36+155种所以当圆周
5、上有12个点时，满足题意的连法有55种. 4现在流行的变速自行车，在主动轴和后轴分别安装了几个齿数不同的齿轮用链条连接不同搭配的齿轮，通过不同的传动比获得若干挡不同的车速“希望牌”变速自行车主动轴上有3个齿轮，齿数分别是48，36，24；后轴上有4个齿轮，齿数分别是36，24，16，12问：这种变速车一共有多少挡不同的车速? 【分析与解】算出全部的传动比，并列成表：这里有4对传动比是相同的：1，2，3，将重复的传动比去掉，剩下8个不同的比，所以共有8挡不同的车速5分子小于6，分母小于60的不可约真分数有多少个?【分析与解】 分子的取值范围是从1到5 当分子为1时，分母可从2到59，共有58个真
6、分数，它们当然都是不可约分数 由于2，3，5都是质数，因此当分子分别为2，3，5时，分母必须而且只需适合下列两个条件： 分母大于分子且小于60 分母不是分子的倍数 易知：当分子为2时，适合条件的分母有29个； 当分子为3时，适合条件的分母有38个： 当分子为5时，适合条件的分母有44个； 最后来看分子为4的情形，与分子为2基本相同，分母不能为偶数，此外分母不能为3所以共有28(=291)个总之，符合要求的分数共有58+29+38+44+28197个 6一个正方形的内部有1996个点，以正方形的4个顶点和内部的1996个点为顶点，将它剪成一些三角形问：一共可以剪成多少个三角形?如果沿上述这些点中
7、某两点之间所连的线段剪开算作一刀，那么共需剪多少刀? 【分析与解】方法一：如下图，采用归纳法，列出1个点、2个点、3个点时可剪出的三角形个数，需剪的刀数 不难看出，当正方形内部有n个点时，可以剪成2n2个三角形，需剪3n+l刀，现在内部有1996个点，所以可以剪成21996+2=3994个三角形，需剪31996+1=5989刀 方法二：我们知道内部一个点贡献360度角，原正方形的四个顶点共贡献了360度角，所以当内部有n个点时，共有360n+360度角，而每个三角形的内角和为180度角，所以可剪成(360n+360)180=2n+2个三角形 2n+2个三角形共有3(2n+2)=6n+6条边，但
8、是其中有4条是原有的正方形的边，所以正方形内部的三角形边有6n+64=6n+2条边，又知道每条边被2个三角形共用，即每2条边是重合的，所以只用剪(6n+2)23n+1刀本题中n=1996，所以可剪成3994个三角形，需剪5989刀7如图153，某城市的街道由5条东西与7条南北向马路组成现在要从西南角的A处沿最短路线走到东北角的B处，由于修路十字路口C不能通过，那么共有多少种不同走法? 【分析与解】 因为每个路口(点)只能由西边相邻点、南边相邻点走过来，所以达到每个点的走法为西边相邻点、南边相邻点的走法之和，并且最南方一排、最西方一排的所有点均只有1种走法 因为C点不能通过，所以C处所标的数字为
9、0如下图所示：所以，从A到B满足条件的走法共有120种8经理将要打印的信件交给秘书，每次给一封，且放在信封的最上面，秘书一有空就从最上面拿一封信来打有一天共有9封信打，经理按第1封，第2封，第9封的顺序交给秘书午饭时，秘书告诉同事，已把第8封信打印好了，但未透露上午工作的其他情况，这个同事很想知道是按什么顺序来打印根据以上信息，下午打印的信的顺序有多少种可能?(没有要打的信也是一种可能) 【分析与解】 我们根据最后一封信来计数： (1)第9封信在上午送给秘书； 于是，T=1，2，3，4，5，6，7，9 则下午打印的每种可能都是T的一个子集，因为秘书可以把不在子集中的信件上午一送来就打完了，而未打别的信集T有8个元素，故有28=256个不同子集(包括空集) (2)第9封信在午后才送给秘书令 S1，2，3，4，5，6，7， 则上午未打印的信的号码是S的一个子集若将9排在子集之后，则与中的情形相同，故只有子集中至少有一封信已把号码9放在该子集的非最后的位置上对于有k个元素的子集，号码9有k个位置可放，即可放在第i一1个元素之后和i个元素之前，i=1，2，k于是不同的顺序总数为： 0C07+1C17+2C27+7C77=7272=726=448 即下午有448种可能的打印顺序 所以，下午共有256+448=704种打印的方法
