数学奥林匹克专题讲座第11讲：计数的方法 标签：广州奥数题
<p><p> 一、枚举法 </p> <p> 一位旅客要从武汉乘火车去北京，他要了解所有可供乘坐的车次共有多少，一个最易行的办法是找一张全国列车运行时刻表，将所有从武汉到北京的车次逐一挑出来，共有多少次车也就数出来了，这种计数方法就是枚举法。所谓枚举法，就是把所要求计数的所有对象一一列举出来，最后计算总数的方法。运用枚举法进行列举时，必须注意无一重复，也无一遗漏。 </p> <p> 例1 四个学生每人做了一张贺年片，放在桌子上，然后每人去拿一张，但不能拿自己做的一张。问：一共有多少种不同的方法? </p> <p> 解：设四个学生分别是A，B，C，D，他们做的贺年片分别是a，b，c，d。 </p> <p> 先考虑A拿B做的贺年片b的情况(如下表)，一共有3种方法。 </p> <p> 同样，A拿C或D做的贺年片也有3种方法。 </p> <p> 一共有3+3+3=9(种)不同的方法。 </p> <p> 例2 甲、乙二人打乒乓球，谁先连胜两局谁赢，若没有人连胜头两局，则谁先胜三局谁赢，打到决出输赢为止。问：一共有多少种可能的情况? </p> <p> 解：如下图，我们先考虑甲胜第一局的情况： </p> <p> 图中打√的为胜者，一共有7种可能的情况。同理，乙胜第一局也有 7种可能的情况。一共有 7+7=14(种)可能的情况。 </p> <p> 二、加法原理 </p> <p> 如果完成一件事情有n类方法，而每一类方法中分别有m1，m2，?，mn种方法，而不论采用这些方法中的任何一种，都能单独地完成这件事情，那么要完成这件事情共有 </p> <p> N=m1+m2+?mn </p> <p> 种方法。 </p> <p> 这是我们所熟知的加法原理，也是利用分类法计数的依据。 </p> <p> 例3 一个自然数，如果它顺着数和倒着数都是一样的，则称这个数为“回文数”。例如2023，7，202都是回文数，而220则不是回文数。问：1到6位的回文数一共有多少个?按从小到大排，第2023个回文数是多少? </p> <p> 解：一位回文数有：1，2，?，9，共9个; </p> <p> 二位回文数有：11，22，?，99，共9个; </p> <p> 三位回文数有：101，111，?，999，共90个; </p> <p> 四位回文数有：2023，2023，?，2023，共90个; </p> <p> 五位回文数有：20231，20231，?，20239，共900个; </p> <p> 六位回文数有：202301，202301，?，202399，共900个。 到六位数为止，回文数共有 </p> <p> 9+9+90+90+900+900=2023(个)。 </p> <p> 第2023个回文数是2023001，第2023个回文数是2023001。 </p> <p> 例4 设有长度为1，2，?，9的线段各一条，现在要从这9条线段中选取若干条组成一个正方形，共有多少种不同的取法?这里规定当用2条或多条线段接成一条边时，除端点外，不许重叠。 </p> <p> 解法1：因为 </p> <p> 所以正方形的边长不大于11。 </p> <p> 下面按正方形的边长分类枚举： </p> <p> (1)边长为11：9+2=8+3=7+4=6+5，可得1种选法; </p> <p> (2)边长为10：9+1=8+2=7+3=6+4，可得1种选法; </p> <p> (3)边长为 9：9=8+1=7+2=6+3=5+4，可得5种选法; </p> <p> (4)边长为8：8=7+1=6+2=5+3，可得1种选法; </p> <p> (5)边长为7：7=6+1=5+2=4+3，可得1种选法; </p> <p> (6)边长≤6时，无法选择。 </p> <p> 综上计算，不同的取法共有 </p> <p> 1+1+5+1+1=9(种)。 </p> <p> 解法2：由于这些线段互不等长，故至少要用7条线段才能组成一个正方形。当恰取7条线段组成正方形时，正方形的3条边各用2条线相接，另一条边只用一条线段;当恰用8条线段时，只能每边各用2条线段相接(容易看出，其他情况不可能发生)。因为 1+2+?+9=45， 45不能被4整除，所以用9条线段，不可能组成正方形。由解法一知，拼出的正方形边长至多为11，又易知正方形的边长不可能为1，2，3，4，5，6。有了以上分析就容易计数了。 </p> <p> (1)取出7条线段，有以下7种： </p> <p> 7=1+6=2+5=3+4; </p> <p> 8=1+7=2+6=3+5; </p> <p> 9=1+8=2+7=3+6=4+5 </p> <p> (这个式子有5种); </p> <p> (2)取出8条线段，有以下2种： </p> <p> 1+9=2+8=3+7=4+6; </p> <p> 2+9=3+8=4+7=5+6。 </p> <p> 综上所述，不同的取法共有7+2=9(种)。 </p> <p> 如果完成一件事必须分n个步骤，而每一个步骤分别有m1，m2，?，mn种方法，那么完成这件事共有 </p> <p> N=m1×m2×?×mn </p> <p> 种方法。 </p> <p> 这就是乘法原理，它是分步法的依据。乘法原理和加法原理被称为是计数的基本原理。我们应注意它们的区别，也要注意二者的联合使用。 例5 一台晚会上有6个演唱节目和4个舞蹈节目。求： </p> <p> (1)当4个舞蹈节目要排在一起时，有多少不同的安排节目的顺序? </p> <p> (2)当要求每2个舞蹈节目之间至少安排1个演唱节目时，一共有多少不同的安排节目的顺序? </p> <p> 解：(1)先将4个舞蹈节目看成1个节目，与6个演唱节目一起排，有 7!=7×6×5×4×3×2×1=2023(种)方法。 </p> <p> 第二步再排4个舞蹈节目，有4!=4×3×2×1=24(种)方法。 根据乘法原理，一共有 2023×24=202360(种)方法。 </p> <p> (2)首先将6个演唱节目排成一列(如下图中的“□”)，一共有6!=6×5×4×3×2 ×1=720(种)方法。 </p> <p> ×□×□×□×□×□×□× </p> <p> 第二步，再将4个舞蹈节目排在一头一尾或2个演唱节目之间(即上图中“×”的位置)，这相当于从7个“×”中选4个来排，一共有7×6×5×4=840(种)方法。 </p> <p> 根据乘法原理，一共有720×840=202300(种)方法。 </p> <p> 例6 有8个队参加比赛，如果采用下面的淘汰制，那么在赛前抽签时，实际上可以得到多少种不同的安排表? </p> <p> 解：8个队要经过3轮比赛才能确定冠亚军。将第1轮的4组，自左至右记为1，2，3，4组，其中第1，2组为甲区，3，4组为乙区。8个队抽签即是在上图的8个位置排列，共有 </p> <p> 8!=8×7×6×5×4×3×2×1=20230(种) </p> <p> 不同的方法。 </p> <p> 但是，两种不同的排列不一定是实际上不同比赛的安排表。事实上，8队中的某4队都分在甲区或乙区，实际上是一样的;同区的4队中某2队在某一组或另一组，实际上也是一样的;同组中的2队，编号谁是奇数谁是偶数实际也是一样的。 </p> <p> 由乘法原理知，在20230种排法中，与某一种排法实质上相同的排法有 2×22×24=27=128(种)，故按实际不同比赛安排表的种数是 </p> <p> 四、对应法 </p> <p> 小孩子数苹果，往往掰着手指头，一个一个地掰，掰完左手掰右手，这种数苹果的方法就是对应法。小孩子把苹果与自己的手指头一对一，他掰了几个指头，也就数出了几个苹果。一般地，如果两类对象彼此有一对一的关系，那么我们可以通过对一类较易计数的对象计数，而得出具有相同数目的另一类难于计数的对象的个数。 </p> <p> 例7 在8×8的方格棋盘中，取出一个由 3个小方格组成的“L”形(如图1)，一共有多少种不同的方法? </p> <p> 解：每一种取法，有一个点与之对应，这就是图1中的A点，它是棋盘上横线与竖线的交点，且不在棋盘边上。 </p> <p> 从图2可以看出，棋盘内的每一个点对应着4个不同的取法(“L”形的“角”在2×2正方形的不同“角”上)。 </p> <p> 由于在 8×8的棋盘上，内部有7×7=49(个)交叉点，故不同的取法共有 </p> <p> 49×4=196(种)。 </p></p>
页:
[1]