《数学奥林匹克专题讲座》第11讲 计数的方法与原理Word文档下载推荐.docx
《《数学奥林匹克专题讲座》第11讲 计数的方法与原理Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《《数学奥林匹克专题讲座》第11讲 计数的方法与原理Word文档下载推荐.docx（13页珍藏版）》请在冰点文库上搜索。
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（种）。
三、乘法原理
如果完成一件事必须分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×
1＝24（种）方法。
根据乘法原理，一共有5040×
24=120960（种）方法。
（2）首先将6个演唱节目排成一列（如下图中的“□”），一共有6！
=6×
2×
1=720（种）方法。
×
□×
第二步，再将4个舞蹈节目排在一头一尾或2个演唱节目之间（即上图中“×
”的位置），这相当于从7个“×
”中选4个来排，一共有7×
4＝840（种）方法。
根据乘法原理，一共有720×
840=604800（种）方法。
例6有8个队参加比赛，如果采用下面的淘汰制，那么在赛前抽签时，实际上可以得到多少种不同的安排表？
8个队要经过3轮比赛才能确定冠亚军。
将第1轮的4组，自左至右记为1，2，3，4组，其中第1，2组为甲区，3，4组为乙区。
8个队抽签即是在上图的8个位置排列，共有
8！
=8×
7×
1=40320（种）
不同的方法。
但是，两种不同的排列不一定是实际上不同比赛的安排表。
事实上，8队中的某4队都分在甲区或乙区，实际上是一样的；
同区的4队中某2队在某一组或另一组，实际上也是一样的；
同组中的2队，编号谁是奇数谁是偶数实际也是一样的。
由乘法原理知，在40320种排法中，与某一种排法实质上相同的排法有2×
22×
24=27=128（种），故按实际不同比赛安排表的种数是
四、对应法
小孩子数苹果，往往掰着手指头，一个一个地掰，掰完左手掰右手，这种数苹果的方法就是对应法。
小孩子把苹果与自己的手指头一对一，他掰了几个指头，也就数出了几个苹果。
一般地，如果两类对象彼此有一对一的关系，那么我们可以通过对一类较易计数的对象计数，而得出具有相同数目的另一类难于计数的对象的个数。
例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个自然数的百分之几？
由容斥原理2知，1至100的自然数中，或能被2整除，或能被3整除，或能被5整除的自然数的个数是
＝50＋33＋20-16-6＋3＝74。
所以，在1至100的自然数中，不能被2整除，又不能被3整除，还不能被5整除的自然数有100－74=26（个），占这100个自然数的26％。
六、归纳法
对于比较复杂的问题，可以先观察其简单情况，归纳出其中带规律性的东西，然后再来解决较复杂的问题。
例1110个三角形最多将平面分成几个部分？
解。
设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×
……
一般地，第n个三角形与前面（n-1）个三角形最多有2（n-1）×
3个交点，从而平面也增加2（n－1）×
3个部分，故
an=2＋2×
3＋…＋2（n-1）×
3
＝2＋［2＋4＋…＋2（n-1）］×
＝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条边当然不用剪；
其余的边，由于是两个三角形的公共边，剪一刀出两条边，所以共剪的刀数是
练习11
1．一只青蛙在A，B，C三点之间跳动，若青蛙从A点跳起，跳4次仍回到A点，则这只青蛙一共有多少种不同的跳法？
2．在国际象棋棋盘上放置两只“车”，如果它们彼此不构成威胁，那么一共有多少种不同的放法？
3．在8×
8的棋盘上可以找到多少个形如右图所示的“凸”字形图形？
4．从19，20，21，…，97，98，99这81个数中，选取两个不同的数，使其和为偶数的选法总数是多少？
5．平面上有7个不在同一直线上的点，以这7个点作为顶点做三角形，使得任何两个三角形至多只有一个公共顶点。
最多可做出多少个满足条件的三角形？
6．下图是一个道路图。
A处有一大群孩子，这群孩子向东或向北走，在从A开始的每个路口，都有一半人向北走，另一半人向东走，如果先后有60个孩子到过路口B，那么先后共有多少个孩子到过路口C？
7．在1001，1002，…，2000这1000个自然数中，可以找到多少对相邻的自然数，使它们相加时不进位？
8．有10个箱子，编号为1，2，…，10，各配一把钥匙，10把各不相同，每个箱子放进一把钥匙锁好，先撬开1，2号箱子，取出钥匙去开别的箱子，如果最终能把所有箱子的锁都打开，则说是一种好的放钥匙的方法。
求好的方法的总数。
1.6种。
如下图，第1步跳到B，4步回到A有3种方法；
同样第1步到C的也有3种方法。
共有6种方法。
2.3136种。
第一步，放第一只“车”，有64种方法；
第二步，放第二只“车”，因不能和第一只同行，也不能同列，故有49种方法。
由乘法原理，一共有64×
49=3136（种）放法。
3.168个。
在每个2×
3的长方形中可以找到2个“凸”字形图形，8×
8方格棋盘中共有84个2×
3的长方形，所以可以找到
84×
2=168（个）。
4.1600种。
从19到99共计81个不同的整数，其中有41个奇数、40个偶数。
若选取两数之和为偶数，则必须且只须选取的两个数有相同的奇偶性，所以选取的方法数分为两类：
第一类，选取两个不同偶数的方法数；
第二类，选取两个不同奇数的方法数。
依加法原理，这两类方法数的总和即为所求的方法数。
第一类是从40个偶数中选取两个不同偶数的方法数，先取第一个偶数有40种方法，从其余39个偶数中选择第2个有39种方法，依乘法原理，共有40×
39种不同的方法，但注意选取第1个数比如30，选取第2个数比如32，与选第1个数32，再选第2个数30，是同一组。
所以总的选法数应该折半，
第二类是从41个奇数中选取两个不同奇数的方法数，与上述方法相同，
5.7个。
2个三角形至多有1个公共顶点，从而任意2个三角形没有公共边，故至多
另一方面，7个是可以达到的。
设7个点依次为A1，A2，…，A7。
如右图，△A1A2A3，△A1A4A5，△A1A6A7，△A2A4A6，△A2A5A7，△A3A4A7，△A3A5A6这7个三角形两两没有公共边。
故最多可以做7个三角形。
6.48人。
如下图，设A处有a个孩子，图中各个路口边上的数字表示到过该
又从下图看出，到过路口C的人数为
7.156个。
相邻两数相加不需进位的数对中，前一个数可分成四类：
（1）1999，1个；
由加法原理知，这样的数对共有
1+5+25+125=156（个）。
8.725760。
设第1，2，3，…，10号箱子中所放的钥匙号码依次为k1，k2，k3，…，k10。
当箱子数为n（n≥2）时，好的放法的总数为an。
当n=2时，显然a2=2（k1=1，k2=2或k1=2，k2=1）。
当n=3时，显然k3≠3，否则第3个箱子打不开，从而k1=3或k2=3，于是n=2时的每一组解对应n=3的2组解，这样就有a3=2a2=4。
当n=4时，也一定有k4≠4，否则第4个箱子打不开，从而k1=4或k2=4或k3=4，于是n=3时的每一组解，对应n=4时的3组解，这样就有a4=3a3=12。
依次类推，有
a10=9a9=9×
8a8=…
=9×
8×
2a2
=2×
9！
=725760。
即好的方法总数为725760。
升级会员 