1、信息学竞赛中问题求解题常见考查题型分析问题求解是信息技术竞赛初赛中常见题型，它共两题，每题 5 分，共 10分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合问题、逻辑推理、递推关系等问题出现在问题求解中，但是在实际的竞赛中，问题求解得分率往往是不高的，下面我对问题求解的题型进行了一下探索。一、寻找假币问题有 n（n3）个硬币，其中一个是假币，已知假币的重量比其他的要重一些，你有一架天平。现在要称出哪个假币来。解析：首先我们先来考虑最简单的问题 1。为了方便叙述，把 n 个硬币按 1,2,n顺次编号。若 n=3，把一号硬币放在天平左边、二号硬币放在天平右边。如果天平：1、左偏，一号重，是
2、假币。2、右偏，二号重，是假币。3、保持平衡，那么一、二都是正常的硬币，因此就只有可能三号硬币是假币了。因此 n=3，至多一次就能称出哪个是假币。记作 f(3)=1。下面考虑 n=9。把所有的硬币分成三组：A1,2,3,B4,5,6,C7,8,9。A 组的硬币放在左边、B 组放在右边。如果天平：1、左偏，则假币在 A 组里面。2、右偏，则假币在 B 组里面。3、保持平衡，假币在 C 组里面。无论在哪个组里面，我们已经把假币的范围从“9”缩小到了“3”，也就是减少到原来的 1/3。之前我们已经研究过，3 个硬币 1 次就能称出来，故而f(9)=2。不难推广到一般的情况：定理 1.1 f(3n)=
3、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.2 f(n)= n3log这个的证明和定理 1.1 完全类似，分 n mod 3 = 0, 1, 2 适当讨论即可。我们必须注意到 是可行的，因为我们能够
4、构造出这样一个方案。问题3l是它是否最优？我们采取的方案是每次将硬币尽量均匀的三分，这样做的根据就是天平只有三种结果：左偏、右偏、平衡。于是就能保证无论假币在哪一份都能将结果的范围缩小到原来的 1/3。从感性上认识， 应该就是最优解了。n3log为了更加严格的证明 的最优性，我们引进判定树的概念。n3log下图就是 n=9 时的一种判定树：比较(1,2,3)与(4,5,6) = 1 3= 7 9= 4 6= 5此题的判定树是这样一棵树：1、叶子节点代表一种可能的结果。2、非叶子节点代表一次称量。3、非叶子节点至多有三个儿子，分别代表天平的左偏、右偏、平衡三种情况。任意一种称量方案都能唯一的表示
5、成一棵判定树；反过来一棵判定树也唯一对应一种称量方案。容易看出判定树的深度就是称量次数。这就是我们之所以引进它的原因。做出判断之前，谁也无法预知哪个硬币是假币，每个都有可能是我们的目标；因此一个有意义的判定树应该具有至少 n 个叶子节点。n 个叶子节点的树的深度 h ，故而可以证明， f(n)= 是最3logn3log优的。我们的结论是：有 n（n 3）个硬币，其中一个是假币，假币的重量比其他的要重一些。给一架天平，至少称 次，就能找出那个假币。n3l具体的方案是将硬币每次都尽量均匀的三分。让我们总结一下。“三分”是整个解法的核心。我们选择三分，而不是二分或者四分是有原因的，它的本质是由判定树
6、的特殊结构三叉树所决定的。同时还必须注意一点，我们在三分的时候有两个字很讲究：“均匀”。实际上 h 中的“= ”当且仅当硬币被均匀的分配时才能达到。n3log这里说的“均匀”是指“在最坏情况下获得最好的效果”。因为一棵树的深度是由它根节点儿子中深度最大的儿子决定的，为了使得整个树深度最小，我们就要务必使得深度最大的儿子深度最小，这就是“均匀”分配的理论根据。练习：第 12 届全国青少年信息学奥林匹克联赛初赛题 现有 80 枚硬币，其中有一枚是假币，其重量稍重，所有真币的重量都相同，如果使 用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第 1 次的称重方法。请写出你的结果：_。
7、答案：4 次 ；第一步，分成三组：27，27，26，将前 2 组放到天平上。二、取石子游戏的策略及其应用有一种很有意思的游戏，就是有物体若干堆，可以是石子或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。取石子游戏是我国民间流传已久的一种博奕，在国外亦称 Nim 游戏。别看这游戏极其简单，却蕴含着深刻的道理。下面我们来分析一下要如何才能够取胜。游戏 有若干堆任意数目的小石子a1，a2，am(m1)，两人轮流取石子，每人每次可以从其中任意一堆中取，每次可以取 1、2、3、或k(1kmina1，a2，am)颗石子，把石子取完的人为胜者。采用符号a1，a2，am；k来代表游戏中
8、小石子的初始状况和限制条件，一个人取一次石子实际上就是把a1，a2，am；k中某个分量ai(1im)减小为 ai，即a1，a2，ai，am；ka1，a2，ai，am；k(0aiai)，我们把这种取一次石子使数组发生的变换称为 T 变换，根据现成博奕论先驱冯诺伊曼(VonNeumann)的“完全确定信息游戏必定存在一种确定的获胜策略”的经典理论，要么对先取者存在某种取法，即某个 T 变换，无论后取者如何取，先取者总有相应对策，直至最终取得胜利；要么无论先取者如何取，后取者可以找到某种 T 变换，保证后取者总有相应策略获胜。为了解决游戏a1，a2，am；k的对策，我们先看一个简单的例子。例 1 桌
9、上放着一堆小石子一共 100 颗，两人(甲、乙)轮流取，每次可以取1 至 10 颗，取完的人为胜者，怎样才能取胜？分析这个问题实际上是取石子游戏的特殊情形100；10，我们利用倒推法：容易看出 11 是取胜的关键数学，因为到此时，不论对方(甲)取多少颗(大于 0且小于 11)，总留下大于 0 且小于 11 颗石子，这样乙方一次取完即获得胜利。同样地分析，要取到 11 必须取到 22，33，44，55，66，77，88，99，这样我们就知道了获胜之道：先取 1 颗石子，留下 99 颗，然后对方取 a(1a10)颗，己方取(11a)颗，就总能掌握这种致胜的关键数，从而确保获胜。如果对方先取，己方只
10、需利用对方不知道其中奥秘，争取到一个致胜数，就总能依中方法取到下一个致胜数，最后取得胜利。实际上，如果局中人均熟知获胜策略，那么开局的局势就已经完全决定了结局的输赢，例 1 其实是先取者必胜的局势，从这个例子的分析过程我们得到启示：可以用同余理论来探讨一般情况。一般地，在取石子游戏a1，a2，am；k 中，aiai(modk+1)(i=1，2，m)其中 0aik，在a1，a2，am；k中有取胜策略的一方在a1，a2，am；k中也有取胜策略。证明 在a1，a2，am；k中有获胜策略的一方，对于大于 k 的分量ai(i=1，2，m 总能做到 aiai(modk+1)，即对方取 a(1k)，己方取k
11、+1-a，使两人各取一次之后该分量减小 k+1，也就对第 i 堆各取 n(n1)次之后石子数便由 ai=ai+n(k+1)变成 ai，故在a1，a2，am；k中有取胜策略的一方在a1，a2，am；k中也有取胜策略。游戏 有若干堆任意数目的小石子a1，a2，am，两人轮流从中取石子，每人每次可以取走任意一堆中任意数目的石子，不能不取，把石子取完的人为胜者。采用 m 元数组a1，a2，am(m1)来描述这类取石子游戏，一人取走一次石子相当于用某个 T 变换把其中某个分量 ai(1im)减小为 ai，即a1，a2，ai，amTa1，a2，ai，am(0aiai)。有趣的是为了解决这类一般情况，我们需
12、要用到整数的二进位制，把 m 元数组a1，a2，am中的每一个分量用二进位制数表示，ai(1im)写在第i 行，同时对齐二进位制数的位数，在列上作十进位制加法，其和写在第(m+1)行，记为n1，n2，nj，nl，如果所有这些和数 nj(1jl)均为偶数，我们称这个 m 元数组为偶数组；若 nj(1jl)，中有一个数为奇数，则称之为非偶数组。例如：对于 3 元数组2，3，5；a1 2 0 1 0a2 3 0 1 1a3 5 1 0 11 2 2 n1 n2 n3因为其中 n1=1，所以2，3，5是非偶数组。同样，对于 3 元数组2，3，1：a1 2 1 0a2 3 1 1a3 1 0 12 2n
13、1 n2由于 nj(j=1，2)为偶数，则2，3，1为偶数组。偶数组与非偶数组在 T 变换下具有如下性质：(1)偶数组经过一次 T 变换之后一定变为非偶数组；(2)对于非偶数组，一定可以找到某一个 T 变换，使其变为偶数组。这样我们容易判定：如果给定的 m 元数组是偶数组，则后取者必有获胜策略；相反，若给定 m 元数组为非偶数组，则先取者有方法获胜，因为给定的 m元数组为偶数组，先取者无论怎样取，只能将偶数组变为非偶数组，后取者则有策略将此时的非偶数组变为偶数组，由于每次取走石子，剩下石子数目一定越来越小，而0，0，0是偶数组，所以后取者获胜，同理可证相反情况。例 2 有三堆石子，各堆数目分别
14、是 2、3、6，两人轮流取，取完的人为胜者，若甲先乙后，谁取胜？解：a1 2 0 1 0a2 3 0 1 1a3 6 1 1 01 3 1n1 n2 n3ni 为奇数 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，1
15、9，50，甲乙两人轮流从任一堆中任取 （每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论 乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果： _。解：由游戏知，得到如下推理：19 0100117 0001115 0001013 000011010010 (18)10501832所以第 1 次只能在第 5 堆石子中取 32 粒，使得取出 32 粒后为偶数组。最后我们看一道综合利用游戏、的例子：例 4 在 325 的棋盘上放着三颗石 a、b、c(如图所示)，两人轮流将石子向右移人一次只可以移动其中一颗石子 1 至 5
16、 后无格可走者为输家，若甲先行，乙后行，赢？abc解 由 257(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 个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果”。这个道理是非常明显的，但应用它却可以解决许多有趣的问题，
17、并且常常得到一些令人惊异的结果。抽屉原理是国际国内各级各类信息学竞赛中的重要内容，本讲就来学习它的有关知识及其应用。一、知识点：定理 1、如果把 n+1 个元素分成 n 个集合，那么不管怎么分，都存在一个集合，其中至少有两个元素。 证明：（用反证法）若不存在至少有两个元素的集合，则每个集合至多 1个元素，从而 n 个集合至多有 n 个元素，此与共有 n+1 个元素矛盾，故命题成立。 在定理 1 的叙述中，可以把“元素”改为“物件”，把“集合”改成“抽屉”，抽屉原理正是由此得名。 同样，可以把“元素”改成“鸽子”，把“分成 n 个集合”改成“飞进 n个鸽笼中”。“鸽笼原理”由此得名。 二、讲解范
18、例：【例 1】一个小组共有 13 名同学，其中至少有 2 名同学同一个月过生日。为什么？【分析】每年里共有 12 个月，任何一个人的生日，一定在其中的某一个月。如果把这 12 个月看成 12 个“抽屉”，把 13 名同学的生日看成 13 只“苹果”，把 13 只苹果放进 12 个抽屉里，一定有一个抽屉里至少放 2 个苹果，也就是说，至少有 2 名同学在同一个月过生日。【例 2】任意 4 个自然数，其中至少有两个数的差是 3 的倍数。这是为什么？【分析与解】首先我们要弄清这样一条规律：如果两个自然数除以 3 的余数相同，那么这两个自然数的差是 3 的倍数。而任何一个自然数被 3 除的余数，或者是
19、 0，或者是 1，或者是 2，根据这三种情况，可以把自然数分成 3 类，这 3种类型就是我们要制造的 3 个“抽屉”。我们把 4 个数看作“苹果”，根据抽屉原理，必定有一个抽屉里至少有 2 个数。换句话说，4 个自然数分成 3 类，至少有两个是同一类。既然是同一类，那么这两个数被 3 除的余数就一定相同。所以，任意 4 个自然数，至少有 2 个自然数的差是 3 的倍数。【例 3】有规格尺寸相同的 5 种颜色的袜子各 15 只混装在箱内，试问不论如何取，从箱中至少取出多少只就能保证有 3 双袜子（袜子无左、右之分）？【分析与解】试想一下，从箱中取出 6 只、9 只袜子，能配成 3 双袜子吗？回答
20、是否定的。按 5 种颜色制作 5 个抽屉，根据抽屉原理 1，只要取出 6 只袜子就总有一只抽屉里装 2 只，这 2 只就可配成一双。拿走这一双，尚剩 4 只，如果再补进 2 只又成 6 只，再根据抽屉原理 1，又可配成一双拿走。如果再补进2 只，又可取得第 3 双。所以，至少要取 622=10 只袜子，就一定会配成 3双。【例 4】一个布袋中有 35 个同样大小的木球，其中白、黄、红三种颜色球各有10 个，另外还有 3 个蓝色球、2 个绿色球，试问一次至少取出多少个球，才能保证取出的球中至少有 4 个是同一颜色的球？【分析与解】从最“不利”的取出情况入手。最不利的情况是首先取出的 5 个球中，
21、有 3 个是蓝色球、2 个绿色球。接下来，把白、黄、红三色看作三个抽屉，由于这三种颜色球相等均超过4 个，所以，根据抽屉原理 2，只要取出的球数多于（4-1）3=9 个，即至少应取出 10 个球，就可以保证取出的球至少有 4 个是同一抽屉（同一颜色）里的球。故总共至少应取出 105=15 个球，才能符合要求。思考：把题中要求改为 4 个不同色，或者是两两同色，情形又如何？当我们遇到“判别具有某种事物的性质有没有，至少有几个”这样的问题时，想到它抽屉原理，这是你的一条“决胜”之路。【例 5】.现有 64 只乒乓球，18 个乒乓球盒，每个盒子里最多可以放 6 只乒乓球，至少有 个乒乓球盒子里的乒乓
22、球数目相同？【分析与解】：18 个乒乓球盒，每个盒子里至多可以放 6 只乒乓球。为使相同乒乓球个数的盒子尽可能少，可以这样放：先把盒子分成 6 份，每份有186=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 只乒乓球的抽屉外），都将使该盒子中的乒乓球数增加
23、 1 只，这时与比该抽屉每盒乒乓数多 1 的抽屉中的 3个盒子里的乒乓球数相等。例如剩下的 1 只乒乓球放进原来有 2 只乒乓球的一个盒子里，该盒乒乓球就成了 3 只，再加上原来装有 3 只乒乓球的 3 个盒子，这样就有 4 个盒子里装有 3 个乒乓球。所以至少有 4 个乒乓球盒里的乒乓球数目相同。提示语抽屉原理还可以反过来理解：假如把 n1 个苹果放到 n 个抽屉里，放 2个或 2 个以上苹果的抽屉一个也没有（与“必有一个抽屉放 2 个或 2 个以上的苹果”相反），那么，每个抽屉最多只放 1 个苹果，n 个抽屉最多有 n 个苹果，与“n+1 个苹果”的条件矛盾。运用抽屉原理的关键是“制造抽屉
24、”。通常，可采用把 n 个“苹果”进行合理分类的方法来制造抽屉。比如，若干个同学可按出生的月份不同分为 12类，自然数可按被 3 除所得余数分为 3 类等等。四、容斥问题在 19 世纪末，德国数学家康托系统地描绘了一个能够为全部数学提供基础的通用数学框架，他创立的这个学科一直是我们数学发展的根植地，这个学科就叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为，数学的所有内容都是在“集合”中讨论、生长的。容斥问题在信息学竞赛的问题求解中也经常出现。一、知识点1、集合与元素：把一类事物的全体放在一起就形成一个集合。每个集合总是由一些成员组成的，集合的这些成员，叫做这个集合的元素。如
25、：集合 A=0，1，2，3，9，其中 0，1，2，9 为 A 的元素。2、并集：由所有属于集合 A 或集合 B 的元素所组成的集合，叫做 A，B 的并集，记作 AB，记号“”读作“并”。AB 读作“A 并 B”，用图表示为图中阴影部分表示集合 A，B 的并集 AB。例：已知 6 的约数集合为 A=1，2，3，6，10 的约数集合为 B=1，2，5，10，则 AB=1，2，3，5，6，103、交集：A、B 两个集合公共的元素，也就是那些既属于 A，又属于 B 的元素，它们组成的集合叫做 A 和 B 的交集，记作“AB”，读作“A 交 B”，如图阴影表示：例：已知 6 的约数集合 A=1，2，3，6，10 的约数集合 B=1，2，5，10，则AB=1，2。4、容斥原理（包含与排除原理）：（用|A|表示集合 A 中元素的个数，如 A=1，2，3，则|A|=3）
