7. 容斥原理（PIE） · Mastering AMC 8

7.10%

容斥的思路

在本节中，你将能够 明白把两个有重叠的组相加时，为什么有些东西会被数两次，以及怎样修正。

老师问：“谁家养猫？”12 只手举了起来。“谁家养狗？”9 只手举了起来。那么一共有 21 个养宠物的孩子吗？如果有些孩子举了两次手，就不是！

有时候，最简单的数法是先多数一些，再把多出来的修正掉。既养猫又养狗的孩子被数了两次，所以要把他们减掉一次。

注意：问题总是出在重叠的部分。重复计数表会准确地告诉你，哪个区域被数了太多次。

动手探索先玩，再学公式

试一试： 先按 + |猫|，再按 + |狗|。哪个区域的颜色变深了？它被数了几次？
试一试： 现在按 − |猫 ∩ 狗|。每个区域都恰好数了一次吗？总数是多少？
试一试： 打开“数字转文字”。把每一行大声读出来。中间那块是哪些孩子？
试一试： 把 |猫 ∩ 狗| 改成 0。重复计数表有什么变化？为什么？

认识概念

定义 7.1.1 · 重复计数

重复计数（多数再减）是指先数得比需要的多，再有条理地减去不该算进去的部分。

定义 7.1.2 · 容斥原理

容斥原理（PIE）是一种计数方法：它利用重复计数，求出至少满足几个性质之一的元素个数，同时保证满足不止一个性质的元素不会被数两次。

自己做

习题 7.5.3

200 名学生中，有 100 人选修几何，70 人选修代数，30 人两门都选修。有多少名学生两门都没有选修？

过关检测（第 7.1 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

7.20%

两个事件的容斥原理

在本节中，你将能够 用 |A ∪ B| = |A| + |B| − |A ∩ B| 数出属于 A 或 B 的东西。

1 到 100 中，有多少个数能平均分成每组 2 个，或者平均分成每组 7 个？50 加 14 等于 64。等一下：14、28 和 42 在两张名单上都出现了！

并集 $A \cup B$ 是属于 $A$ 或属于 $B$ 的所有东西。交集 $A \cap B$ 是同时属于两者的所有东西。把 $|A|$ 和 $|B|$ 相加，交集被数了两次，所以要减掉一次。

当“好”的情况很多、“坏”的情况很少时，就用容斥原理数出坏的情况，再从总数中减去。

动手探索先玩，再学公式

试一试： 一项一项地把和搭起来。加完前两项后，有多少个数被数了两次？
试一试： 打开“显示公式”。哪一项修正了重叠部分？
试一试： 让 |×7| 等于 |×2 ∩ ×7|。这时每个 7 的倍数都是偶数。维恩图会变成什么样？
试一试： 打开“数字转文字”。1 到 100 中，既不是 2 的倍数也不是 7 的倍数的数有多少个？

认识概念

定义 7.2.1 · 并集符号

$|A \cup B|$ 表示 $A$ 和 $B$ 的并集中元素的个数（也就是属于集合 $A$ 或集合 $B$ 的所有元素，重复的只算一次）。

定义 7.2.2 · 交集符号

$|A \cap B|$ 表示 $A$ 和 $B$ 的交集中元素的个数（也就是只算那些同时属于两个集合的元素）。

定理 7.2.3 · 两个集合的容斥原理

对于两个集合，元素个数分别为 $|A_1|$ 和 $|A_2|$ ，有

|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|.

简单地说，就是把两类“东西”的可能数加起来，再减去重复的部分。

注 7.2.4

当不满足要求的情况比满足要求的情况少得多时，把补集计数和容斥原理结合起来用，往往很有帮助。

看例题先预测，再揭晓

例 7.1

求 1 到 100（含 1 和 100）中能被 2 或 7 整除的数的个数。

1
1 到 100 中，有多少个数能被 2 整除？

先预测一下：
你的预测

例 7.2

Omega Learn

集合 $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ 有多少个子集，满足其中至多有 4 个偶数，并且至多有 2 个元素是 3 的倍数？

1
怎样把容斥原理用到这道题上？

例 7.3

Omega Learn

Mark 和 George 在玩猜数游戏。George 从 1 到 25 中随机选出 2 个数。Mark 问 George：这 2 个数中是否恰好有 1 个能被 7 整除？George 如实回答：是的。接着 Mark 猜 1 个 7 的倍数和 1 个不是 7 的倍数的数。Mark 至少猜对 1 个数的概率是多少？

1
1 到 25 中有多少个 7 的倍数？有多少个数不是 7 的倍数？

先预测一下：
你的预测

在 YouTube 上打开

例 7.4

Omega Learn

把单词 LOLLIPOP 中的字母重新排列，要求每个 L 都必须紧挨着一个 O，一共有多少种不同的排法？

1
LOLLIPOP 有 3 个 L，却只有 2 个 O。每个 O 只有 2 边。其中一个 O 必须怎么样？

在 YouTube 上打开

自己做

习题 7.5.1

小于或等于 100 的正数中，有多少个是 2 的倍数或 3 的倍数？

习题 7.5.2

小于或等于 100 的正数中，有多少个既不是 2 的倍数，也不是 3 的倍数？

习题 7.5.5

一个镇上有 351 个成年人，每个成年人都拥有汽车或摩托车，或者两样都有。如果有 331 个成年人拥有汽车，45 个成年人拥有摩托车，那么拥有汽车的人中，有多少人没有摩托车？

习题 7.5.7

小于或等于 200 的正数中，有多少个是 2 的倍数且是 3 的倍数，但不是 5 的倍数？

竞赛角真实竞赛题

习题 7.5.4

AMC 8

如维恩图所示，集合 $A$ 和 $B$ 的元素个数相同。它们的并集有 2007 个元素，交集有 1001 个元素。求 $A$ 中元素的个数。

习题 7.5.6

AMC 8

在 Euler 中学，198 名学生在一次校内公投中对两个议题进行了投票，结果如下：149 人赞成第一个议题，119 人赞成第二个议题。如果恰好有 29 名学生两个议题都投了反对票，那么有多少名学生两个议题都投了赞成票？

过关检测（第 7.2 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

7.30%

三个事件的容斥原理

在本节中，你将能够 数出属于 A、B 或 C 的东西：加上单个集合，减去每两个的交集，再把三个的交集加回来。

你们学校有美术、乐队和象棋三个社团。有些学生参加了两个社团，还有几个学生三个都参加了！怎样才能让每个学生恰好被数一次呢？

有三个圆时，中间就变复杂了。参加全部三个社团的学生先被加了 3 次，又被减了 3 次。这样就剩 0 次了，所以要把他们加回来一次。

注意：符号是轮流出现的：单个集合用加号，两两交集用减号，三个的交集用加号。

动手探索先玩，再学公式

逐项求和 →

重复计数表：每个区域被数了几次

只在美术中还没数
只在乐队中还没数
只在象棋中还没数
只在美术和乐队中还没数
只在美术和象棋中还没数
只在乐队和象棋中还没数
三个圈都在还没数

|美术|10

|乐队|9

|象棋|8

|美术 ∩ 乐队|4

|美术 ∩ 象棋|3

|乐队 ∩ 象棋|3

|美术 ∩ 乐队 ∩ 象棋|1

全部25

试一试： 把三个单项加起来。看看重复计数表的正中间。同时参加三个社团的学生被数了几次？
试一试： 减去三个两两交集。正中间发生了什么？现在它还被数到了吗？
试一试： 按 + 加上最后一项。现在每个区域都恰好数了一次吗？
试一试： 打开“数字转文字”。有多少个学生一个社团都没参加？用方框的总数验证一下。

认识概念

定理 7.3.1 · 三个集合的容斥原理

对于三个集合，元素个数分别为 $|A_1|, |A_2|, |A_3|$ ，有

\begin{aligned}|A_1 \cup A_2 \cup A_3| = {} & |A_1| + |A_2| + |A_3| \\ & - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| \\ & + |A_1 \cap A_2 \cap A_3|.\end{aligned}

在这个公式里，我们先把三类“东西”的可能数加起来，再减去每两个集合之间重复的部分（共 3 对），最后把三个集合共有的部分加回来。

看例题先预测，再揭晓

例 7.5

小于或等于 193 的数中，有多少个是 2、3 或 5 的倍数？

1
不超过 193 的数中，有多少个能被 2 整除？被 3 整除呢？被 5 整除呢？

先预测一下：
你的预测: 被 2 整除你的预测: 被 3 整除你的预测: 被 5 整除

例 7.6

AMC 8

把 5 个不同的奖项发给 3 名学生，每名学生至少得到 1 个奖项。一共有多少种不同的发奖方法？

1
先暂时忘掉这条规则。每个奖项都可以发给 3 名学生中的任何一名。一共有多少种方法？

先预测一下：
你的预测

在 YouTube 上打开

竞赛角真实竞赛题

习题 7.5.8

AMC 8

Sanders 太太有三个孙辈，他们经常给她打电话。一个每 3 天打一次，一个每 4 天打一次，一个每 5 天打一次。2016 年 12 月 31 日，三个人都给她打了电话。在接下来的一年里，有多少天她没有接到任何一个孙辈的电话？

习题 7.5.9

AMC 10

Alice 不肯挨着 Bob 坐，也不肯挨着 Carla 坐。Derek 不肯挨着 Eric 坐。在这些条件下，他们五个人坐在一排 5 把椅子上，一共有多少种坐法？

习题 7.5.11（补充题）

AMC 10

有 20 名学生参加一个课后项目，项目开设瑜伽、桥牌和绘画三门课。每名学生至少要上这三门课中的一门，但也可以上两门或三门都上。上瑜伽的有 10 人，上桥牌的有 13 人，上绘画的有 9 人。至少上两门课的学生有 9 人。三门课都上的学生有多少人？

习题 7.5.13（补充题）

AMC 12

如果一个数是合数，但不能被 2、3 或 5 整除，就称它为“像质数的数”。最小的三个像质数的数是 49、77 和 91。小于 1000 的质数有 168 个。小于 1000 的像质数的数有多少个？

过关检测（第 7.3 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

7.40%

任意多个事件的容斥原理（选学）

在本节中，你将能够 看出任意多个集合的容斥原理背后的规律（选学）。

如果有 4 个互相重叠的组呢？10 个呢？这样的维恩图可没法好好画出来。但规律会一直延续下去！

先加上每一个单个集合，再减去每两个的交集，加上每三个的交集，减去每四个的交集，依此类推。符号轮流变化，直到最后一项：所有集合的交集。

互动工具里的星星代表一个元素。不管它属于多少个集合，经过这几轮之后，它最终总是恰好被数一次。

动手探索先玩，再学公式

集合数4

★ 所在集合数3

4 个集合的容斥轮次
轮次	符号	项数	含 ★ 的项	★ 计数
单个集合	+	4	·	·
每两个的交集	−	6	·	·
每三个的交集	+	4	·	·
每四个的交集	−	1	·	·

★ 被数了 0 次

4 个集合一共有 15 项。改变“★ 所在集合数”：最后一轮之后，计数总是恰好为 1。

试一试： 一轮一轮地按那个大按钮。每一轮之后，星星被数了几次？
试一试： 把“★ 所在集合数”依次改成 1、2、3 和 4。最后的计数总是 1 吗？
试一试： 把集合数设为 5。最后一轮是加还是减？为什么？

认识概念

概念 7.4.1 · 容斥原理的推广

数超过 3 个事件时，道理也一样。对于任意 $n$ 个事件，要求出至少有一个事件发生的方法总数：

求出每个事件单独发生的方法数。
对每一对（2 个）事件，减去两个都发生的方法数。
对每一组 3 个事件，加回三个都发生的方法数。
对每一组 4 个事件，减去四个都发生的方法数……
对全部 $n$ 个事件，当 $n$ 是奇数时加上、当 $n$ 是偶数时减去它们全都发生的方法数。

加和减轮流进行，直到算到全部 $n$ 个事件都发生的情况。因为加减是交替的，所以全部 $n$ 个事件都发生的方法数是加还是减，取决于 $n$ 是不是奇数。

定理 7.4.2 · 容斥原理的一般公式

更正式地说，如果 $(A_i)_{1 \le i \le n}$ 都是有限集合，那么：

\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i=1}^{n} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} |A_1 \cap \cdots \cap A_n|.

竞赛角真实竞赛题

习题 7.5.12（补充题）

BmMT

Berkeley 数学系要给学生分配导师。如果有 7 名不同的学生和 3 位不同的导师，每名学生恰好有一位导师，那么要使每位导师至少带一名学生，一共有多少种分配方法？

习题 7.5.14（补充题）

MATHCOUNTS

集合 $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$ 有多少个不同的子集，与集合 $\{2, 4, 6, 8, 10, 12\}$ 、 $\{3, 6, 9, 12\}$ 和 $\{2, 3, 5, 7, 11\}$ 中的每一个都至少有一个公共元素？

过关检测（第 7.4 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

7.5

练习题

在本节中，你将能够 在竞赛题中综合运用两个集合和三个集合的容斥原理。

来挑战一道 AIME 难题吧！找出两个事件，分别求出它们发生的概率，再减去重叠部分。每道题都有三个提示，卡住了就看看。

想在一页上看到本章的所有题目吗？打开习题集。

竞赛角真实竞赛题

习题 7.5.10

AIME

很多州的标准车牌格式是：先是三个字母，后面跟着三个数字。假设每种“三个字母加三个数字”的排列出现的可能性都相同，那么这样一块车牌至少含有一个回文（即三个字母的排列或三个数字的排列从左往右读和从右往左读都一样）的概率是 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m+n$ 。