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

初一数学竞赛讲座第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种措施。这是咱们所熟知加法原理，也是运用分类法计数根据。例3一种自然数，假如它顺着数和倒着数都是同样，则称这个数为“回文数”。例如1331，7，202都是回文数，而220则不是回文数。问：1到6位回文数一共有多少个？按从小到大排，第个回文数是多少？解：一位回文数有：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，第个回文数是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×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（种），故按实际不一样比赛安排表种数是四、对应法小孩子数苹果，往往掰着手指头，一种一种地掰，掰完左手掰右手，这种数苹果措施就是对应法。小孩子把苹果与自己手指头一对一，她掰了几种指头，也就数出了几种苹果。一般地，假如两类对象彼此有一对一关系，那么咱们可以通过对一类较易计数对象计数，而得出具有相似数目另一类难于计数对象个数。例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×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条边当然不用剪；别旳边，由于是两个三角形公共边，剪一刀出两条边，因此共剪刀数是练习101．一只青蛙在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，…，这1000个自然数中，可以找到多少对相邻自然数，使它们相加时不进位？8．有10个箱子，编号为1，2，…，10，各配一把钥匙，10把各不相似，每个箱子放进一把钥匙锁好，先撬开1，2号箱子，取出钥匙去开别箱子，假如最终能把所有箱子锁都打开，则说是一种好放钥匙措施。求好措施总数。练习10答案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个三角形至多