基础篇

第1章 辨识问题比解决问题更重要

对义务教育阶段的孩子而言，掌握解题技巧虽然重要，但认识到为什么有些做法是错的往往更重要。看似相同的问题，可能会有九九八十一变。准确地辨识问题需要孩子拥有一双火眼金睛。下面我以经典的分球问题、图论问题、大黄蜂找蜂房、容斥原理问题为例，来谈谈数学解题中如何辨识问题。

分球问题

先从分鱼食问题开始，本质上，这是排列组合中常见的分球入盒问题。

例1 鱼缸里有4条不同的鱼。你将10颗不同的食物颗粒放入鱼缸里。假如允许给鱼分0颗食物颗粒，那么把10颗食物颗粒分给4条鱼，一共有多少种不同的分法？

例2 鱼缸里有4条不同的鱼。你将10颗相同的食物颗粒放入鱼缸里。假如允许给鱼分0颗食物颗粒，那么把10颗食物颗粒分给4条鱼，一共有多少种不同的分法？

这两道题都是经典的排列组合问题，抽象出来就是分球入盒问题，相当于把10个球放入4个盒子里。这两道题中的食物颗粒对应球，鱼则对应盒子。

你看出上面两个问题有什么差别了吗？其他条件都一样，只是把食物从“不同”变成了“相同”。但就是这么微小的文字改动，问题的难度和解题的方法便完全不同了。

分球问题有很多变种，一不小心，我们就会搞混。这些变种主要是由以下3个约束条件产生的：

组合上面的约束条件，一共可以产生2×2×2=8种不同的分球入盒变种问题，如表1所示。

表1

如果搞不清楚这些看似微小的条件变化而引起问题本质上的差别，只是机械地记忆问题解法，那就很容易张冠李戴。

下面我就对表1中一些比较简单的情况（第1种、第5种、第6种、第8种组合方式）进行分析。

第1种组合方式的分析

上面第1题对应的是表1中第1种组合方式，这也是这类题目中最简单的。

为了更清楚地讲解这一问题，我曾拿出一些棒棒糖，并以此举了一个更简单的例子。

问题：把3根不同颜色的棒棒糖分给2个学生，有多少种分法？

一个孩子说有14种。他是这么思考的：

第一个学生分3根，第二个学生分0根；第一个学生分0根，第二个学生分3根。有2种分法。

剩下的12种情况里，每个学生至少分得1根棒棒糖。

他把3根不同颜色的棒棒糖做排列，得到6种排序方法。然后假设第一个学生分1根，第二个学生分2根，每次把排列的第一根棒棒糖分给第一个学生，剩下的2根分给第二个学生。

比如，排列为A，B，C，那么第一个学生分A，第二个学生分B，C；如果排列为C，B，A，那么第一个学生分C，第二个学生分B，A……所以有6种分法。如果第一个学生分2根，第二个学生分1根，则同上又有6种方法。因此，他认为总共有2+6×2=14种。

很快有孩子意识到这个思路有问题。问题在于：排列A，B，C或A，C，B，最后都是第一个学生分A，第二个学生分B，C，属于同一种分法，因此不是一一对应的，而是有两种排列方式对应一种分法。

经过这么一点拨，这个孩子就知道，其实只有2+3+3=8种分法。

但如果试图把这种方法拓展到更大的数，就存在困难。

在前面的分鱼食问题中，我们的任务是把10颗不同的食物颗粒分给4条不同的鱼，可以分成10步来完成这个任务，每一步分1颗食物。由于允许鱼可以分0颗食物，每一颗食物颗粒都可以分给4条鱼中的任何一条，有4种不同的分法。因此，根据乘法原理，共有种方法。

第6种组合方式的原始解法分析

上面第2题对应了表1中第5种组合方式。在解决这个问题之前，我们可以先来解决表1中第6种组合方式的问题，即10颗相同的食物颗粒分给4条不同的鱼，并且每条鱼至少要吃到1颗食物颗粒。

同样，以棒棒糖举例，小朋友就很容易理解。现在分到你手中的是哪根棒棒糖并不重要，因为都是一样的棒棒糖，重要的是你分到了几根。

此时可以用枚举法，尽管方法有点儿笨。比如：10=1+1+1+7，但谁分7根，有4种分法。拆分和对应的不同分法如表2所示。

表2

所以，总共有4+12+12+6+12+24+4+4+6=84种不同的分法。

第8种组合方式的分析

这里要先分析表1中第8种组合方式，因为上述过程实际上也解决了第8种组合方式的问题，即10个相同的球放入4个相同的盒子，且不允许盒子为空，等价于把10拆分成4个大于0的整数之和，并且整数是无序的，也就是说，1，3，3，3和3，3，3，1是相同的拆分方式。

我们不妨假设可以将10写成4个数a，b，c，d之和，且0＜a≤b≤c≤d。

因此，总共有9种分法，分别如下：

10=1+1+1+7

10=1+1+2+6

10=1+1+3+5

10=1+1+4+4

10=1+2+2+5

10=1+2+3+4

10=1+3+3+3

10=2+2+2+4

10=2+2+3+3

第6种组合方式的插板法分析

再回到上面的问题，当数量变大时，枚举法就不再适用了，因为可扩展性太差。那么，有没有其他的办法呢？

把10个球排列如下：

我们假设第1个盒子放最左边的几个球，第2个盒子放随后的球，最后一个盒子放最右边的球。

例如，我们按照上面的方法将10个球分一下，用竖线隔开，那么就相当于第1个、第2个、第3个、第4个盒子分别放了2、3、4、1个球。

这个问题就转换成，在10个球的9个间隔中选择3个间隔插入分隔符（可以用板来分隔），从而把10个球分成有序的4组。

把3块不同的板放到9个间隔中的3个位置，一共有9×8×7种放法。在这里，板是相同的，3块板有6种不同的排列，只要3块板放的位置相同，对应的就是同一种划分。

比如，如下图所示，3块板A、B、C分别放在3，5，8三个空位上，可以有ABC，ACB，BAC，BCA，CAB，CBA这6种不同的排列。但当3块板相同时，对应的是同一种划分。

因此，一共有9×8×7÷6=84种不同的放法。

可以看到，这个结果和上面的枚举结果是一样的。这就是经典的插板法。

第5种组合方式的分析

再回到表1的第5种组合方式，也就是如果允许盒子为空怎么办？

孩子们首先想到的是能插分隔符的地方从9个增加为11个，因此，共有11×10×9÷6=165种。但很快有孩子意识到这是不对的，因为允许空盒后，可以把几个分隔符插在一个位置（如下图）。

比如，上面这种就表示第1个、第2个、第3个、第4个盒子分别放0、0、3、7个球。因此，问题就不等同于在11个位置选3个位置放分隔符了。

其实，这个问题可以转化为表1中第6种组合方式的问题来做。转化是求解未知数学问题的利器，能将未知变成已知。

在这个问题中，转化的诀窍就在于怎么去掉允许盒子为空这个约束条件。如果不允许盒子为空，那么我们可以再拿4个相同的球，在每个盒子先放1个球。这样，后面10个球还是按照原来的允许盒子为空来放，最后的结果是没有盒子为空。

比如，最后4个盒子放的球数是3，1，5，5，那么对应的10个球的放法就是2，0，4，4。反之，如果10个球的放法为2，0，4，4，那么对应的14个球的放法就是3，1，5，5。两者是一一对应的。

这里不得不多说一句，很多计数问题解决方法背后都蕴含着“一一对应”这一最朴素却最有用的思想，它将会一直贯穿整个中学时代的函数学习。

于是，10个相同的球放入4个不同的盒子，允许盒子为空，就相当于14个相同的球放进4个不同的盒子，不允许盒子为空。根据第6种组合方式的解法，共有13×12×11÷6=286种。

其他组合方式

到此，我们讲解了表1中的第1种、第5种、第6种、第8种组合方式的解法，当然，第8种如果数量大，那么还需要其他解决方法。实际上，这个问题里其他组合方式的解法很复杂，涉及递归等更高级的技巧，这是大学组合数学内容的一部分，在此就不再深入探讨了。

最关键的问题是，我们需要有一双火眼金睛，能够识别出这一问题不同的变种，从而采取合适的做法。

欧拉通路还是哈密尔顿通路

我们来看下面这个易辨识错误的问题。

在一片大海上，有许多藏有金币的小岛，这些小岛由桥连接在一起（如下图）。每通过一座小岛，就可以收获相应数量的金币（每座小岛上的金币数量已经标记）。从起点到终点，每座桥最多只能走一次。小朋友试着走一走，最后把经过的每座小岛上的金币数量加起来，算一算，最多能收获多少个金币？

不少学过一笔画的同学很快就把它与一笔画问题对应起来，并做出如下结论：由于图中存在8个奇点，原图无法一笔画，所以要去掉一些边才行。

一笔画问题在图论里对应于欧拉图，由七桥问题发展而来。欧拉通路（或欧拉回路）要经过图中所有的边一次且仅一次，但对于每个点经过多少次并没有限制。然而，在上面的这个问题中，由于金币并不在桥上，而是在岛上，显然不用经过所有的桥（或尽可能多地经过桥），因此不是一笔画问题。

在图论中，还有一个相似的问题是寻找一条经过图中每个顶点一次且仅一次的通路，这样的通路被称为哈密尔顿通路。在上面的问题中，由于金币在岛上，因此，如果存在一条从起点到终点能经过所有点一次的通路，那就能获得所有的金币。

但经过多次尝试，我们发现，这个图似乎不存在这么一条从起点经过所有点一次且仅一次后到达终点的路径。事实上，如果我们按下图的方式用0，1对所有点进行间隔标号，那起点标号为0，终点标号也为0，标号为0和1的点各有8个。由于0和1间隔标号，走过的路径一定呈现0-1-0-1-0-1……的排列，要遍历所有点（8个0，8个1）一次且仅一次，最后一个点的标号应该是1才对，因此无法遍历。所以，至少要去掉1个点才行。

我们发现，如果去掉有3个金币的岛，那么左上角的点将成为度数为1的悬挂点，因此不行。而如果去掉有4个金币的岛，则是可以的，具体的走法如下图。相应地，可以获得129个金币。

我们回过头再次仔细审视一下题目，可以发现题目中只限制每座桥走一次，但并没有限制每座岛只能走一次。因此，这个问题其实与哈密尔顿通路是两码事！

去掉了这个限制以后，我们不难找到一条从起点到终点且经过所有小岛的路径（路径并不唯一），如下图（图中的标号给出了走的次序）所示。这条路径两次经过了有9个金币的小岛。所以，这个问题的正确答案就是把所有岛上的金币数加起来，为133个金币，而不是129个。

大黄蜂找蜂房

我们再来看一个问题：

一只黄蜂想从图中左上角的蜂房移到右下角有蜂蜜的蜂房。每次移动，它只能往右侧相邻的蜂房移动一步，那么，它一共有多少种不同的方法到达有蜂蜜的蜂房呢？

当大黄蜂位于上图的某个位置时，它的下一步基本上都有两种移动方法，比如，当它位于上面一行的中间位置时，那么它可以向右和右下两个位置移动；如果位于下面一行的中间位置，那么它可以向右和右上两个位置移动。

于是，许多同学的第一反应是用乘法原理求解：2×2×2×…×2。但问题也随之而来，一共有多少个2相乘呢？我们知道，应用乘法原理有两个基本的前提条件。

第一，乘法原理要求完成任务的步数是确定的。但这只大黄蜂满足条件的移动步数是不确定的，最少6步完成，最多可以11步完成（如下图）。

第二，乘法原理的形象表示是如下所示的分支图，它要求每一层下面所有分支的分叉数一样多。

下面的分支图表示一个人有3条裤子和4件上衣，一共可以有12种不同的搭配。第一步选裤子，有3种选法；第二步选上衣，每一条裤子配上衣时都有4种选法。

但在大黄蜂找蜂房这个问题中，如果仔细观察，你会发现，其实并非每一个位置的下一步都有两种选择。比如，到达右上角的位置后，大黄蜂的下一步只有一种移动方法，即向右下。

所以，乘法原理并不适用于这个问题。

碰到这种问题，我们不妨先尝试数数距离起点最近的几个格子的移动方法，看看能有什么发现。简单试一下就得到了下面的结果。

比如要到达图片左下角的格子“A”中，只有一种走法，即从起点向右下方走。到达黄蜂所在格子右边的第一格“B”中，有两种走法，分别是从起点经过A到B和从起点直接到B。

通过简单分析可以发现，从左上角到达A，B，C，D，E的方法数分别是1，2，3，5，8种。原来这是个斐波那契数列。为什么会是这样？我们可以回过头来再思考。在这幅图中，到达某个格子有两种可能（除了图中的左下格）。比如，为了到达K，只能从I或J到达，并且经过I或J直接到达K的走法一定不同。因此，到达K的方法数=到达I的方法数+到达J的方法数。所以说，这个问题实际上是加法原理，而不是乘法原理的应用。最后，到达K的方法数为144种。

容斥原理问题

我们再来看下面这道看上去很熟悉的题：

四（3）班有40人，喜欢语文的有30人，喜欢数学的有36人，请问同时喜欢语文和数学的有多少人？

学过容斥原理的同学会不假思索地回答：30+36-40=26人。

但真的是这样吗？不妨再来看下面这个问题。

四（3）班有40人，每个人至少喜欢语文或数学中的一门，喜欢语文的有30人，喜欢数学的有36人，请问同时喜欢语文和数学的有多少人？

有人看完题目后不免疑惑：这两个问题不是一样的吗？连数字都一样啊！但再仔细看一下，好像有那么一点儿区别。在第二个问题里，每个人至少喜欢语文或数学中的一门，而在第一个问题里并没有这个约束条件，因此第一个问题里可能有人两门都不喜欢！

有了上面的分析，我们就知道，26人（30+36-40=26）应该是第二个问题的答案，而第一个问题的答案并不是一个固定值，应该是个范围。

如果每个人都至少喜欢语文或数学中的一门，那么第一个问题的解答就和第二个问题一样，为26人；但如果其中有1个人两门都不喜欢，那么至少喜欢语文或数学中一门的就只有39人，从而同时喜欢语文和数学的同学为：30+36-39=27人。

最极端的情况是所有喜欢语文的人都喜欢数学，此时有4个人两门都不喜欢，如下图所示。显然，这种情况下，两门都喜欢的就是30人，也是能达到的最大值。

因此，第一个问题的答案应该是26～30人。

如果你觉得现在已经完全掌握了，那再来看下面这个问题：

四（3）班的每个同学至少喜欢语文、数学或英语中的一门课，喜欢语文的有30人，喜欢数学的有36人，喜欢英语的有28人，同时喜欢语文和数学的有24人，同时喜欢语文和英语的有20人，同时喜欢数学和英语的有18人，三门课都喜欢的有8人，请问四（3）班一共有多少人？

有了上面的经验，不少同学都会仔细地看一下，题目里是不是说清楚了每个同学都至少喜欢语文、数学或英语中的一门课，确认无误后，就可以放心地根据容斥原理公式算出结果：

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|=30+36+28-24-20-18+8=40

但这个解答对不对呢？如果不会公式，画个韦恩图会如何？

画完上面的图后，我们会发现，只喜欢语文和只喜欢英语的没法填了。因为16+8+12=36已经超过喜欢语文的总人数30人了，同样12+8+10=30也大于喜欢英语的总人数28人了。

因此，这个问题的根本在于题目出错了！但是，如果只用容斥原理的公式求解，是察觉不了这个错误的。

那怎样才能确保题目不出错呢？我们可以先算出喜欢数学同时又喜欢语文和英语中至少一门的人数，然后出题时要确保喜欢数学的人数不小于这个数才行。对于语文和英语，也要做同样的限制。这里也就是要确保喜欢数学的人数不少于34人，喜欢语文的人数不少于36人，喜欢英语的人数不少于30人才行。