备战NOIP2010提高组初赛复习——问题求解篇

备战NOIP2010提高组初赛复习——问题求解篇

问题求解是信息技术竞赛初赛中常见题型，它共两题，每题5分，共10分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合问题、逻辑推理、递推关系等问题出现在问题求解中，但是在实际的竞赛中，问题求解得分率往往是不高的，下面我对问题求解的题型进行了一下探索。

一、寻找假币问题

有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.1 f(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、左偏，假币在A

2、右偏，假币在B

3、平衡，假币在C

无论哪种结果，我们都把假币的范围缩小到了3k 个硬币里面。而f(3k)=k ，

故而f(3k+1)=k+1。

综上，定理1.1成立。

稍经分析不难得到：

定理1.2 f(n)= ??n 3log

这个的证明和定理1.1完全类似，分n mod 3 = 0, 1, 2适当讨论即可。

我们必须注意到??n 3log 是可行的，因为我们能够构造出这样一个方案。问题

是它是否最优？

我们采取的方案是每次将硬币尽量均匀的三分，这样做的根据就是天平只有

三种结果：左偏、右偏、平衡。于是就能保证无论假币在哪一份都能将结果的范

围缩小到原来的1/3。从感性上认识，??n 3log 应该就是最优解了。

为了更加严格的证明??n 3log 的最优性，我们引进判定树的概念。

下图就是n=9时的一种判定树：

此题的判定树是这样一棵树： 1、叶子节点代表一种可能的结果。

1 3 2

7 9 8 4 6 5

2、非叶子节点代表一次称量。

3、非叶子节点至多有三个儿子，分别代表天平的左偏、右偏、平衡三种情况。

任意一种称量方案都能唯一的表示成一棵判定树；反过来一棵判定树也唯一对应一种称量方案。

容易看出判定树的深度就是称量次数。这就是我们之所以引进它的原因。

做出判断之前，谁也无法预知哪个硬币是假币，每个都有可能是我们的目标；因此一个有意义的判定树应该具有至少n个叶子节点。

n个叶子节点的树的深度h ???n3

log是最

log，故而可以证明，f(n)= ??n3

优的。

我们的结论是：有n（n?3）个硬币，其中一个是假币，假币的重量比其他的要重一些。给一架天平，至少称??n3

log次，就能找出那个假币。

具体的方案是将硬币每次都尽量均匀的三分。

让我们总结一下。

“三分”是整个解法的核心。我们选择三分，而不是二分或者四分是有原因的，它的本质是由判定树的特殊结构——三叉树——所决定的。

同时还必须注意一点，我们在三分的时候有两个字很讲究：“均匀”。实际上h ???n3

log中的“=”当且仅当硬币被均匀的分配时才能达到。

这里说的“均匀”是指“在最坏情况下获得最好的效果”。因为一棵树的深度是由它根节点儿子中深度最大的儿子决定的，为了使得整个树深度最小，我们就要务必使得深度最大的儿子深度最小，这就是“均匀”分配的理论根据。

练习：第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′

例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′

有趣的是为了解决这类一般情况，我们需要用到整数的二进位制，把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}；

a1 2 0 1 0

a2 3 0 1 1

a3 5 1 0 1

1 2 2

n1 n2 n3

因为其中n1=1，所以{2，3，5}是非偶数组。

同样，对于3元数组{2，3，1}：

a1 2 1 0

a2 3 1 1

a3 1 0 1

2 2

n1 n2

由于nj(j=1，2)为偶数，则{2，3，1}为偶数组。

偶数组与非偶数组在T变换下具有如下性质：

(1)偶数组经过一次T变换之后一定变为非偶数组；

(2)对于非偶数组，一定可以找到某一个T变换，使其变为偶数组。

这样我们容易判定：如果给定的m元数组是偶数组，则后取者必有获胜策略；相反，若给定m元数组为非偶数组，则先取者有方法获胜，因为给定的m元数组为偶数组，先取者无论怎样取，只能将偶数组变为非偶数组，后取者则有策略将此时的非偶数组变为偶数组，由于每次取走石子，剩下石子数目一定越来越小，而{0，0，…，0}是偶数组，所以后取者获胜，同理可证相反情况。

例2 有三堆石子，各堆数目分别是2、3、6，两人轮流取，取完的人为胜者，若甲先乙后，谁取胜？

解：

a1 2 0 1 0

a2 3 0 1 1

a3 6 1 1 0

1 3 1

n1 n2 n3

ni为奇数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，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果： _________________________________________________。

解：由游戏Ⅱ知，得到如下推理：

19 010011

7 000111

5 000101

3 000011

010010 (18)

10

50－18＝32

所以第1次只能在第5堆石子中取32粒，使得取出32粒后为偶数组。

最后我们看一道综合利用游戏Ⅰ、Ⅱ的例子：

例4在3×25的棋盘上放着三颗石a、b、c(如图所示)，两人轮流将石子向右移人一次只可以移动其中一颗石子1至5后无格可走者为输家，若甲先行，乙

解由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∣二、解题思路：

遇到集合问题，首先要弄请：集合里的元素是什么。

集合新名词新概念多。如集合、元素、有限集、无限集、列举法、描述法、子集、真子集、空集、非空集合、全集、补集、交集、并集等。新关系新符号多，如属于、不属于、包含、包含于、真包含、真包含于、相等、不相等、相交、相

A、I、＝、≠……)并、互补(∈、、、、N、N※、Z、Q、R、∩、∪、C

s

等，这些新概念新关系，多而抽象。在这千头万绪中，应该抓住“元素”这个关键，因为集合是由元素确定的，“子、全、补、交、并、空”等集合也都是通过元素来定义的。集合中元素的特征即“确定性”，“互异性”、“无序性”也就是元素的性质。集合的分类(有限集与无限集)与表示方法(列举法与描述法)也是通过元素来刻画的。元素是集合的基本内核，研究集合，首先就要确定集合里的元素是什么。

三、例题分析：

例1 求不超过20的正整数中是2的倍数或3的倍数的数共有多少个。

分析：设A={20以内2的倍数}，B={20以内3的倍数}，显然，要求计算2或3的倍数个数，即求∣A∪B∣。

解1：A={2，4，6，…20}，共有10个元素，即|A|=10

B={3，6，9，…18}，共有6个元素，即|B|=6

A∩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 类办法，在第一类办法中有1m 种

不同的方法，在第二类办法中有2m 种不同的方法，……，在第n 类办法中有n

m 种不同的方法那么完成这件事共有 12n N m m m =+++ 种不同的方法

2.分步计数原理：做一件事情，完成它需要分成n 个步骤，做第一步有1m 种不

同的方法，做第二步有2m 种不同的方法，……，做第n 步有n m 种不同的方法，

那么完成这件事有12n N m m m =??? 种不同的方法

3．排列的概念：从n 个不同元素中，任取m （m n ≤）个元素（这里的被取元素

各不相同）按照一定的顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列

4．排列数的定义：从n 个不同元素中，任取m （m n ≤）个元素的所有排列的个

数叫做从n 个元素中取出m 元素的排列数，用符号m n A 表示

5．排列数公式：(1)(2)(1)m n A n n n n m =---+ （,,m n N m n *∈≤） 6阶乘：!n 表示正整数1到n 的连乘积，叫做n 的阶乘规定0!1=．

7．排列数的另一个计算公式：m n A =!

(n n m -

8组合的概念：一般地，从n 个不同元素中取出m ()m n ≤个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合9．组合数的概念：从n 个不同元素中取出m

()m n ≤个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数．用符号m n C 表示．

10．组合数公式：(1)(2)(1)!m m n n

m m A n n n n m C A m ---+==

或)!(!!m n m n C m n -=,,(n m N m n ≤∈*且 11组合数的性质1：m n n m n C C -=．规定：1

0=n C ；

2：m n C 1+＝m n C +1-m n C

12．圆排列

（1）由},,,,{321n a a a a A =的n 个元素中，每次取出r 个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）．

（2）圆排列有三个特点：（i ）无头无尾；（ii ）按照同一方向转换后仍是

同一排列；（iii ）两个圆排列只有在元素不同或者元素虽然相同，但元素之间

的顺序不同，才是不同的圆排列．

（3）定理：在},,,,{321n a a a a A =的n 个元素中，每次取出r 个不同的元素进行圆排列，圆排列数为r

P r n ． 13．可重排列

允许元素重复出现的排列，叫做有重复的排列．

在m 个不同的元素中，每次取出n 个元素，元素可以重复出现，按照一定的

顺序那么第一、第二、…、第n 位是的选取元素的方法都是m 种，所以从m 个不

同的元素中，每次取出n 个元素的可重复的排列数为n m ．

14．不尽相异元素的全排列

如果n 个元素中，有1p 个元素相同，又有2p 个元素相同，…，又有s p 个元

素相同（n p p p s ≤+++ 21），这n 个元素全部取的排列叫做不尽相异的n 个元素的全排列，它的排列数是!

!!!21s p p p n ??? 15．可重组合

（1）从n 个元素，每次取出p 个元素，允许所取的元素重复出现p ,,2,1 次的

组合叫从n 个元素取出p 个有重复的组合．

（2）定理：从n 个元素每次取出p 个元素有重复的组合数为：r p n p n C H )1(-+=

二、解题思路：

排列组合题的求解策略

（1）排除：对有限条件的问题，先从总体考虑，再把不符合条件的所有情况排

除，这是解决排列组合题的常用策略．

（2）分类与分步

有些问题的处理可分成若干类，用加法原理，要注意每两类的交集为空集，

所有各类的并集是全集；有些问题的处理分成几个步骤，把各个步骤的方法数相

乘，即得总的方法数，这是乘法原理．

（3）对称思想：两类情形出现的机会均等，可用总数取半得每种情形的方法数．

（4）插空：某些元素不能相邻或某些元素在特殊位置时可采用插空法．即先安

排好没有限制条件的元素，然后将有限制条件的元素按要求插入到排好的元素之

间．

（5）捆绑：把相邻的若干特殊元素“捆绑”为一个“大元素”，然后与其它“普

通元素”全排列，然后再“松绑”，将这些特殊元素在这些位置上全排列．

（6）隔板模型：对于将不可辨的球装入可辨的盒子中，求装的方法数，常用隔

板模型．如将12个完全相同的球排成一列，在它们之间形成的11个缝隙中任意

插入3块隔板，把球分成4堆，分别装入4个不同的盒子中的方法数应为311C ，

这也就是方程12=+++d c b a 的正整数解的个数．

解排列组合问题，首先要弄清一件事是“分类”还是“分步”完成，对于元

素之间的关系，还要考虑“是有序”的还是“无序的”，也就是会正确使用分类

计数原理和分步计数原理、排列定义和组合定义，其次，对一些复杂的带有附加

条件的问题，需掌握以下几种常用的解题方法：

三、讲解范例：

一、相临问题——整体捆绑法

例1．7名学生站成一排，甲、乙必须站在一起有多少不同排法？

解：两个元素排在一起的问题可用“捆绑”法解决，先将甲乙二人看作一个元

素与其他五人进行排列，并考虑甲乙二人的顺序，所以共有 种。

捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需

要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素

内部也可以作排列.一般地: 个人站成一排,其中某 个人相邻,可用“捆绑”

法解决，共有 种排法。

练习：5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法? 分析 此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素,

并且要求她们要相邻,因此可以将她们看成是一个元素来解决问题.

解 因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全

排列,有 66P 种排法,其中女生内部也有33P 种排法,根据乘法原理,共有

3366P P 种不同的排法.

二、不相临问题——选空插入法

例2． 7名学生站成一排，甲乙互不相邻有多少不同排法？

解：甲、乙二人不相邻的排法一般应用“插空”法，所以甲、乙二人不相邻的

排法总数应为： 种 .

插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先

排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档

之中即可.若 个人站成一排，其中 个人不相邻，可用“插空”法解决，共有

种排法。

练习： 学校组织老师学生一起看电影，同一排电影票12张。8个学生，4个老

师，要求老师在学生中间，且老师互不相邻，共有多少种不同的坐法？

分析 此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊

元素,在解决时就要特殊对待.所涉及问题是排列问题.

解 先排学生共有88P 种排法,然后把老师插入学生之间的空档，共有7个空档可

插,选其中的4个空档,共有 4

7P 种选法.根据乘法原理,共有的不同坐法为

4788P P 种.

三、复杂问题——总体排除法或排异法

有些问题直接法考虑比较难比较复杂，或分类不清或多种时，而它的反面往往比

较简捷，可考虑用“排除法”，先求出它的反面,再从整体中排除.解决几何问题

必须注意几何图形本身对其构成元素的限制。

例3.正六边形的中心和顶点共7个点，以其中3个点为顶点的三角形共有

个.

解：从7个点中取3个点的取法有 种，但其中正六边形的对角线所含的中

心和顶点三点共线不能组成三角形，有3条，所以满足条件的三角形共有 －

3＝32个.

练习： 我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一

人在内的抽法有多少种?

分析 此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容

易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,

不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程.

解 43人中任抽5人的方法有 543C 种,正副班长,团支部书记都不在内的抽法有

540C 种,所以正副班长,团支部书记至少有1人在内的抽法有 540543C C 种.

四、特殊元素——优先考虑法

对于含有限定条件的排列组合应用题，可以考虑优先安排特殊位置，然后

再考虑其他位置的安排。

例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.不相临：共有A 62

种；2.相临：共有A 22A 61种。故不同插法的种数为：A 62 +A 22A 61=42 ，故选A 。

六、混合问题——先选后排法

对于排列组合的混合应用题，可采取先选取元素，后进行排列的策略．

例7． 12名同学分别到三个不同的路口进行车流量的调查，若每个路口4

人，则不同的分配方案共有（ ）

A ． 种

B ． 种

C ． 种

D ． 种

解：本试题属于均分组问题。则12名同学均分成3组共有种方法,分

配到三个不同的路口的不同的分配方案共有：种，故选A。

例8．从黄瓜、白菜、油菜、扁豆4种蔬菜品种中选出3种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有（）

A．24种 B．18种 C．12种 D．6种解:先选后排,分步实施. 由题意，不同的选法有: C

3

2种,不同的排法有:

A 31·A

2

2,故不同的种植方法共有A

3

1·C

3

2·A

2

2=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份,显然有711

C种不同的放法,所以名额分配方案有711

C种.

总之，排列、组合应用题的解题思路可总结为：排组分清，加乘明确；有序排列，无序组合；分类为加，分步为乘。

具体说，解排列组合的应用题，通常有以下途径：

（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有四门得了相同的分数；