容斥定理50经典例题-容斥原理例题

这是最直接的应用，通常通过画文氏图辅助理解，并直接套用容斥公式。

例题1（两集合基础）：某班有50名学生，其中28人喜欢数学，30人喜欢语文，12人两科都喜欢。问两科都不喜欢的有几人？

解析：设喜欢数学为集合M，喜欢语文为集合C。则 |M| = 28， |C| = 30， |M∩C| = 12。根据两集合容斥原理，至少喜欢一科的人数为：|M∪C| = 28 + 30 - 12 = 46。
也是因为这些，两科都不喜欢的人数为总人数减去至少喜欢一科的人数：50 - 46 = 4人。

例题2（三集合标准型）：某公司员工中，参加外语培训的有62人，参加计算机培训的有54人，参加财务培训的有34人；其中既参加外语又参加计算机的有21人，既参加外语又参加财务的有15人，既参加计算机又参加财务的有10人；三项培训都参加的有8人。问至少参加一项培训的员工有多少人？

解析：直接应用三集合标准型容斥公式：|A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|。代入数据：62 + 54 + 34 - 21 - 15 - 10 + 8 = 112人。故至少参加一项的有112人。

实际问题中，条件给出的常常不是标准的三两交集，而是“只满足两个条件”或“至少满足两个条件”等，需要灵活转化。

例题3（给出“只满足两种”）：对120名学生的学习兴趣进行调查，发现喜欢数学、物理、化学的学生分别有80、68、60人；其中同时喜欢数学和物理的有40人，同时喜欢数学和化学的有30人，同时喜欢物理和化学的有28人；三门都喜欢的只有6人。问仅喜欢一门课程的学生有多少人？

解析：此题的关键在于区分“同时喜欢两门”（包含喜欢三门）和“仅喜欢两门”。设喜欢数学、物理、化学的集合分别为M、P、C。 已知：|M|=80， |P|=68， |C|=60， |M∩P|=40， |M∩C|=30， |P∩C|=28， |M∩P∩C|=6。 我们需要求的是仅喜欢一门的人数，即：|仅M| + |仅P| + |仅C|。 我们可以通过文氏图各区域计算：

• 仅喜欢数学和物理（不喜欢化学）：|M∩P| - |M∩P∩C| = 40 - 6 = 34
• 仅喜欢数学和化学：30 - 6 = 24
• 仅喜欢物理和化学：28 - 6 = 22
• 只喜欢数学：|M| - (34+24+6) = 80 - 64 = 16
• 只喜欢物理：68 - (34+22+6) = 68 - 62 = 6
• 只喜欢化学：60 - (24+22+6) = 60 - 52 = 8

也是因为这些，仅喜欢一门的人数为：16 + 6 + 8 = 30人。

例题4（“至少满足两个”）：承接上题数据，求至少喜欢两门课程的学生人数。

解析：“至少喜欢两门”包括“恰好喜欢两门”和“喜欢三门”。

• 恰好喜欢两门：34 + 24 + 22 = 80人
• 喜欢三门：6人

所以至少喜欢两门的有：80 + 6 = 86人。也可用公式：至少喜欢两门 = 总喜欢数 - 仅喜欢一门 = (80+68+60) - 30 = 208 - 30 = 178？这里计算有误。实际上，我们之前算出的“仅喜欢一门”是30人，但总人数是120。更稳妥的方法是：至少喜欢两门的人数 = (|M∩P| + |M∩C| + |P∩C|) - 2|M∩P∩C| + |M∩P∩C| = (40+30+28) - 26 + 6 = 98 - 12 + 6 = 92？这也不对。正确理解：“至少喜欢两门”的区域在文氏图中是两两相交的部分加上中间三交的部分，但两两相交的部分（如M∩P）包含了中间的三交部分。所以，|至少喜欢两门| = (|M∩P| + |M∩C| + |P∩C|) - 2|M∩P∩C|。因为三个两两交集加起来，中间的三交部分被加了三次，而我们需要它只被算一次，所以要减去2次。即：40+30+28 - 26 = 98 - 12 = 86人。与分区域计算结果一致。

容斥原理在求解“在1~n中能被若干个数整除的整数个数”问题上大放异彩。

例题5：求1到1000之间（包含1和1000）能被2、3或5整除的整数个数。

解析：设A：能被2整除的数的集合；B：能被3整除；C：能被5整除。求|A∪B∪C|。

• |A| = floor(1000/2) = 500
• |B| = floor(1000/3) = 333
• |C| = floor(1000/5) = 200
• |A∩B| = 能被6整除的数， floor(1000/6) = 166
• |A∩C| = 能被10整除的数， floor(1000/10) = 100
• |B∩C| = 能被15整除的数， floor(1000/15) = 66
• |A∩B∩C| = 能被30整除的数， floor(1000/30) = 33

代入公式：|A∪B∪C| = 500+333+200 - 166-100-66 + 33 = 1033 - 332 + 33 = 734。 所以，能被2、3或5整除的数有734个。

例题6：求1到100之间与100互质的正整数个数（即欧拉函数φ(100)的值）。

解析：100 = 2^2 5^2。与100互质即不能被2也不能被5整除。设A为能被2整除的集合，B为能被5整除的集合。则与100互质的数即为总数减去能被2或5整除的数。

• 总数：100
• |A| = floor(100/2) = 50
• |B| = floor(100/5) = 20
• |A∩B| = 能被10整除的数， floor(100/10) = 10

故能被2或5整除的数有：50 + 20 - 10 = 60个。 所以，与100互质的数有：100 - 60 = 40个。即φ(100)=40。

当排列组合问题带有“不能”、“至少”等限制条件时，容斥原理是化“反面”为“正面”的有效策略。

例题7（错位排列）：编号1、2、3、4的四封信，装入编号1、2、3、4的四个信封，要求每封信与信封编号不同，问有多少种装法？

解析：这是经典的错位排列问题D4。设总全排列为4! = 24。设Ai为第i封信装对了信封（i=1,2,3,4）。 所求 = 总排列数 - |A1∪A2∪A3∪A4|。

• |Ai| = 3! = 6 （固定一封信对，其余三封随便排）
• |Ai∩Aj| = 2! = 2 （固定两封信对，其余两封随便排）
• |Ai∩Aj∩Ak| = 1! = 1
• |A1∩A2∩A3∩A4| = 0! = 1

根据容斥原理：|A1∪A2∪A3∪A4| = C(4,1)6 - C(4,2)2 + C(4,3)1 - C(4,4)1 = 24 - 12 + 4 - 1 = 15。 所以错位排列数 D4 = 24 - 15 = 9种。

例题8（受限位置排列）：5个人站成一排，其中甲不站排头，乙不站排尾，共有多少种不同的排法？

解析：设总排列数5! = 120。设A：甲站排头；B：乙站排尾。 所求 = 总数 - |A∪B| = 总数 - (|A|+|B|-|A∩B|)。

• |A|：甲固定排头，其余4人全排列，4! = 24。
• |B|：乙固定排尾，其余4人全排列，4! = 24。
• |A∩B|：甲排头且乙排尾，中间3人全排列，3! = 6。

所以 |A∪B| = 24 + 24 - 6 = 42。 所求排法 = 120 - 42 = 78种。

容斥原理可用于计算满足多个几何条件的点、区域数量。

例题9：在边长为10的正方形内，任意投入100个点。求证：存在一个半径为1的圆，至少能盖住其中的3个点。

解析：此题虽非直接计算，但解题思路蕴含容斥思想。将正方形划分为9x9=81个边长为10/9≈1.11的小方格。每个小方格的外接圆直径约为1.57，半径小于1。但更精巧的划分是考虑点的“势力范围”。用反证法，假设任意一个半径为1的圆至多盖住2个点。以每个投点为圆心，1为半径作圆。如果任意两点的距离都大于2，则这些圆不重叠。但100个半径为1的不重叠圆总面积至少为100π ≈ 314，而它们都必须落在边长为12（原正方形向外扩展1）的大正方形内，其面积为144，矛盾。实际上，这里用到了面积上的“包含”关系，是容斥思想在度量上的体现。更严格的证明需要用到更精细的打包论或直接应用狄利克雷原理（抽屉原理），但其“总量超过容器则必有重叠”的逻辑与容斥原理的精神一脉相承。

在计算若干事件至少发生其一的概率时，概率形式的容斥原理与集合形式完全对应。

例题10：甲、乙、丙三人独立破译一份密码，已知各自能破译的概率分别为1/2, 1/3, 1/4。求密码被破译的概率。

解析：设事件A、B、C分别表示甲、乙、丙破译密码。则所求P(A∪B∪C)。 根据概率容斥公式： P(A∪B∪C) = P(A)+P(B)+P(C) - P(AB) - P(AC) - P(BC) + P(ABC)。 由于独立，P(AB)=P(A)P(B)=1/6， P(AC)=1/8， P(BC)=1/12， P(ABC)=1/24。 代入得：P(A∪B∪C) = 1/2 + 1/3 + 1/4 - 1/6 - 1/8 - 1/12 + 1/24。 通分计算：= (12+8+6-4-3-2+1)/24 = 18/24 = 3/4。 故密码被破译的概率为3/4。

这类题目往往需要先进行巧妙建模，将文字描述转化为集合或条件语言。

例题11：某次调查了100名游客，其中75人带了相机，68人带了雨伞，85人带了水，其中三样都带了的有40人。带了相机和雨伞但没带水的有10人，带了雨伞和水但没带相机的有8人，带了相机和水但没带雨伞的有5人。问三样都没带的有几人？

解析：设带相机、雨伞、水的集合分别为C、U、W。已知：|C|=75， |U|=68， |W|=85， |C∩U∩W|=40。 并且给出了“只带两种”的数量：

• 只带C和U：|C∩U| - |C∩U∩W| = 10 => |C∩U| = 10+40=50
• 只带U和W：|U∩W| - |C∩U∩W| = 8 => |U∩W| = 8+40=48
• 只带C和W：|C∩W| - |C∩U∩W| = 5 => |C∩W| = 5+40=45

现在我们可以求至少带一样的人数 |C∪U∪W|。代入三集合公式： |C∪U∪W| = 75+68+85 - (50+48+45) + 40 = 228 - 143 + 40 = 125。 这个结果125超过了总人数100，显然矛盾。说明题目数据设置有误。在合理的数据下，我们可以用此思路：先利用“只带两种”的数据求出两两交集的实际大小，再代入容斥公式求至少带一样的人数，最后用总人数减去，得到三样都没带的人数。此例题旨在展示解题流程。

例题12（方格路径计数）：从一个4x4网格的左下角到右上角，只能向右或向上走。问不经过对角线上方那个特定禁止点（如(1,3)）的路径有多少条？

解析：总路径数：从(0,0)到(4,4)需要走8步，其中4步向右，4步向上，所以总数为C(8,4)=70。 设A为经过禁止点(1,3)的路径集合。求|A|可以分两步：先从(0,0)到(1,3)，再从(1,3)到(4,4)。

• (0,0)到(1,3)：需要走1+3=4步，其中1步右，3步上，路径数C(4,1)=4。
• (1,3)到(4,4)：需要走3+1=4步，其中3步右，1步上，路径数C(4,1)=4。

所以 |A| = 4 4 = 16。 也是因为这些，不经过禁止点的路径数为：70 - 16 = 54条。这是一个简单的“总数-违反条件数”的容斥思想应用。对于多个禁止点，则需要使用更一般的容斥原理。