1、第十二讲 乘法原理进阶 在之前我们学习了“加法原理与乘法原理”一讲，即分类相加与分步相乘的 思想 如果完成一件事分为几个步骤，在每一个步骤中又有不同的方法，那么把每 步的方法数相乘就得到所有的方法数这就是乘法原理 要想把过程分成几个步骤从而应用乘法原理，必须保证各步骤之间满足下面 两个要求： 1. 每步都只是整件事情的一个部分，必须全部完成才算做完这件事； 2. 步骤之间要有先后顺序，先确定好一步，再做下一步，直到最后 那么是不是只要分步骤完成整件事情就可以直接用乘法原理呢？ 如下图，把 A、B、C 三部分用三种不同的颜色染色，要求相邻两部分不能 同色，那么一共有多少种不同的染法呢？ 其实，整
2、个染色过程是需要分为三步的，即分别给其中一块染色： 当染色顺序为 ABC 时，那么 A 有 3 种染法，B 不能和 A 一样，有 2 种 染法，同样 C 有 2 种，那么一共就有“3 22 ”种染法； （CBA 同理） 当染色顺序为 BAC 时，那么 B 有 3 种染法，A 不能和 B 一样，有 2 种 染法，同样 C 有 2 种，那么一共就有“3 22 ”种染法； （BCA 同理） 当染色顺序为 ACB 时，那么 A 有 3 种染法，第二步 C 没有限制，也有 3 种染法，但是最后的 B 就出问题了，我们没法确定它有 2 种还是 1 种染法 如果 C 和 A 同色，则 B 有 2 种染法；如
3、果 C 和 A 不同色，则 B 只有 1 种染法 此时，根据分步相乘的思想计算整个过程的染色方法“33? ”就不再适用 了 （CAB 同理） 因此，并不是只要分步完成整件事情就一定可以应用乘法原理，要想应用乘 法原理，还必须满足第三个要求： 3. 做完一步时，这一步的结果很可能会影响后面步骤的结果，但一定不能 影响后面步骤的方法数 如果这一步的不同结果会导致后面某一步的方法数发生 变化，就不能直接用乘法原理计算 简称“前不影响后 原则” 染色问题，是应用乘法原理最常见的一类题型，其实，从上面对 A、B、C 三部分的染色分析我们应该可以发现，染色的时候，要尽量避免“隔”着染，一 定不要“跳”着染
4、，而且，第一步要尽量去染“接触最多”的那一部分，这样， 才能够使得后面的染色过程尽量避开“前影响后” A B C 例题 1 如图，把 A、B、C、D、E 这五部分用 4 种不同的颜色 染色，且相邻的部分不能使用同一种颜色请问：这 幅图共有多少种不同的染色方法？ 分析分析分五步染色，先染哪一块呢？能否按照 A、B、C、D、 E 的顺序染呢？ 练习 1 如图，把 A、B、C、D 这四部分用 4 种不同的 颜色染色， 且相邻的部分不能使用同一种颜色 请问： 这幅图共有多少种不同的染色方法？ 例题 2 某市实行垃圾分类处理每个地方放置五个垃圾桶，从左向右依次标 明：电池、塑料、废纸、易拉罐、其它现在准
5、备把五个垃圾桶染成 红、绿、蓝这 3 种颜色之一 （1）要求相邻两个垃圾桶颜色不同，一共有多少种染色方法？ （2）要求相邻两个垃圾桶颜色不同且回收易拉罐的垃圾桶不能染成 红色，一共有多少种染色方法？ 分析分析如果我们先染废纸垃圾桶：当它染红色时，回收易拉罐的垃圾桶可以染 绿、蓝两种颜色；而当它染绿色（蓝色）时，回收废纸的垃圾桶只能染蓝色（绿 色） 因此先染废纸垃圾桶时，会影响易拉罐垃圾桶的染色方法数，就不能直接 用乘法原理计算了那么我们应该先给哪个垃圾桶染色呢？ 练习 2 麦兜很挑食， 只吃带有鱼丸或粗面的搭配 一天它和 3 位同学来餐厅吃东西， 一开口就要鱼丸粗面，结果老板说没有这个时候，由
6、于时间太晚，餐厅快打烊 了，只能做牛肚河粉，鱼丸油面，猪肉米线和牛肉拉面各一份，请问它们四只猪 各点一份，有几种点法？ B E C D A A B C D 在例题 2 中， 有一个垃圾桶是有特殊要求的易拉罐垃圾桶不能染成红色， 我们通过尝试可知：如果一开始先染其他的垃圾桶，那么前面垃圾桶的染色方法 就会影响到易拉罐垃圾桶的染色方法数，即不能满足“前不影响后”原则，而如 果首先染易拉罐垃圾桶，则不会出现该问题，所以一般而言，如果题目中有些对 象是有特殊要求的， 那么我们分步分步 分析计算的时候， 首先要考虑这些特殊的对象 例题 3 卡莉娅、墨莫、小高和大头 4 名同学竞选班委有班长、学习委员、
7、生活委员三个职位，每个人只能担任一个职位，并且每个职位只能由 一个人担任 （1）有多少种可能的选举结果？ （2）如果班长必须由卡莉娅来担任，有多少种可能的选举结果？ （3）如果生活委员只能在墨莫和大头之中选，有多少种可能的选举 结果？ （4）如果学习委员不能由小高担任，有多少种可能的选举结果？ 分析分析可以按照职位一一确定，第（2）问中，班长只能由卡莉娅来担任，那么 先确定哪一个职位的人选呢？其他小问呢？ 练习 3 甲、乙、丙、丁、戊 5 个人竞选班委有班长、副班长、纪律委员、卫生委 员四个职位， 每个人只能担任一个职位， 并且每个职位只能由一个人担任： 请问： （1）一共有多少种可能的选举结
8、果？（2）如果副班长只能在甲、丁和戊中选， 有多少种可能的选举结果？（3）如果卫生委员不能由乙、丙担任，有多少种可 能的选举结果？ 例题 4 甲、乙、丙、丁四个人要住进 A、B、C、D 四间房间，每个房间住一 个人其中甲不住 A 房间，丙只住 D 房间请问：这四个人住进四 个房间有多少种住法？ 分析分析本题中甲和丙有特殊要求，我们应该先考虑甲还是丙呢？ 练习 4 甲、乙、丙、丁四个人要住进 A、B、C、D 四间房间，每个房间住一个人其 中甲只住 A 或 B 房间，丙只住 A、B 或 C 房间请问：这四个人住进四个房间 有多少种住法？ 例题 5 甲、乙、丙、丁、戊五人要驾驶 A、B、C、D、E
9、这五辆不同型号的 汽车，请计算在下列情况下，分别共有多少种不同的安排方案： （1）只有甲能开汽车 A，乙不会开汽车 B； （2）会开 A 的只有甲和乙，会开 E 的只有甲、乙、丙 分析分析第 （1） 问中， 甲和丙两人有特殊要求， 我们应该先考虑哪一个人呢？ 第（2）问中，A 和 E 两车有特殊要求，我们应该先考虑哪辆车呢? 接下来我们分析一下“放相同棋子”的问题 如右图，将 2 枚相同的棋子放入 22 的方格内，每个格子 只能放 1 枚，且要求每行每列最多只能放 1 枚，那么一共会有 几种方法呢？ 其实，要把两枚相同的棋子放进格子内，只需要选出两个 格子即可，然后每个格子里放一枚棋子 一共有
10、两行，所以必定会是每行一枚，所以我们完全可以分行选格子，第一 行有两种选法，第一行选好后，第二行就只有一种选法了，所以一共有 2 1=2 种 例题 6 右图是一个阶梯形方格表，在方格中放入五枚相同的棋 子，使得每行、每列中都只有一枚棋子，这样的放法共 有多少种？ 分析分析容易看出， 每行只能有 1 枚棋子， 每列也只能由一枚棋子， 我们可以把放五枚棋子的过程分成五步：一行一行或一列一列的 放 课堂内外 四色定理 四色定理与费马大定理、 哥德巴赫猜想并称为 近代数学三大难题 四色定理的内容是：对于任何一张地图，只用 四种颜色，就可以把有相邻边界的国家染上不同 的颜色 四色问题的提出来自英国185
11、2 年，在大学 读书的格 斯里向他的老师著名数学家摩根提出了这个问题， 摩根没有能找到解决这个 问题的途径 “四色问题”提出以后，最初并没有引起广泛的重视，许多数学家低估了它 的难度就连素以谦虚著称的德国数论专家闵可夫斯基在大学上拓扑课时也说： 四色问题之所以一直没有获得解决，那仅仅是由于没有一流的数学家来解决 它说罢，他拿起粉笔，竟要当堂给学生推导出来，结果没有成功下一节课他 又去试，还是没有成功过了几个星期，仍无进展有一天，他刚跨进教室，适 逢天上雷声大作，震耳欲聋他马上对学生说：“上天在责备我自大，我也无法 解决四色问题”这样，四色问题就成了世界最著名的问题之一l00 多年中， “四色问
12、题”使数学家们深为困扰没有人能证明它，也没有人推翻它 电子计算机问世以后，由于演算速度迅速提高，加 之人机对话的出现，大大加快了四色猜想的证明进程 就在 1976 年 6 月， 哈肯与阿佩尔在美国伊利诺斯大 学 的两台不同的电子计算机上，用了 1200 个小时，作了 100 亿次判断，终于完成了四色定理的证明， 轰动了世界 作业 1. 五个座位排成一排，小高、墨莫、萱萱、阿呆、阿瓜每人选一个座位坐下，其中每个座 位只能坐一个人，且萱萱不坐在中间的位置这五个人有多少种坐法？ 2. 如图，把 A、B、C 这三部分用 4 种不同的颜色染色，且相邻的部分不能使用同一种颜 色请问，这幅图共有多少种不同的
13、染色方法？ 3. 把 A、B、C、D、E 这五部分用 4 种不同的颜色染色，且相邻的部分不能使用同一种颜 色这幅图共有多少种不同的染色方法？ 4. 甲、乙、丙、丁四个人排成一队，甲不当排头，乙不当排头也不当排尾，共有多少种不 同的排法？ 5. 在的方格中放入两枚相同的棋子，要求两枚棋子既不在同一行也不在同一列，共 有多少种放法？ 24 A B C D E A B C 第十二讲 乘法原理进阶 1. 例题 1 答案：96 详解： 分步， 分别给分步， 分别给 E、 B、 C、 A、 D 染色， 分别有染色， 分别有 4、 3、 2、 2、 2 种染法， 所以一共有种染法， 所以一共有4 3 222
14、96 种染色方法种染色方法 2. 例题 2 答案：48；32 详解： （1）从左往右依次染色，分别有）从左往右依次染色，分别有 3、2、2、2、2 种染法，共有种染法，共有3 222248 种染色种染色 方法；方法； （2）分步，先染易拉罐垃圾桶，再分别给废纸、塑料、电池、其他这四个垃圾桶染色，五个垃）分步，先染易拉罐垃圾桶，再分别给废纸、塑料、电池、其他这四个垃圾桶染色，五个垃 圾桶分别有圾桶分别有 2、2、2、2、2 种染法，所以一共有种染法，所以一共有2222232 种染色方法种染色方法 3. 例题 3 答案：24；6；12；18 详解： （1） 分别确定班长、 学委、 生活委员的人选，
15、 分别有） 分别确定班长、 学委、 生活委员的人选， 分别有 4、 3、 2 种选法， 所以共有种选法， 所以共有4 3 224 种；种； （2）分别确定班长、学委、生活委员的人选，分别有）分别确定班长、学委、生活委员的人选，分别有 1、3、2 种选法，所以共有种选法，所以共有1 3 26 种；种； （3） 分别确定生活委员、 学委、 班长的人选， 分别有） 分别确定生活委员、 学委、 班长的人选， 分别有 2、 3、 2 种选法， 所以共有种选法， 所以共有2 3 212 种；种； （4） 分别确定学委、 班长、 生活委员的人选， 分别有） 分别确定学委、 班长、 生活委员的人选， 分别有
16、3、 3、 2 种选法， 所以共有种选法， 所以共有3 3 218 种种 4. 例题 4 答案：4 详解：分步，分别安排丙、甲、乙、丁，分别有分步，分别安排丙、甲、乙、丁，分别有 1、2、2、1 种选法，所以一共有种选法，所以一共有1 2 2 14 种选法种选法 5. 例题 5 答案：18；24 详解： （1）先考虑甲，后考虑乙，再考虑其他三个人，分别有）先考虑甲，后考虑乙，再考虑其他三个人，分别有 1、3、3、2、1 种可能，共有种可能，共有 1 3 3 2 1 18 种；种； （2）先考虑）先考虑 A，后考虑，后考虑 E，再考虑其他三辆车，分别有，再考虑其他三辆车，分别有 2、2、3、2、
17、1 种可能，所以共有种可能，所以共有 2 2 3 2 124 种种 6. 例题 6 答案：16 详解：一共要选一共要选 5 个格子放棋子，一行一行选，每行个格子放棋子，一行一行选，每行 1 个，而且不能在同一列，从上往下，个，而且不能在同一列，从上往下，5 行分别有行分别有 2、2、2、2、1 种选法，所以一共有种选法，所以一共有2222 1 16 种选法种选法 7. 练习 1 答案：48 详解：分步，分别给分步，分别给 B、C、A、D 染色，分别有染色，分别有 4、3、2、2 种染法，所以一共有种染法，所以一共有 4 3 2248 种染色方法种染色方法 8. 练习 2 答案：6 详解：先让麦
18、兜点，只有鱼丸油面先让麦兜点，只有鱼丸油面 1 种可选，然后让其他种可选，然后让其他 3 位同学依次点，分别有位同学依次点，分别有 3、2、1 种种 选法，共分四步，乘法原理，所以共有选法，共分四步，乘法原理，所以共有1 3 2 16 中不同的选法 9. 练习 3 答案：120；72；72 简答： （1）5 4 3 2120 种；种； （2）先确定副班长，再依次确定其他，共有）先确定副班长，再依次确定其他，共有3 4 3 272 种；种； （3）先确定卫生委员，再依次确定其他，共有）先确定卫生委员，再依次确定其他，共有3 4 3 272 种种 10. 练习 4 答案：8 简答：分步，分别安排甲
19、、丙、乙、丁，分别有分步，分别安排甲、丙、乙、丁，分别有 2、2、2、1 种选法，所以一共有种选法，所以一共有222 18 种选法种选法 11. 作业 1 答案：96 简答：可以按照萱萱、小高、墨莫、阿呆、阿瓜的顺序安排座位，有44 3 2 196 种安 排座位的顺序不唯一 12. 作业 2 答案：24 简答：可以按照 A、B、C 的顺序染色，4 3 224 种染色顺序不唯一 13. 作业 3 答案：96 简答：可以按照 A、B、C、D、E 的顺序染色，有4 3 22296 种染色顺序不唯一 14. 作业 4 答案：8 简答：按照乙、甲、丙、丁的顺序安排，有222 18 种排法 15. 作业 5 答案：12 简答：一行一行选位置，第一行有 4 个格子可选，即 4 种选法；第二行还有 3 个格子可选，即 有 3 种选法因此有4 312 种不同的放法