《2017海事局事业单位容斥问题小结-更新》由会员分享，可在线阅读，更多相关《2017海事局事业单位容斥问题小结-更新（7页珍藏版）》请在金锄头文库上搜索。
1、原题：原题：一个班有 100 名学生，班里共有 3 个兴趣小组，每人至少参加了一个兴趣小组，没有参加 兴趣小组 A 的有 50 名学生，没有参加兴趣小组 B 的有 60 名学生，没有参加兴趣小组 C 的 有 70 名学生。问至少有多少学生参加了两个或者 3 个兴趣小组？ 注意：从“有 100 名学生，没有参加兴趣小组 A 的有 50 名学生”中，我们可以看出，参 加兴趣小组 A 的有 100-50=50 名学生；从“没有参加兴趣小组 B 的有 60 名学生”知道参加 兴趣小组 B 的有 100-60=40 名学生，从“没有参加兴趣小组 C 的有 70 名学生”知道参加兴 趣小组 C 的有 10
2、0-70=30 名学生。设只参加兴趣小组 A 的人数为，只参加兴趣小组 B 的人数是，只参加兴趣小组 CANBN的人数是，只参加兴趣小组 A 和 B 的人数是，只参加兴趣小组 A 和 C 的人数是CNABN，只参加兴趣小组 B 和 C 的人数是，只参加兴趣小组 A、B 和 C 的人数是。ACNBCNABCN方法方法 1：ANBNCNABNACNBCNABCN根据题意，可以列写方程如下：1001502603704ABCABACBCABCBCBCACACABABNNNNNNNeqNNNeqNNNeqNNNeq 要求的是的最小值ABACBCABCNNNN1001502603704ABCABACBCA
3、BCBCBCACACABABNNNNNNNeqNNNeqNNNeqNNNeq Eq2+eq3+Eq4 得到： 21805ABCABACBCNNNNNNeq根据 eq5 得到：18062ABACBC ABCNNNNNNeq把 eq6 带入 eq1 得到： 220ABACBCABCNNNN要求的最小值，根据约束，ABACBCABCNNNN220ABACBCABCNNNN显然当时，最小，值为 10.010ABACBCABCNNNNABACBCABCNNNN我们再把010ABACBCABCNNNN代入原始方程，看看原始方程是否有可行解，1001502603704ABCABACBCABCBCBCACAC
4、ABABNNNNNNNeqNNNeqNNNeqNNNeq 如果有，则最小值就是 10.ABACBCABCNNNN00 1010ABACBCABACBCABCABCNNNNNNNN所以把带入原始方程，发现010ABACBCABCNNNN 101001 502 603 70440 30 20ABCBCACABABCNNNeq NNeq NNeq NNeqN N N 即最终的解为40 30 200 0 0 10ABCABBCCAABCN N NN N N N 即存在可行解，所以最小值就是 10.ABACBCABCNNNN方法方法 2：根据题意，参加兴趣小组：根据题意，参加兴趣小组 A 的人数（包含参
5、加的人数（包含参加AB、AC 和和 ABC）有）有 100-50=50 人；参加兴趣小组人；参加兴趣小组 B 的人的人数（包含参加数（包含参加 AB、BC 和和 ABC）有）有 100-60=40 人；参加兴人；参加兴趣小组趣小组 C 的人数（包含参加的人数（包含参加 AC、BC 和和 ABC）有）有 100-70=30 人。设参加兴趣小组人。设参加兴趣小组 AB 的人数（包含参加的人数（包含参加 ABC）为为 x，参加兴趣小组，参加兴趣小组 AC 的人数（包含参加的人数（包含参加 ABC）是）是 y，参，参加兴趣小组加兴趣小组 BC 的人数（包含参加的人数（包含参加 ABC）是）是 z，参加
6、兴趣小，参加兴趣小组组 ABC 的人数是的人数是 t。根据容斥原理：。根据容斥原理：100504030xyzt所以：20xyzt 题目要求的是的最小值，即的最小值。xtytztt2xyzt因为，所以20xyzt 220xyztxyzttt 显然，只要在满足题意的情况下，使得 t 最大，就最小。2xyzt如何求 t 的最大值呢？题目约束条件只有，根据题意，所以20xyzt ,xt yt zt结合，所以，所以，所以 t 的最大值是2xyztt 20xyzt 202t10t 10，等号成立的条件是，经分析该条件可以成立，此时xyzt，即原题目的最小值为 10.22010xyztxyzttt 容易原理
7、：容易原理： N ABCN AN BN CN ABN ACN BCN ABCUUIIIII如何绘制下图，本图使用如何绘制下图，本图使用 visio 软件绘制：软件绘制：ANBNCNABNACNBCNABCN第一步：绘制如下所示三个圆形第一步：绘制如下所示三个圆形:第二步：选中这三个圆形，点击第二步：选中这三个圆形，点击“开发工具开发工具”中的中的“拆分拆分”第三步：选中每一个部分，分别填充即可。第三步：选中每一个部分，分别填充即可。第四步第四步:如果想把如果想把 1 和和 3 合并怎么办？选中合并怎么办？选中 1 和和 3，点击开，点击开发工具下的发工具下的“联合联合”23得到如下图所示效果：
