SaDuck

深色模式

容斥问题 ​

一、两者容斥 ​

  如果被计数的事物有 A、B 两类，那么，先把 A、B 两个集合的元素个数相加，A 和 B 中都算了一次 A∩B 部分的元素，所以要把这部分重复计算的元素减去一次。如下图所示。


I-非A且非B=A+B-A‌∩B


  1. 如果题目中有提到类似“每人参加了至少一项”的表述，说明都不满足数=0、非A且非B=0

二、三者容斥 ​


I-非A且非B且非C=A+B+C-A‌∩B-B‌∩C-A‌∩C+A‌∩B‌∩C


  三集合标准公式：总数－都不满足=A+B+C-(A∩B)-(A∩C)-(B∩C)+(A∩B∩C)
  三集合变形公式 ：总数－都不满足=A+B+C－只满足两项－2×满足三项

公式推导

  1. 根据上图：总数－都不满足=1+2+3+4+5+6+7；A=1+4+6+7；B=3+5+6+7；C=2+4+5+7。
  2. 然后A+B+C=1+2+3+++++++++
  3. 发现跟总数－都不满足相比，4、5、6多计算了一次，7多计算两次。
  4. 4代表只满足AC，5代表只满足BC，6代表只满足AB，我们把4、5、6三块统称为“只满足两项”
  5. 7是A‌∩B‌∩C，统称为“满足三项”
  6. 因此总数－都不满足=A+B+C－只满足两项－2×满足三项（变形公式）
  7. 我们在换个思路，4+7可以表示A∩C，5+7可以表示B∩C，6+7可以表示A∩B
  8. 因此我们可以这样写：A+B+C-（4+7）-（5+7）-（6+7）=1+2+3+4+5+6
  9. 发现多减了一个7，因此需要加回来，所以总数－都不满足=A+B+C-（4+7）-（5+7）-（6+7）+7
  10. 即所以总数－都不满足=A+B+C-A∩B-A∩C-B∩C+A∩B∩C（标准公式）

  如果题目中有提到类似“每人参加了至少一项”的表述，说明都不满足数=0，即 非A且非B且非C=0

  1. 解题步骤分三步走：
    1. ①画文氏图；
    2. ②弄清楚图形中每一部分所代表的含义；
    3. ③代入公式

三、容斥的极值问题 ​

方法1：多集合反向构造 ​

  1. 第一步：反向。先分别反向求出各集合的补集；例如：不喜欢音乐、舞蹈、美术的学生，分别有9、11、14人；
  2. 第二步：加和。反向的补集进行相加；例如：这9、11、14人毫无重复，则此时’不都喜欢’的最多，有9+11+14=34（人）；
  3. 第三步：做差。例如：’不都喜欢‘的最多，那么‘都喜欢的’最少，有45－34=11（人）。
  4. 这种思路的核心是“让不都喜欢的无任何重复，则不满足要求的最多”。

方法2：正向思路 ​

  1. 求最小值
    1. 两个集合A、B交集的最小值为A+B-U（U为全集）
    2. 三个集合A、B、C交集的最小值为A+B+C-2U（U为全集）
    3. 四个集合A、B、C、D交集的最小值为A+B+C+D-3U（U为全集）
  2. 求最大值
    1. N个集合交集的最大值均为较小的集合

四、随笔练习 ​

  1. 例1：(2016年河南省) 某公司组织歌舞比赛，共 68 人参赛。其中，参加舞蹈比赛的有 12 人，参加歌唱比赛的有 18 人，45 人什么比赛都没有参加。问同时参加歌舞比赛的有多少人？ （ ）
  2. A.7
  3. B.8
  4. C.9
  5. D.10
：。所以两项比赛都参加的人数为 12+18-（68-45）=7 人。故答案为A

  1. 例2：(2011年国家) 某市对 52 种建筑防水卷材产品进行质量抽检，其中有 8 种产品的低温柔度不合格，10 种产品的可溶物含量不达标，9 种产品的接缝剪切性能不合格，同时两项不合格的有 7 种，有 1 种产品这三项都不合格。则三项全部合格的建筑防水卷材产品有多少种？ （ ）
  2. A.34
  3. B.35
  4. C.36
  5. D.37
：在将低温柔度不合格、可溶物含量不达标、接缝剪切性能不合格的产品数相加时，两项同时不合格的产品数被计算了两次，；三项同时不合格的产品数被计算了三次，。设三项全合格的建筑防水卷材产品有 x 种，根据容斥原理可得，8+10+9-7-2×1+x=52，解得 x=34。故答案为A

  1. 例3：(2018年江西) 某高校做有关碎片化学习的问卷调查，问卷回收率为90%，在调查对象中有180人会利用网络课程进行学习，200人利用书本进行学习，100人利用移动设备进行碎片化学习，同时使用三种方式学习的有50人，同时使用两种学习方式的有20人，不存在三种学习都不用的人。那么这次共发放了多少份问卷？
  2. A.370
  3. B.380
  4. C.390
  5. D.400
：这是一道。注意题目中提到：不存在三种学习都不用的人。所以在的过程中，非A且非B且非C=0。代入三集合容斥问题非标准形式得到：总人数=180+200+100-20-2*50，总人数=360，总问卷=360/90%=400。答案选D。

  1. 例4：(2024广东梅州事业单位) 某单位42名职工参加健身活动，每人至少参加一种，已知参加瑜伽的有22人，参加蛙跳的有30人，参加跑步的有15人，其中5名职工三种健身活动都参加了，该单位有（ ）名职工只参加了一种健身活动？
  2. A.19
  3. B.20
  4. C.21
  5. D.22
：这是一道。根据三集合容斥问题非标准型公式：A+B+C-满足两项-满足三项×2=总数-都不，可得：22+30+15-参加两种健身活动-5x2=42-0，解得参加两种健身活动的人数 = 15。根据三集合容斥问题常识公式：满足一项+ 满足两项 + 满足三项 = 总数-都不，则只参加一种健身活动的人数=42-15-5=22人。故正确答案为D。