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

PAGEPAGE17用心爱心专心一、寻找假币问题 有n（n≥3）个硬币，其中一个是假币，已知假币的重量比其他的要重一些，你有一架天平。现在要称出哪个假币来。解析：首先我们先来考虑最简单的问题1。为了方便叙述，把n个硬币按1,2,…,n顺次编号。若n=3，把一号硬币放在天平左边、二号硬币放在天平右边。如果天平：1、左偏，一号重，是假币。2、右偏，二号重，是假币。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。之前我们已经研究过，3个硬币1次就能称出来，故而f(9)=2。不难推广到一般的情况：定理1.1f(3n)=n。证明：n=1,2时，已证。设n=k成立，则f(3k)=k；下面考虑n=k+1的情况。将3k+1个硬币分成三堆A,B,C，使得|A|=|B|=|C|=3k。把A放在天平左边、B放在右边，天平：1、左偏，假币在A2、右偏，假币在B3、平衡，假币在C无论哪种结果，我们都把假币的范围缩小到了3k个硬币里面。而f(3k)=k，故而f(3k+1)=k+1。综上，定理1.1成立。稍经分析不难得到：定理1.2f(n)=这个的证明和定理1.1完全类似，分nmod3=0,1,2适当讨论即可。我们必须注意到是可行的，因为我们能够构造出这样一个方案。问题是它是否最优？我们采取的方案是每次将硬币尽量均匀的三分，这样做的根据就是天平只有三种结果：左偏、右偏、平衡。于是就能保证无论假币在哪一份都能将结果的范围缩小到原来的1/3。从感性上认识，应该就是最优解了。为了更加严格的证明的最优性，我们引进判定树的概念。下图就是n=9时的一种判定树：比较比较(1,2,3)与(4,5,6)>=<比较(1)与(2)>13=<2比较(7)与(8)>79=<8比较(4)与(5)>46=<5此题的判定树是这样一棵树：1、叶子节点代表一种可能的结果。2、非叶子节点代表一次称量。3、非叶子节点至多有三个儿子，分别代表天平的左偏、右偏、平衡三种情况。任意一种称量方案都能唯一的表示成一棵判定树；反过来一棵判定树也唯一对应一种称量方案。容易看出判定树的深度就是称量次数。这就是我们之所以引进它的原因。做出判断之前，谁也无法预知哪个硬币是假币，每个都有可能是我们的目标；因此一个有意义的判定树应该具有至少n个叶子节点。n个叶子节点的树的深度h≥，故而可以证明，f(n)=是最优的。我们的结论是：有n（n≥3）个硬币，其中一个是假币，假币的重量比其他的要重一些。给一架天平，至少称次，就能找出那个假币。具体的方案是将硬币每次都尽量均匀的三分。让我们总结一下。“三分”是整个解法的核心。我们选择三分，而不是二分或者四分是有原因的，它的本质是由判定树的特殊结构——三叉树——所决定的。同时还必须注意一点，我们在三分的时候有两个字很讲究：“均匀”。实际上h≥中的“=”当且仅当硬币被均匀的分配时才能达到。这里说的“均匀”是指“在最坏情况下获得最好的效果”。因为一棵树的深度是由它根节点儿子中深度最大的儿子决定的，为了使得整个树深度最小，我们就要务必使得深度最大的儿子深度最小，这就是“均匀”分配的理论根据。练习：第12届全国青少年信息学奥林匹克联赛初赛题现有80枚硬币，其中有一枚是假币，其重量稍重，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。请写出你的结果：_________________________________________________。答案：4次；第一步，分成三组：27，27，26，将前2组放到天平上。二、取石子游戏的策略及其应用有一种很有意思的游戏，就是有物体若干堆，可以是石子或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。取石子游戏是我国民间流传已久的一种博奕，在国外亦称Nim游戏。别看这游戏极其简单，却蕴含着深刻的道理。下面我们来分析一下要如何才能够取胜。游戏Ⅰ有若干堆任意数目的小石子{a1，a2，…，am}(m≥1)，两人轮流取石子，每人每次可以从其中任意一堆中取，每次可以取1、2、3、……或k(1≤k≤min{a1，a2，…，am})颗石子，把石子取完的人为胜者。采用符号{a1，a2，…，am；k}来代表游戏Ⅰ中小石子的初始状况和限制条件，一个人取一次石子实际上就是把{a1，a2，…，am；k}中某个分量ai(1≤i≤m)减小为ai′，即{a1，a2，…，ai，…，am；k}—→{a1，a2，…，ai′，…，am；k}(0≤ai′<ai)，我们把这种取一次石子使数组发生的变换称为T变换，根据现成博奕论先驱冯·诺伊曼(VonNeumann)的“完全确定信息游戏必定存在一种确定的获胜策略”的经典理论，要么对先取者存在某种取法，即某个T变换，无论后取者如何取，先取者总有相应对策，直至最终取得胜利；要么无论先取者如何取，后取者可以找到某种T变换，保证后取者总有相应策略获胜。为了解决游戏{a1，a2，…，am；k}的对策，我们先看一个简单的例子。例1桌上放着一堆小石子一共100颗，两人(甲、乙)轮流取，每次可以取1至10颗，取完的人为胜者，怎样才能取胜？分析这个问题实际上是取石子游戏的特殊情形{100；10}，我们利用倒推法：容易看出11是取胜的关键数学，因为到此时，不论对方(甲)取多少颗(大于0且小于11)，总留下大于0且小于11颗石子，这样乙方一次取完即获得胜利。同样地分析，要取到11必须取到22，33，44，55，66，77，88，99，这样我们就知道了获胜之道：①先取1颗石子，留下99颗，然后对方取a(1≤a≤10)颗，己方取(11—a)颗，就总能掌握这种致胜的关键数，从而确保获胜。②如果对方先取，己方只需利用对方不知道其中奥秘，争取到一个致胜数，就总能依①中方法取到下一个致胜数，最后取得胜利。实际上，如果局中人均熟知获胜策略，那么开局的局势就已经完全决定了结局的输赢，例1其实是先取者必胜的局势，从这个例子的分析过程我们得到启示：可以用同余理论来探讨一般情况。一般地，在取石子游戏{a1，a2，…，am；k中，ai≡ai′(modk+1)(i=1，2，…，m)其中0≤ai′≤k，在{a1′，a2′，…，am′；k}中有取胜策略的一方在{a1，a2，…，am；k}中也有取胜策略。证明在{a1′，a2′，…，am′；k}中有获胜策略的一方，对于大于k的分量ai(i=1，2，…，m总能做到ai≡ai′(modk+1)，即对方取a(1≤≤k)，己方取k+1-a，使两人各取一次之后该分量减小k+1，也就对第i堆各取n(n≥1)次之后石子数便由ai=ai′+n(k+1)变成ai′，故在{a1′，a2′，…，am′；k}中有取胜策略的一方在{a1，a2，…，am；k}中也有取胜策略。游戏Ⅱ有若干堆任意数目的小石子{a1，a2，…，am}，两人轮流从中取石子，每人每次可以取走任意一堆中任意数目的石子，不能不取，把石子取完的人为胜者。采用m元数组{a1，a2，…，am}(m≥1)来描述这类取石子游戏，一人取走一次石子相当于用某个T变换把其中某个分量ai(1≤i≤m)减小为ai′，即{a1，a2，…，ai，…，am}T{a1，a2，…，ai′，…，am}(0≤ai′<ai)。有趣的是为了解决这类一般情况，我们需要用到整数的二进位制，把m元数组{a1，a2，…，am}中的每一个分量用二进位制数表示，ai(1≤i≤m)写在第i行，同时对齐二进位制数的位数，在列上作十进位制加法，其和写在第(m+1)行，记为{n1，n2，…，nj，…，nl}，如果所有这些和数nj(1≤j≤l)均为偶数，我们称这个m元数组为偶数组；若nj(1≤j≤l)，中有一个数为奇数，则称之为非偶数组。例如：对于3元数组{2，3，5}；a12010a23011a3510122n1n2n3因为其中n1=1，所以{2，3，5}是非偶数组。同样，对于3元数组{2，3，1}：a1210a2311a310122n1n2由于nj(j=1，2)为偶数，则{2，3，1}为偶数组。偶数组与非偶数组在T变换下具有如下性质：(1)偶数组经过一次T变换之后一定变为非偶数组；(2)对于非偶数组，一定可以找到某一个T变换，使其变为偶数组。这样我们容易判定：如果给定的m元数组是偶数组，则后取者必有获胜策略；相反，若给定m元数组为非偶数组，则先取者有方法获胜，因为给定的m元数组为偶数组，先取者无论怎样取，只能将偶数组变为非偶数组，后取者则有策略将此时的非偶数组变为偶数组，由于每次取走石子，剩下石子数目一定越来越小，而{0，0，…，0}是偶数组，所以后取者获胜，同理可证相反情况。例2有三堆石子，各堆数目分别是2、3、6，两人轮流取，取完的人为胜者，若甲先乙后，谁取胜？解：a12010a23011a36110131n1n2n3ni为奇数i=1，2，3，所以{2，3，6}为非偶数，我们可以判定：先取者甲获胜，依性质证明过程给出的操作方法，只需将a3=6变为1，可以验证{2，3，1}是偶数组，无论乙如只可能变成如下六种情形之一：{2，3，0}，1}，{2，1，1}，{2，0，1}，{1，3，1}，{0，3，1}，都是非偶数组，同样按原方法可以将其变2}或{1，1}，乙再取后，甲总能确保获胜。例3：第12届全国青少年信息学奥林匹克联赛初赛题现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：_________________________________________________。解：由游戏Ⅱ知，得到如下推理：19010011700011150001013000011010010(18)1050－18＝32所以第1次只能在第5堆石子中取32粒，使得取出32粒后为偶数组。最后我们看一道综合利用游戏Ⅰ、Ⅱ的例子：例4在3×25的棋盘上放着三颗石a、b、c(如图所示)，两人轮流将石子向右移人一次只可以移动其中一颗石子1至5后无格可走者为输家，若甲先行，乙后行，赢？abc解由25≡7(mod6)，根据游戏Ⅰ的策略{25，25，25；5}中有获胜策略的一方在{7，7，7；5}中也有获胜方法，又把石子由图中所示{3，2，6}移到{7，7，7}即相当于取石子游戏Ⅱ的{4，5，1}，由于{4，5，1}是偶数组，故先移者输。三、抽屉原理“抽屉原理”最先是由19世纪的德国数学家迪里赫莱（Dirichlet）运用于解决数学问题的，所以又称“迪里赫莱原理”，也有称“鸽巢原理”的。这个原理可以简单地叙述为“把10个苹果，任意分放在9个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果”。这个道理是非常明显的，但应用它却可以解决许多有趣的问题，并且常常得到一些令人惊异的结果。抽屉原理是国际国内各级各类信息学竞赛中的重要内容，本讲就来学习它的有关知识及其应用。一、知识点：定理1、如果把n+1个元素分成n个集合，那么不管怎么分，都存在一个集合，其中至少有两个元素。证明：（用反证法）若不存在至少有两个元素的集合，则每个集合至多1个元素，从而n个集合至多有n个元素，此与共有n+1个元素矛盾，故命题成立。在定理1的叙述中，可以把“元素”改为“物件”，把“集合”改成“抽屉”，抽屉原理正是由此得名。同样，可以把“元素”改成“鸽子”，把“分成n个集合”改成“飞进n个鸽笼中”。“鸽笼原理”由此得名。二、讲解范例：【例1】一个小组共有13名同学，其中至少有2名同学同一个月过生日。为什么？【分析】每年里共有12个月，任何一个人的生日，一定在其中的某一个月。如果把这12个月看成12个“抽屉”，把13名同学的生日看成13只“苹果”，把13只苹果放进12个抽屉里，一定有一个抽屉里至少放2个苹果，也就是说，至少有2名同学在同一个月过生日。【例2】任意4个自然数，其中至少有两个数的差是3的倍数。这是为什么？【分析与解】首先我们要弄清这样一条规律：如果两个自然数除以3的余数相同，那么这两个自然数的差是3的倍数。而任何一个自然数被3除的余数，或者是0，或者是1，或者是2，根据这三种情况，可以把自然数分成3类，这3种类型就是我们要制造的3个“抽屉”。我们把4个数看作“苹果”，根据抽屉原理，必定有一个抽屉里至少有2个数。换句话说，4个自然数分成3类，至少有两个是同一类。既然是同一类，那么这两个数被3除的余数就一定相同。所以，任意4个自然数，至少有2个自然数的差是3的倍数。【例3】有规格尺寸相同的5种颜色的袜子各15只混装在箱内，试问不论如何取，从箱中至少取出多少只就能保证有3双袜子（袜子无左、右之分）？【分析与解】试想一下，从箱中取出6只、9只袜子，能配成3双袜子吗？回答是否定的。按5种颜色制作5个抽屉，根据抽屉原理1，只要取出6只袜子就总有一只抽屉里装2只，这2只就可配成一双。拿走这一双，尚剩4只，如果再补进2只又成6只，再根据抽屉原理1，又可配成一双拿走。如果再补进2只，又可取得第3双。所以，至少要取6＋2＋2=10只袜子，就一定会配成3双。【例4】一个布袋中有35个同样大小的木球，其中白、黄、红三种颜色球各有10个，另外还有3个蓝色球、2个绿色球，试问一次至少取出多少个球，才能保证取出的球中至少有4个是同一颜色的球？【分析与解】从最“不利”的取出情况入手。最不利的情况是首先取出的5个球中，有3个是蓝色球、2个绿色球。接下来，把白、黄、红三色看作三个抽屉，由于这三种颜色球相等均超过4个，所以，根据抽屉原理2，只要取出的球数多于（4-1）×3=9个，即至少应取出10个球，就可以保证取出的球至少有4个是同一抽屉（同一颜色）里的球。故总共至少应取出10＋5=15个球，才能符合要求。思考：把题中要求改为4个不同色，或者是两两同色，情形又如何？当我们遇到“判别具有某种事物的性质有没有，至少有几个”这样的问题时，想到它——抽屉原理，这是你的一条“决胜”之路。【例5】.现有64只乒乓球，18个乒乓球盒，每个盒子里最多可以放6只乒乓球，至少有个乒乓球盒子里的乒乓球数目相同？【分析与解】：18个乒乓球盒，每个盒子里至多可以放6只乒乓球。为使相同乒乓球个数的盒子尽可能少，可以这样放：先把盒子分成6份，每份有18÷6=3（只），分别在每一份的3个盒子中放入1只、2只、3只、4只、5只、6只乒乓球，即3个盒子中放了1只乒乓球，3个盒中放了2只乒乓球……3个盒子中放了6只乒乓球。这样，18个盒子中共放了乒乓球（1+2+3+4+5+6）×3=63（只）。把以上6种不同的放法当做抽屉，这样剩下64-63=1（只）乒乓球不管放入哪一个抽屉里的任何一个盒子里（除已放满6只乒乓球的抽屉外），都将使该盒子中的乒乓球数增加1只，这时与比该抽屉每盒乒乓数多1的抽屉中的3个盒子里的乒乓球数相等。例如剩下的1只乒乓球放进原来有2只乒乓球的一个盒子里，该盒乒乓球就成了3只，再加上原来装有3只乒乓球的3个盒子，这样就有4个盒子里装有3个乒乓球。所以至少有4个乒乓球盒里的乒乓球数目相同。提示语抽屉原理还可以反过来理解：假如把n＋1个苹果放到n个抽屉里，放2个或2个以上苹果的抽屉一个也没有（与“必有一个抽屉放2个或2个以上的苹果”相反），那么，每个抽屉最多只放1个苹果，n个抽屉最多有n个苹果，与“n+1个苹果”的条件矛盾。运用抽屉原理的关键是“制造抽屉”。通常，可采用把n个“苹果”进行合理分类的方法来制造抽屉。比如，若干个同学可按出生的月份不同分为12类，自然数可按被3除所得余数分为3类等等。四、容斥问题在19世纪末，德国数学家康托系统地描绘了一个能够为全部数学提供基础的通用数学框架，他创立的这个学科一直是我们数学发展的根植地，这个学科就叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为，数学的所有内容都是在“集合”中讨论、生长的。容斥问题在信息学竞赛的问题求解中也经常出现。一、知识点1、集合与元素：把一类事物的全体放在一起就形成一个集合。每个集合总是由一些成员组成的，集合的这些成员，叫做这个集合的元素。如：集合A={0，1，2，3，……，9}，其中0，1，2，…9为A的元素。2、并集：由所有属于集合A或集合B的元素所组成的集合，叫做A，B的并集，记作A∪B，记号“∪”读作“并”。A∪B读作“A并B”，用图表示为图中阴影部分表示集合A，B的并集A∪B。例：已知6的约数集合为A={1，2，3，6}，10的约数集合为B={1，2，5，10}，则A∪B={1，2，3，5，6，10}3、交集：A、B两个集合公共的元素，也就是那些既属于A，又属于B的元素，它们组成的集合叫做A和B的交集，记作“A∩B”，读作“A交B”，如图阴影表示：例：已知6的约数集合A={1，2，3，6}，10的约数集合B={1，2，5，10}，则A∩B={1，2}。4、容斥原理（包含与排除原理）：（用|A|表示集合A中元素的个数，如A={1，2，3}，则|A|=3）原理一：给定两个集合A和B，要计算A∪B中元素的个数，可以分成两步进行：第一步：先求出∣A∣+∣B∣（或者说把A，B的一切元素都“包含”进来，加在一起）；第二步：减去∣A∩B∣（即“排除”加了两次的元素）总结为公式：|A∪B|=∣A∣+∣B∣-∣A∩B∣原理二：给定三个集合A，B，C。要计算A∪B∪C中元素的个数，可以分三步进行：第一步：先求∣A∣+∣B∣+∣C∣；第二步：减去∣A∩B∣，∣B∩C∣，∣C∩A∣；第三步：再加上∣A∩B∩C∣。即有以下公式：∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣B∩C∣-|C∩A|+|A∩B∩C∣二、解题思路：遇到集合问题，首先要弄请：集合里的元素是什么。集合新名词新概念多。如集合、元素、有限集、无限集、列举法、描述法、子集、真子集、空集、非空集合、全集、补集、交集、并集等。新关系新符号多，如属于、不属于、包含、包含于、真包含、真包含于、相等、不相等、相交、相并、互补(∈、、、、N、N※、Z、Q、R、∩、∪、CsA、I、＝、≠……)等，这些新概念新关系，多而抽象。在这千头万绪中，应该抓住“元素”这个关键，因为集合是由元素确定的，“子、全、补、交、并、空”等集合也都是通过元素来定义的。集合中元素的特征即“确定性”，“互异性”、“无序性”也就是元素的性质。集合的分类(有限集与无限集)与表示方法(列举法与描述法)也是通过元素来刻画的。元素是集合的基本内核，研究集合，首先就要确定集合里的元素是什么。三、例题分析：例1求不超过20的正整数中是2的倍数或3的倍数的数共有多少个。分析：设A={20以内2的倍数}，B={20以内3的倍数}，显然，要求计算2或3的倍数个数，即求∣A∪B∣。解1：A={2，4，6，…20}，共有10个元素，即|A|=10B={3，6，9，…18}，共有6个元素，即|B|=6A∩B={既是2的倍数又是3的倍数}={6，12，18}，共有3个元素，即|A∩B|=3所以∣A∪B∣=∣A∣+∣B∣-∣A∩B∣=10+6-3=13，即A∪B中共有13个元素。解2：本题可直观地用图示法解答如图,其中,圆A中放的是不超过20的正整数中2的倍数的全体;圆B中放的是不超过20的正整数中3的倍数的全体,其中阴影部分的数6,12,18是既是2的倍数又是3的倍数的数(即A∩B中的数)只要数一数集合A∪B中的数的个数即可。例2某班统计考试成绩，数学得90分上的有25人；语文得90分以上的有21人；两科中至少有一科在90分以上的有38人。问两科都在90分以上的有多少人？解：设A={数学成绩90分以上的学生}B={语文成绩90分以上的学生}那么，集合A∪B表示两科中至少有一科在90分以上的学生，由题意知，∣A∣=25，∣B∣=21，∣A∪B∣=38现要求两科均在90分以上的学生人数，即求∣A∩B∣，由容斥原理得∣A∩B∣=∣A∣+∣B∣-∣A∪B∣=25+21-38=8点评：解决本题首先要根据题意，设出集合A，B，并且会表示A∪B，A∩B，再利用容斥原理求解。例3某班同学中有39人打篮球，37人跑步，25人既打篮球又跑步，问全班参加篮球、跑步这两项体育活动的总人数是多少？解：设A={打篮球的同学}；B={跑步的同学}则A∩B={既打篮球又跑步的同学}A∪B={参加打篮球或跑步的同学}应用容斥原理∣A∪B∣=∣A∣+∣B∣-∣A∩B∣=39+37-25=51（人）例4某年级的课外学科小组分为数学、语文、外语三个小组，参加数学小组的有23人，参加语文小组的有27人，参加外语小组的有18人；同时参加数学、语文两个小组的有4人，同时参加数学、外语小组的有7人，同时参加语文、外语小组的有5人；三个小组都参加的有2人。问：这个年级参加课外学科小组共有多少人？解1：设A={数学小组的同学}，B={语文小组的同学}，C={外语小组的同学}，A∩B={数学、语文小组的同学}，A∩C={参加数学、外语小组的同学}，B∩C={参加语文、外语小组的同学}，A∩B∩C={三个小组都参加的同学}由题意知：∣A∣=23，∣B∣=27，∣C∣=18∣A∩B∣=4，∣A∩C∣=7，∣B∩C∣=5，∣A∩B∩C∣=2根据容斥原理二得：∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣A∩C|-∣B∩C|+|A∩B∩C∣=23+27+18-（4+5+7）+2=54（人）解2：利用图示法逐个填写各区域所表示的集合的元素的个数，然后求出最后结果。设A、B、C分别表示参加数学、语文、外语小组的同学的集合，其图分割成七个互不相交的区域，区域Ⅶ（即A∩B∩C）表示三个小组都参加的同学的集合，由题意，应填2。区域Ⅳ表示仅参加数学与语文小组的同学的集合，其人数为4-2=2（人）。区域Ⅵ表示仅参加数学与外语小组的同学的集合，其人数为7-2=5（人）。区域Ⅴ表示仅参加语文、外语小组的同学的集合，其人数为5-2=3（人）。区域Ⅰ表示只参加数学小组的同学的集合，其人数为23-2-2-5=14（人）。同理可把区域Ⅱ、Ⅲ所表示的集合的人数逐个算出，分别填入相应的区域内，则参加课外小组的人数为；14+20+8+2+5+3+2=54（人）点评：解法2简单直观，不易出错。由于各个区域所表示的集合的元素个数都计算出来了，因此提供了较多的信息，易于回答各种方式的提问。例5学校教导处对100名同学进行调查，结果有58人喜欢看球赛，有38人喜欢看戏剧，有52人喜欢看电影。另外还知道，既喜欢看球赛又喜欢看戏剧（但不喜欢看电影）的有6人，既喜欢看电影又喜欢看戏剧（但不喜欢看球赛）的有4人，三种都喜欢的有12人。问有多少同学只喜欢看电影？有多少同学既喜欢看球赛又喜欢看电影（但不喜欢看戏剧）？（假定每人至少喜欢一项）解法1：画三个圆圈使它们两两相交，彼此分成7部分（如图）这三个圆圈分别表示三种不同爱好的同学的集合，由于三种都喜欢的有12人，把12填在三个圆圈的公共部分内（图中阴影部分），其它6部分填上题目中所给出的不同爱好的同学的人数（注意，有的部分的人数要经过简单的计算）其中设既喜欢看电影又喜欢看球赛的人数为χ，这样，全班同学人数就是这7部分人数的和，即16+4+6+（40-χ）+（36-χ）+12=100解得χ=14只喜欢看电影的人数为36-14=22解法2：设A={喜欢看球赛的人}，B={喜欢看戏剧的人}，C={喜欢看电影的人}，依题目的条件有|A∪B∪C|=100，|A∩B|=6+12=18（这里加12是因为三种都喜欢的人当然喜欢其中的两种），|B∩C|=4+12=16，|A∩B∩C|=12，再设|A∩C|=12+χ由容斥原理二：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|得：100=58+38+52-（18+16+х+12）+12解得：х=14∴36-14=22所以既喜欢看电影又喜欢看球赛的人数为14，只喜欢看电影的人数为22。五、排列组合问题一、知识点：1分类计数原理：做一件事情，完成它可以有n类办法，在第一类办法中有种不同的方法，在第二类办法中有种不同的方法，……，在第n类办法中有种不同的方法那么完成这件事共有种不同的方法2.分步计数原理：做一件事情，完成它需要分成n个步骤，做第一步有种不同的方法，做第二步有种不同的方法，……，做第n步有种不同的方法，那么完成这件事有种不同的方法3．排列的概念：从个不同元素中，任取（）个元素（这里的被取元素各不相同）按照一定的顺序排成一列，叫做从个不同元素中取出个元素的一个排列4．排列数的定义：从个不同元素中，任取（）个元素的所有排列的个数叫做从个元素中取出元素的排列数，用符号表示5．排列数公式：（）6阶乘：表示正整数1到的连乘积，叫做的阶乘规定．7．排列数的另一个计算公式：=8组合的概念：一般地，从个不同元素中取出个元素并成一组，叫做从个不同元素中取出个元素的一个组合9．组合数的概念：从个不同元素中取出个元素的所有组合的个数，叫做从个不同元素中取出个元素的组合数．用符号表示．10．组合数公式：或11组合数的性质1：．规定：；2：＝+12．圆排列（1）由的个元素中，每次取出个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）．（2）圆排列有三个特点：（=1\*romani）无头无尾；（=2\*romanii）按照同一方向转换后仍是同一排列；（=3\*romaniii）两个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同，才是不同的圆排列．（3）定理：在的个元素中，每次取出个不同的元素进行圆排列，圆排列数为．13．可重排列允许元素重复出现的排列，叫做有重复的排列．在个不同的元素中，每次取出个元素，元素可以重复出现，按照一定的顺序那么第一、第二、…、第位是的选取元素的方法都是种，所以从个不同的元素中，每次取出个元素的可重复的排列数为．14．不尽相异元素的全排列如果个元素中，有个元素相同，又有个元素相同，…，又有个元素相同（），这个元素全部取的排列叫做不尽相异的个元素的全排列，它的排列数是15．可重组合（1）从个元素，每次取出个元素，允许所取的元素重复出现次的组合叫从个元素取出个有重复的组合．（2）定理：从个元素每次取出个元素有重复的组合数为：二、解题思路：排列组合题的求解策略（1）排除：对有限条件的问题，先从总体考虑，再把不符合条件的所有情况排除，这是解决排列组合题的常用策略．（2）分类与分步有些问题的处理可分成若干类，用加法原理，要注意每两类的交集为空集，所有各类的并集是全集；有些问题的处理分成几个步骤，把各个步骤的方法数相乘，即得总的方法数，这是乘法原理．（3）对称思想：两类情形出现的机会均等，可用总数取半得每种情形的方法数．（4）插空：某些元素不能相邻或某些元素在特殊位置时可采用插空法．即先安排好没有限制条件的元素，然后将有限制条件的元素按要求插入到排好的元素之间．（5）捆绑：把相邻的若干特殊元素“捆绑”为一个“大元素”，然后与其它“普通元素”全排列，然后再“松绑”，将这些特殊元素在这些位置上全排列．（6）隔板模型：对于将不可辨的球装入可辨的盒子中，求装的方法数，常用隔板模型．如将12个完全相同的球排成一列，在它们之间形成的11个缝隙中任意插入3块隔板，把球分成4堆，分别装入4个不同的盒子中的方法数应为，这也就是方程的正整数解的个数．解排列组合问题，首先要弄清一件事是“分类”还是“分步”完成，对于元素之间的关系，还要考虑“是有序”的还是“无序的”，也就是会正确使用分类计数原理和分步计数原理、排列定义和组合定义，其次，对一些复杂的带有附加条件的问题，需掌握以下几种常用的解题方法：三、讲解范例：一、相临问题——整体捆绑法例1．7名学生站成一排，甲、乙必须站在一起有多少不同排法？解：两个元素排在一起的问题可用“捆绑”法解决，先将甲乙二人看作一个元素与其他五人进行排列，并考虑甲乙二人的顺序，所以共有种。捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列.一般地:个人站成一排,其中某个人相邻,可用“捆绑”法解决，共有种排法。练习：5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法?分析此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素,并且要求她们要相邻,因此可以将她们看成是一个元素来解决问题.解因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全排列,有种排法,其中女生内部也有种排法,根据乘法原理,共有种不同的排法.二、不相临问题——选空插入法例2．7名学生站成一排，甲乙互不相邻有多少不同排法？解：甲、乙二人不相邻的排法一般应用“插空”法，所以甲、乙二人不相邻的排法总数应为：种.插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.若个人站成一排，其中个人不相邻，可用“插空”法解决，共有种排法。练习：学校组织老师学生一起看电影，同一排电影票12张。8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的坐法？分析此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊元素,在解决时就要特殊对待.所涉及问题是排列问题.解先排学生共有种排法,然后把老师插入学生之间的空档，共有7个空档可插,选其中的4个空档,共有种选法.根据乘法原理,共有的不同坐法为种.三、复杂问题——总体排除法或排异法有些问题直接法考虑比较难比较复杂，或分类不清或多种时，而它的反面往往比较简捷，可考虑用“排除法”，先求出它的反面,再从整体中排除.解决几何问题必须注意几何图形本身对其构成元素的限制。例3.正六边形的中心和顶点共7个点，以其中3个点为顶点的三角形共有个.解：从7个点中取3个点的取法有种，但其中正六边形的对角线所含的中心和顶点三点共线不能组成三角形，有3条，所以满足条件的三角形共有－3＝32个.练习：我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种?分析此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程.解43人中任抽5人的方法有种,正副班长,团支部书记都不在内的抽法有种,所以正副班长,团支部书记至少有1人在内的抽法有种.四、特殊元素——优先考虑法对于含有限定条件的排列组合应用题，可以考虑优先安排特殊位置，然后再考虑其他位置的安排。例4．1名老师和4名获奖学生排成一排照像留念，若老师不排在两端，则共有不同的排法种．解：先考虑特殊元素（老师）的排法，因老师不排在两端，故可在中间三个位置上任选一个位置，有种，而其余学生的排法有种，所以共有＝72种不同的排法.例5．乒乓球队的10名队员中有3名主力队员，派5名队员参加比赛，3名主力队员要安排在第一、三、五位置，其余7名队员选2名安排在第二、四位置，那么不同的出场安排共有种.解：由于第一、三、五位置特殊，只能安排主力队员，有种排法，而其余7名队员选出2名安排在第二、四位置，有种排法，所以不同的出场安排共有＝252种.五、多元问题——分类讨论法对于元素多，选取情况多，可按要求进行分类讨论，最后总计。例6．某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数为（A） A．42 B．30 C．20 D．12解：增加的两个新节目，可分为相临与不相临两种情况：1.不相临：共有A62种；2.相临：共有A22A61种。故不同插法的种数为：A62+A22A61=42，故选A。六、混合问题——先选后排法对于排列组合的混合应用题，可采取先选取元素，后进行排列的策略．例7．12名同学分别到三个不同的路口进行车流量的调查，若每个路口4人，则不同的分配方案共有（） A．种 B．种 C．种 D．种解：本试题属于均分组问题。则12名同学均分成3组共有种方法,分配到三个不同的路口的不同的分配方案共有：种，故选A。例8．从黄瓜、白菜、油菜、扁豆4种蔬菜品种中选出3种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有（）

A．24种

B．18种

C．12种

D．6种

解:先选后排,分步实施.由题意，不同的选法有:C32种,不同的排法有:A31·A22,故不同的种植方法共有A31·C32·A22=12，故应选C.七．相同元素分配——档板分隔法例9．把10本相同的书发给编号为1、2、3的三个学生阅览室，每个阅览室分得的书的本数不小于其编号数，试求不同分法的种数。请用尽可能多的方法求解，并思考这些方法是否适合更一般的情况？本题考查组合问题。解：先让2、3号阅览室依次分得1本书、2本书；再对余下的7本书进行分配，保证每个阅览室至少得一本书，这相当于在7本相同书之间的6个“空档”内插入两个相同“I”（一般可视为“隔板”）共有种插法，即有15种分法。八．转化法:对于某些较复杂的、或较抽象的排列组合问题，可以利用转化思想,将其化归为简单的、具体的问题来求解.例10高二年级8个班,组织一个12个人的年级学生分会,每班要求至少1人,名额分配方案有多少种?分析此题若直接去考虑的话,就会比较复杂.但如果我们将其转换为等价的其他问题,就会显得比较清楚,方法简单,结果容易理解.解：此题可以转化为:将12个相同的白球分成8份,有多少种不同的分法问题,因此须把这12个白球排成一排,在11个空档中放上7个相同的黑球,每个空档最多放一个,即可将白球分成8份,显然有种不同的放法,所以名额分配方案有种.总之，排列、组合应用题的解题思路可总结为：排组分清，加乘明确；有序排列，无序组合；分类为加，分步为乘。具体说，解排列组合的应用题，通常有以下途径：（1）以元素为主体，即先满足特殊元素的要求，再考虑其他元素。（2）以位置为主体，即先满足特殊位置的要求，再考虑其他位置。（3）先不考虑附加条件，计算出排列或组合数，再减去不合要求的排列组合数。六、逻辑推理问题通常把只涉及一些相互关联（或依存）条件或关系，极少给出（不直接赋与）数量关系与几何图形的一类非标准（常规）数学问题叫逻辑推理问题，处理这类问题，要从一些关联的条件出发，应用某些数学知识，甚至日常生活常识，依据一定的思维规律（机智灵活、准确敏捷的思考），通过分析、推理、排除不可能情况（剔除不合理成分），然后作出正确的判断。逻辑推理问题中常用到以下三条逻辑基本规律：（1）同一律：是指同一东西（对象）。它是什么就是什么，不能模棱两可，亦此亦彼；（2）矛盾律：是指互相对立（矛盾）的事不能都真，二者必有一假（即同一思想不能既真又假）；（3）排中律：是指两个不相容的判断不能都假，二者必有一真（即任何判断或同一思想不能既不真也不假）。逻辑推理问题条件扑朔迷离，层次重叠纷纭，没有一定的定理可以依据，无现成公式可用，无模式可循，靠的是逻辑推理。可画框图、紧抓关系、细抠条件，寻找突破口，穷追到底，层层进逼，以求找到答案。本文结合一些赛题,谈谈处理逻辑推理问题的一些主要方法。一、利用逻辑原理,直接推理对于一些简单的逻辑推理问题,往往只需以似真推理为主,直接通过分析就可以得出正确的结果。用这种方法解决“真假话”问题尤为有效。住在某个旅馆的同一房间的四个人A、B、C、D正在听一组流行音乐，她们当中有一个人在修指甲，一个人在写信，一个人躺在床上，另一个人在看书。1.A不在修指甲，也不在看书；2.B不躺在床上，也不在修指甲；3.如果A不躺在床上，那么D不在修指甲；4.C既不在看书，也不在修指甲；5.D不在看书，也不躺在床上。她们各自在做什么呢？由1、2、4、5知，既不是A、B在修指甲，也不是C在修指甲，因此修指甲的应该是D；但这与3的结论相矛盾，所以3的前提肯定不成立，即A应该是躺在床上；在4中C既不看书又不修指甲，由前面分析，C又不可能躺在床上，所以C是在写信；而B则是在看书。二、利用表格辅助推理某些逻辑推理问题中,有时会涉及很多对象,每个对象又有几种不同情况,同时还给出不同对象之间不同情况的判断,要求推出确定的结论。对于这类问题,通常可以利用表格把本来凌乱的信息集中整理出来,方便推理。甲、乙、丙、丁、戊五名同学参加推铅球比赛，通过抽签决定出赛顺序，在未公布顺序之前每人都对出赛顺序进行了猜测。甲猜：乙第三，丙第五；乙猜：戊第四，丁第五；丙猜：甲第一，戊第四；丁猜：丙第一，乙第二；戊猜：甲第三，丁第四。老师说每人的出赛顺序都至少被一人所猜中。第一、第三、第五分别是哪位同学？解：本题相互关系过于复杂，不便分析和推断，不妨由已知条件列表如下：由于每人的出赛顺序至少被一人所猜中，所以戊第四，丁第五，丙第一，甲第三，乙第二；出赛的顺序：丙乙甲戊丁例5.某校举办作文比赛，A、B、C、D四位同学参加比赛，其中只有一位同学获奖。老师为了解比赛情况，分别向选手询问，回答如下：A：我获了奖； B：我没有获奖，C也没有获奖C：是A获奖或B获奖 D：是B获奖事后证实，有两人的话符合事实，哪位同学获了奖？解：“某人获奖”就将此人记为“1”，否则为“0”。根据四个人的话可得下表。由表可知，若是A获奖，则有3人说的话符合事实，只有B获奖时，有两人的话符合事实。三、利用计算辅助推理某些逻辑推理问题常常有几个未知量同时存在,或答案有多种可能性,解题时需要充分利用已知条件进行计算,并通过对计算结果的分析,推理得出正确的结论。例5学校进行了一次考试，考试的科目是语文、历史、数学、物理和英语，每科满分为5分，其余等级依次是4、3、2、1分。今已知按总分由多到少排列着五名学生，A、B、C、D、E满足下列条件：（1）在同一科目中以及在总分数中没有得同样分数的人；（2）A的总分是24分；（3）C有四门得了相同的分数；（4）E语文得3分，物理得5分；（5）D的历史得4分。试求题目中未直接给出的各人其它各科的成绩？讲解:先从五人的总分入手，再扣掉A的得分，得出B、C、D、E四人的总分，再从得分最低的E出发进行推断，即可逐步得出结果。（1）由已知可得5人的总分为5×(1+2+3+4+5)=75分。因A得24分，故B、C、D、E共得75－24=51分又E两科得8分，故E（还有三科）至少得11分稍加验算可知：B、C、D、E的得分情况应该是15、13、12、11。（2）E两科8分，总分11分，因而E的英语、历史、数学各得1分。（3）A的总分是24分，故只有一科得4分，其它各科均是5分，因E的物理得4分，故语文、历史、数学、英语各五分。（4）C的总分为13分，且有四科得分相同，故得分情况只能是一科五分，四科各2分或一科1分，四科各3分。因5分为A、E所得，则C的四科各得3分，一科得1分，又因E语文得3分，故C语文得1分，其余各科得3分。（5）D的总分是12分，历史得4分，余下8分，因全部5分为A、E所得，全部3分为C、E所得，四个1分为C、E所得，故除历史外，D的其它各科各得2分。显然，B的语文、数学、英语皆得4分，历史2分，物理1分。【例9】赵、钱、孙、李四人，一个是教师，一个是售货员，一个是工人，一个是机关干部。试根据以下条件，判断这四人的职业。（1）赵和钱是邻居，每天一起骑车上班；（2）钱比孙年龄大；（3）赵在教李打太极拳；（4）教师每天步行去上班；（5）售货员的邻居不是机关干部；（6）机关干部和工人互不相识；（7）机关干部比售货员和工人年龄都大。【分析】由条件（4）和条件（1）可知赵、钱都不是教师。由条件（2）和条件（7），可推知孙不是干部。如果是的话，钱不是工人或售货员，钱又不是教师。于是，钱也是干部，矛盾。这样我们得到下表。下面几步推理也用表格说明。四、利用图形辅助推理美国数学家斯蒂恩说过:“如果一个特定的问题可以被转化成一个图形,那么,思想就整体地把握了问题,并且能创造性地思索问题解法。”A、B、C、D、E五支球队进行单循环比赛（每两支球队间都要进行一场比赛），当比赛进行到一定阶段时，统计A、B、C、D四个球队已经赛过的场数，依次为A队4场，B队3场，C队2场，D队1场，这时，E队已赛过的场数是（）A.1 B.2 C.3 D.4解：用五个点分别表示A、B、C、D、E五支球队，将它们之间比赛的情况用图1表示出来。A队已经赛过4场，由于是“单循环比赛”，这说明A与B、C、D、E四支球队各赛了1场；D队赛过1场，是与A队赛过的；B队3场，不可能与D队比赛，是与A、C、E各赛1场；C队2场，是与A、B赛的，从图中可以看出，E队已经赛了2场。七、递推关系的建立及在信息学竞赛中的应用瞬息变幻的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。即是说，某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。所谓“三岁看老”，说的就是这个道理。这一道理也正体现了递推的思想。递推关系几乎在所有的数学分支中都有重要作用，在一切向“更快、更高、更强”看齐的当今信息学奥林匹克竞赛中更因简洁高效而显示出其独具的魅力。在递推关系发挥重要作用的今天，深入研究其性质、特点便成为一件十分必要的事情。本文就将围绕着递推关系的三大基本问题中的如何建立递推关系展开论述，并通过例题说明递推关系在当今信息学竞赛中的应用。递推关系的定义相信每个人对递推关系都不陌生，但若要说究竟满足什么样的条件就是递推关系，可能每个人又会有不同的说法。为了更好地研究递推关系，首先让我们明确什么是递推关系。【定义1】给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hn(0i<n)联系起来，这样的式子就叫做递推关系。递推关系的建立递推关系中存在着三大基本问题：如何建立递推关系，已给的递推关系有何性质，以及如何求解递推关系。建立递推关系的关键在于寻找第n项与前面几项的关系式，以及初始项的值。它不是一种抽象的概念，是需要针对某一具体题目或一类题目而言的。在下文中，我们将对五种典型的递推关系的建立作比较深入具体的讨论。1．四种典型的递推关系Ⅰ.Fibonacci数列在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中，就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中，Fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题的提出：有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？解：设满x个月共有兔子Fx对，其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数目设为Ox对。则：Fx=Nx+Ox而Ox=Fx-1，Nx=Ox-1=Fx-2(即第x-2个月的所有兔子到第x个月都有繁殖能力了)∴Fx=Fx-1+Fx-2 边界条件：

F0=0，F1=1由上面的递推关系可依次得到F2=F1+F0=1，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，……。Ⅱ.Hanoi塔问题问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。abcabc图1要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？解：设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。∴hn=2hn-1+1边界条件：hn-1=1Ⅲ.平面分割问题问题的提出：11321132412346578图21234567108911121314n=1n=2n=3n=4解：设an为n条封闭曲线把平面分割成的区域个数。由图2可以看出：a2-a1=2；a3-a2=4；a4-a3=6。从这些式子中可以看出an-an-1=2(n-1)。当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后，第n-1条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，且第n条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an