信息学竞赛中问题求解题常见考查题型分析

一、寻找问有n（n≥3）个硬币，其中一个是，已知的重量比其他的要重一些，你有一1n1,2,…,n顺次编号。n=3，把一号硬币放在天平左边、二号硬币放在天平右边。如果天平：因此n=3，至多一次就能称出哪个是。记作f(3)=1。n=9。把所有的硬币分成三组：A{1,2,3},B{4,5,6},C{7,8,9}。A组的硬币放在左边、B组放在右边。如果天平：1、左偏，则在A组里面2、右偏，则在B组里面3、保持平衡，在C组里面无论在哪个组里面，我们已经把的范围从“9”缩小到了“3”，也就是减少到原1/3。之前我们已经研究过，31次就能称出来，故而f(9)=2。1.1f(3n)=n。3k+1ABC，使得|A|=|B|=|C|=3kA放在天平左边、B放在右1、左偏，在2、右偏，在3、平衡，在无论哪种结果，我们都把的范围缩小到了3k个硬币里面。而f(3k)=k，故而1.11.2f(n)=log3n1.1nmod30,1,21/3log3n应该就是最优解了。为了更加严格的证明log3n的最优性，我们引进判定树的概念。n=9时的一种判定树：>><<>>=>

<>< <><做出判断之前，谁也无法预知哪个硬币是，每个都有可能是我们的目标；因此一n个叶子节点。，nh≥log3n，故而可以证明，f(n)=log3n是最优的。， 同时还必须注意一点，我们在三分的时候有两个字很讲究：“均匀”。实际上h练习：第12届青少年信息学联赛初赛题现有80枚硬币，其中有一枚是，其重量稍重，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出？你还要第1次的称重方法。请写出你的结果： 答案：427，27，262有若干堆任意数目的小石子{a1，a2，…，am}(m≥1)，两人轮流取石子，每人··者必胜的，从这个例子的分析过程我们得到启示：可以用同余理论来探讨一般情况。k+1+n(k+1)ai′，故在{a1′，a2′，…，am′；k}中有取胜策略的一方在{a1，a2，…，有若干堆任意数目的小石子{a1，a2，…，am}，两人轮流从中取石子，每人每a1a2am}中的每一个分量用二进位制数表示，ai(1≤i≤minj(1≤j≤lmnj(1≤j≤l)，中3201030115101122n1n2n1=1，所以{2，3，5}是非偶数组。32，3，1}：21031110122nj(j=1，2)为偶数，则{2，3，1}为偶数组。偶数组与非偶数组在T201030116110131nii=1，2，3，所以{2，3，6}为非偶数，我们可以判定：先取者甲获胜，依性a3=61，可以验证{2，3，1}是偶数组，无论乙如例3：第12届青少年信息学联赛初赛题现有5堆石子,石子数依次为3，5，7，19，50，（每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失 753 abc“抽屉原理”最先是由19世纪的德国数学家赫莱（Dirichlet）运用于解决数学1091n+1n证明：（用反证法）1而n个集合至多有n个元素，此与共有n+1个元素，故命题成立。1nn22【例【分析与解33301，或者2，3332426442，只要取出的球数多于（4-1）×3=9104（同一颜色）里的球。【分析与解】：186618÷6=3（只），分别在每一312345631乒乓球，32……36，18664-63=1（只）乒乓球不管放入哪一个抽33434抽屉原理还可以反过来理解：假如把n＋1n22上苹果的抽屉一个也没有（22），那么，每个抽屉最多只放1个苹果，n个抽屉最多有n个苹果，与“n+1个苹果”的条件。n192、并集ABA，BA∪B，记号“∪”读作“并”。A∪B“ABA，BA∪B。6A={1，2，3，6}，10B={1，2，5，10}A∪3、交集：A、BA，BAB“A∩B”，读作“A交B”，如图阴影表示：6A={1，2，3，6}，10B={1，2，5，10A∩B={1，A，B，CA∪B∪C即有以下于、包含、包含于、真包含、真包含于、相等、不相等、相交、相并、互补(∈、s、、N、N※、Z、Q、R、∩、∪、CA、I、＝、≠……)等，这些新概念新关系，多s1：A={2，4，6，…20}，10|A|=10B={3，6，9，…18}6|B|=6A∩B={236，12，183|A∩B|=3A202B2036,12,1823解A={90B={90点评A，BA∪B，A∩B，再利用容斥原339，37，25A∩B={既打篮球又跑步的同学}=54（人A、B、C交的区域，区域Ⅶ（A∩B∩C）2。区4-2=2（人）。区域Ⅵ表示仅参7-2=5（人）。区域Ⅴ表示仅参加语文、外语5-2=3（人）。区域Ⅰ表示只参加数学小组的同学的集合，23-2-2-5=14（人）。同理可把区域Ⅱ、Ⅲ所表示的集合的人数逐个算出，分别点评2例5学校教导处对100名同学，结果有58人喜欢看球赛，有38人喜欢看戏剧，有52人喜欢看。另外还知道，既喜欢看球赛又喜欢看戏剧（但不喜欢看）的有6人，既喜欢看又喜欢看戏剧（但不喜欢看球赛）的有4人，三种都喜欢的有12人。问有多少同学只喜欢看？有多少同学既喜欢看球赛又喜欢看（但不喜欢看戏17（如图）这三个圆圈分别表示三7解得只喜欢看的人数36-解法2：设A={喜欢看球赛的人}，B={喜欢看戏剧的人}，C={喜欢看的人}，依题目的条件有|A∪B∪C|=100，|A∩B|=6+12=18（12C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|解得∴36-所以既喜欢看又喜欢看球赛的人数为14，只喜欢看的人数为221nm1种不同的方法，在第二类办法中有m2nmn种不同的方法那么

Nm1m2 mn分步计数原理nm1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事有Nm1m2 mn排列的概念：从n个不同元素中，任取m（mn）个元素（这里的被取元素各不相同）按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列排列数的定义：从n个不同元素中，任取m（mn）n从n个元素中取出m元素的排列数，用符号nn排列数

Amn(n1)(n (nm

（m,nN,mn6n!1n的连乘积，叫做n的阶乘规定AnAn7．排列数的另一个计算

m(n8：一般地，从n个不同元素中取出mmnn个不同元素中取出m个元素的一个组合组合数的概念：从n个不同元素中取出mmnCn(nn(n1)(n (nmCmn

nA A组合 nCm n或

(nmN且mCmCnm

C011组合数的性质1： ．规定：

C2：n1C

CCn+CCAa1a2a3,an}的n个元素中，每次取出r个元素排在一个圆环上，叫列；（iii）两个圆排列只有在元素不同或者元素虽然相同，但元间的顺序不同，才是Aa1a2a3,an}的n个元素中，每次取出rPrnrm个不同的元素中，每次取出n个元素，元素可以重复出现，按照一定的顺序那么第一、第二、…、第n位是的选取元素的方法都是m种，所以从m取出n个元素的可重复的排列数为mn如果np1p2ps（p1p2psn），这n个元素全部取的排列叫做不尽相异的n

从np个元素，允许所取的元素重复出现1,2,,p次的组合叫n个元素取出p个有重复的组合．定理：从npHpCr n(1211344C3abcd12一、相临问题——整体 种地:个人站成一排,其中某 分析此题涉及到的是排队问题,对于有特殊的限制,因此,是特殊元素,并且要求她们 P6P3 种排法,其中内部也有 6 27应为：种.条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.若个人站成 种排法练习：学校组织老师学生一起看，同一排票12张。8个学生，4个老师，要求此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊元素,在解决解先排学生共有874

P4

P8P4 8 个解：从7个点中取3个点的取法有种，但其中正六边形的对角线所含的中心和顶点三点共线不能组成三角形，有3条，所以满足条件的三角形共有－3＝32个.练习435此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情解435

C43C

C40C

C C例4．1名老师和4名获奖学生排成一排照像留念，若老师不排在两端，则共有不同的 ＝72种不同的排法.例5．乒乓球队的10名队员中有3名主力队员，派5名队员参加比赛，3名主力队员要安排在第一、三、五位置，其余7名队员选2名安排在第二、四位置，那么不同的出场 解：由于第一、三、五位置特殊，只能安排主力队员，有7出2名安排在第二、四位置，有种排法，所以不同的出场安排共有＝252种.例6．某班新年联欢会原定的5个已排成单，开演前又增加了两个新.如果将这两个插入原单中，那么不同插法的种数为（A） 626626解：增加的两个新，可分为相临与不相临两种情况：1.不相临：共有A2种；2.相A2A1种。故不同插法的种数为：A2+A2A1=42A。626626例7．12名同学分别到三个不同的路口进行车流量的，若每个路口4人，则不 解：本试题属于均分组问题。则12名同学均分成3组共有 种，故选A。8．43地上，其中黄瓜必须种植，不同的种植方法共有（） 332332解C2种,不同的排法有:A1·A2,故不同的种植方法共有A1·C2·A2=12C.332332解2、312776“I”（一般可视为“隔板”）共有种插法，即有15种分法。108121分析此题若直接去考虑的话,就会比较复杂.但如果其转换为等价的其他问题,就会

C11C

C C 既真又假A、B、C、D 1、2、4、5A、BCD；但这与3的结论相，所以3的前提肯定不成立，即A应该是躺在；在4中C既不看书又不修指甲，由前面分析，C又不可能躺在，所以C是在写信；而B则是在看5.A、B、C、D C：ABD：BA3B5学校进行了一次考试，考试的科目是语文、历史、数学、物理和英语，每科满B、C、D、EAB、C、D、EE（1）55×(1+2+3+4+5)=75A24B、C、D、E75－24=51E8E（还有三科）11稍加验算可知：B、C、D、E、、135A、EC31E3分，故C13（5）D12485A、E3C、E1C、ED2【例9】赵、钱、孙、人，一个是教师，一个是售货员，一个是工人，一个是机关。试根据以下条件，判断这四人的职业。售货员的邻居不是机关机关和工人互不相识机关比售货员和工 也是，。这样我们得到下表。下面几步推理也用表格说明。A、B、C、D、E（每两支球队间都要进行一场比赛），当比A、B、C、DA4，B3，C2，D1，E（）A. B. C. D.A、B、C、D、E1A4AB、C、D、E一 递推关系的定二 递推关系的建在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序LogoBasicPascalCFibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于“Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年兔子繁殖问题”(又称“Fibonacci“nOx对。则： 边界条件 ancnacn-1chn-1+1+hn-1个盘次。 n1 1 610349875 图a1=1。6-4)h5=5nhn。P1Pn也不例外，再根据“不在同一直线上的三点可以①③② ①③②

域②的拆分方案数为Cn-k+1，故包含△P1PkPn的n边形的拆分方案数 CiCni1，

A EA ED方法？”先求通项an或递推关系，再求a6。【解答】解法一：按A、C、E染况进行分类A、C、E染一种色，则此时共有43331084A、C、EP32221924若P2C2322432 a6由已知条件容易建立递推关系

4

(n。由该