初一数学竞赛教程含例题练习及答案⑽

初一数学竞赛讲座

第10讲 计数的方法与原理

计数方法与原理是组合数学的主要课题之一，本讲介绍一些计数的基本方法及计数的基本原理。

一、枚举法

一位旅客要从武汉乘火车去北京，他要了解所有可供乘坐的车次共有多少，一个最易行的办法是找一张全国列车运行时刻表，将所有从武汉到北京的车次逐一挑出来，共有多少次车也就数出来了，这种计数方法就是枚举法。所谓枚举法，就是把所要求计数的所有对象一一列举出来，最后计算总数的方法。运用枚举法进行列举时，必须注意无一重复，也无一遗漏。

例1 四个学生每人做了一张贺年片，放在桌子上，然后每人去拿一张，但不能拿自己做的一张。问：一共有多少种不同的方法？

解：设四个学生分别是A，B，C，D，他们做的贺年片分别是a，b，c，d。 先考虑A拿B做的贺年片b的情况（如下表），一共有3种方法。

同样，A拿C或D做的贺年片也有3种方法。

一共有3＋3＋3=9（种）不同的方法。

例2 甲、乙二人打乒乓球，谁先连胜两局谁赢，若没有人连胜头两局，则谁先胜三局谁赢，打到决出输赢为止。问：一共有多少种可能的情况？ 解：如下图，我们先考虑甲胜第一局的情况：

图中打√的为胜者，一共有7种可能的情况。同理，乙胜第一局也有 7种可能的情况。一共有 7＋7=14（种）可能的情况。

二、加法原理

如果完成一件事情有n类方法，而每一类方法中分别有m1，m2，?，mn种方法，而不论采用这些方法中的任何一种，都能单独地完成这件事情，那么要完成这件事情共有：N=m1+m2+?mn种方法。

这是我们所熟知的加法原理，也是利用分类法计数的依据。

1

例3 一个自然数，如果它顺着数和倒着数都是一样的，则称这个数为“回文数”。例如1331，7，202都是回文数，而220则不是回文数。问：1到6位的回文数一共有多少个？按从小到大排，第2000个回文数是多少？

解：一位回文数有：1，2，?，9，共9个；

二位回文数有：11，22，?，99，共9个；

三位回文数有：101，111，?，999，共90个；

四位回文数有：1001，1111，?，9999，共90个；

五位回文数有：10001，10101，?，99999，共900个；

六位回文数有：100001，101101，?，999999，共900个。

到六位数为止，回文数共有

9＋9＋90＋90＋900＋900=1998（个）。

第1999个回文数是1000001，第2000个回文数是1001001。

例4 设有长度为1，2，?，9的线段各一条，现在要从这9条线段中选取若干条组成一个正方形，共有多少种不同的取法？这里规定当用2条或多条线段接成一条边时，除端点外，不许重叠。

解法1：因为

所以正方形的边长不大于11。

下面按正方形的边长分类枚举：

（1）边长为11：9＋2=8+3=7＋4=6＋5，可得1种选法；

（2）边长为10：9＋1=8＋2=7＋3=6＋4，可得1种选法；

（3）边长为 9：9=8＋1=7＋2=6＋3=5＋4，可得5种选法；

（4）边长为8：8=7＋1=6＋2=5+3，可得1种选法；

（5）边长为7：7=6＋1=5＋2=4＋3，可得1种选法；

（6）边长≤6时，无法选择。

综上计算，不同的取法共有

1＋1+5＋1＋1=9（种）。

解法2：由于这些线段互不等长，故至少要用7条线段才能组成一个正方形。当恰取7条线段组成正方形时，正方形的3条边各用2条线相接，另一条边只用一条线段；当恰用8条线段时，只能每边各用2条线段相接（容易看出，其他情况不可能发生）。因为 1+2＋?＋9=45， 45不能被4整除，所以用9条线段，不可能组成正方形。由解法一知，拼出的正方形边长至多为11，又易知正方形的边长不可能为1，2，3，4，5，6。有了以上分析就容易计数了。

（1）取出7条线段，有以下7种：

7=1+6＝2＋5＝3＋4；

8＝1+7＝2+6＝3＋5；

9＝1＋8＝2＋7＝3＋6=4＋5

（这个式子有5种）；

（2）取出8条线段，有以下2种：

1＋9＝2＋8＝3＋7＝4＋6；

2＋9＝3＋8＝4＋7＝5＋6。

综上所述，不同的取法共有7＋2=9（种）。

三、乘法原理

2

如果完成一件事必须分n个步骤，而每一个步骤分别有m1，m2，?，mn种方法，那么完成这件事共有：N＝m1×m2×?×mn种方法。

这就是乘法原理，它是分步法的依据。乘法原理和加法原理被称为是计数的基本原理。我们应注意它们的区别，也要注意二者的联合使用。

例5 一台晚会上有6个演唱节目和4个舞蹈节目。求：

（1）当4个舞蹈节目要排在一起时，有多少不同的安排节目的顺序？

（2）当要求每2个舞蹈节目之间至少安排1个演唱节目时，一共有多少不同的安排节目的顺序？

解：（1）先将4个舞蹈节目看成1个节目，与6个演唱节目一起排，有 7！=7×6×5×4×3×2×1=5404（种）方法。

第二步再排4个舞蹈节目，有4！=4×3×2×1＝24（种）方法。 根据乘法原理，一共有 5040×24=120960（种）方法。

（2）首先将6个演唱节目排成一列（如下图中的“□”），一共有6！=6×5×4×3×2 ×1=720（种）方法。

×□×□×□×□×□×□×

第二步，再将4个舞蹈节目排在一头一尾或2个演唱节目之间（即上图中“×”的位置），这相当于从7个“×”中选4个来排，一共有7×6×5×4＝840（种）方法。

根据乘法原理，一共有720×840=604800（种）方法。

例6 有8个队参加比赛，如果采用下面的淘汰制，那么在赛前抽签时，实际上可以得到多少种不同的安排表？

解：8个队要经过3轮比赛才能确定冠亚军。将第1轮的4组，自左至右记为1，2，3，4组，其中第1，2组为甲区，3，4组为乙区。8个队抽签即是在上图的8个位置排列，共有

8！=8×7×6×5×4×3×2×1=40320（种）

不同的方法。

但是，两种不同的排列不一定是实际上不同比赛的安排表。事实上，8队中的某4队都分在甲区或乙区，实际上是一样的；同区的4队中某2队在某一组或另一组，实际上也是一样的；同组中的2队，编号谁是奇数谁是偶数实际也是一样的。

由乘法原理知，在40320种排法中，与某一种排法实质上相同的排法有 2×22×24=27=128（种），故按实际不同比赛安排表的种数是

四、对应法

小孩子数苹果，往往掰着手指头，一个一个地掰，掰完左手掰右手，这种数苹果的方法就是对应法。小孩子把苹果与自己的手指头一对一，他掰了几个指头，也就数出了几个苹果。一般地，如果两类对象彼此有一对一的关系，那么我们可以通过对一类较易计数的对象计数，而得出具有相同数目的另一类难于计数的对象的个数。

3

例7 在8×8的方格棋盘中，取出一个由 3个小方格组成的“L”形（如图

1），一共有多少种不同的方法？

解：每一种取法，有一个点与之对应，这就是图1中的A点，它是棋盘上横线与竖线的交点，且不在棋盘边上。

从图2可以看出，棋盘内的每一个点对应着4个不同的取法（“L”形的“角”在2×2正方形的不同“角”上）。

由于在 8×8的棋盘上，内部有7×7=49（个）交叉点，故不同的取法共有 49×4=196（种）。

例8 数3可以用4种方法表示为1个或几个正整数的和，如3，1＋2，2+1，1+1＋1。问：1999表示为1个或几个正整数的和的方法有多少种？

分析与解：我们将1999个1写成一行，它们之间留有1998个空隙，在这些空隙处，或者什么都不填，或者填上“＋”号。例如对于数3，上述4种和的表达方法对应：

111，11＋1，1＋11，1＋1＋1。

显然，将1999表示成和的形式与填写1998个空隙处的方式之间一对一，而每一个空隙处都有填“＋”号和不填“＋”号2种可能，因此1999可以表示为正整数之和的不同方法有

五、容斥原理

在应用加法原理时，关键在于把所要计数的对象分为若干个不重不漏的类，使得每类便于计数。但是具体问题往往是复杂的，常常扭成一团，难以分为不重不漏的类，而要把条理分清楚就得用加法原理的推广——容斥原理。

为了表达方便，我们用A表示A类元素的个数，用B表示B类元素的个数，用 A∪B表示是 A类或是 B类元素的个数，用A∩B表示既是A类又是B类元素的个数。A∪B∩C，A∪B∩C的意义类似。

容斥原理1 如果被计数的事物有两类，那么A∪B＝A＋B－A∩B。

容斥原理2 如果被计数的事物有三类，那么A∪B∪C＝A+B＋C-A∩B-B∩C－A∩C＋A∩B∩B。

容斥原理的实质在于包含与排除，或形象地称之为“多退少补”。容斥原理若用韦恩图进行分析和记忆，十分方便，留给读者研究。

例9 在100名学生中，有10人既不会骑自行车又不会游泳，有65人会骑自行车，有73人会游泳，既会骑自行车又会游泳的有多少人？

解：从100名总人数中减去既不会骑自行车又不会游泳的10人，就是会骑自行车或会游泳的人数

100-10=90（人）。

既会骑自行车又会游泳的有（65＋73）－90=48（人）。

例10 在1至100的自然数中，不能被2整除，又不能被3整除，还不能被5整除的数，占这100个自然数的百分之几？

4

解：由容斥原理2知，1至100的自然数中，或能被2整除，或能被3整除，或能被5整除的自然数的个数是

＝50＋33＋20-16-6＋3＝74。

所以，在1至100的自然数中，不能被2整除，又不能被3整除，还不能被5整除的自然数有100－74=26（个），占这100个自然数的26％。

六、归纳法

对于比较复杂的问题，可以先观察其简单情况，归纳出其中带规律性的东西，然后再来解决较复杂的问题。

例11 10个三角形最多将平面分成几个部分？

解。设n个三角形最多将平面分成an个部分。

n=1时，a1=2；

n=2时，第二个三角形的每一条边与第一个三角形最多有2个交点，三条边与第一个三角形最多有2×3=6（个）交点。这6个交点将第二个三角形的周边分成了6段，这6段中的每一段都将原来的每一个部分分成2个部分，从而平面也增加了6个部分，即a2＝2＋2×3。

n＝3时，第三个三角形与前面两个三角形最多有4×3＝12（个）交点，从而平面也增加了12个部分，即：

a3=2＋2×3＋4×3。

??

一般地，第n个三角形与前面（n-1）个三角形最多有2（n-1）×3个交点，从而平面也增加2（n－1）×3个部分，故

an=2＋2×3＋4×3＋?＋2（n-1）×3

＝2＋［2＋4＋?＋2（n-1）］×3

＝2＋3n（n-1）＝3n2-3n＋2。

特别地，当n＝10时，a10＝3×102＋3×10＋2=272，即10个三角形最多把平面分成272个部分。

七、整体法

解答数学题，有时要“化整为零”，使问题变得简单；有时反而要从整体上来考虑，从全局、从整体来研究问题。

例12 正方形ABCD的内部有1999个点，以正方形的4个顶点和内部的1999个点为顶点，将它剪成一些三角形。问：一共可以剪成多少个三角形？共需剪多少刀？

解：我们从整体来考虑，先计算所有三角形的内角和。汇聚在正方形内一点的诸角之和是360°，而正方形内角和也是360°，共有 360°×1999＋360°，从而三角形的个数是

由于每个三角形有三条边，而正方形纸原来的4条边当然不用剪；其余的边，由于是两个三角形的公共边，剪一刀出两条边，所以共剪的刀数是

5