2017海事局事业单位容斥问题小结-更新

《2017海事局事业单位容斥问题小结-更新》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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的有100-70=30名学生。设只参加兴

2、趣小组A的人数为，只参加兴趣小组B的人数是，只参加兴趣小组C的人数是，只参加兴趣小组A和B的人数是，只参加兴趣小组A和C的人数是，只参加兴趣小组B和C的人数是，只参加兴趣小组A、B和C的人数是。方法1：根据题意，可以列写方程如下：要求的是的最小值Eq2+eq3+Eq4得到：根据eq5得到：把eq6带入eq1得到：要求的最小值，根据约束，显然当时，最小，值为10.我们再把代入原始方程，看看原始方程是否有可行解，如果有，则最小值就是10.所以把带入原始方程，发现即最终的解为即存在可行解，所以最小值就是10.方法2：根据题意，参

3、加兴趣小组A的人数（包含参加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，参加兴趣小组ABC的人数是t。根据容斥原理：所以：题目要求的是的最小值，即的最小值。因为，所以显然，只要在满足题意的情况下，使得t最大，就最小。如何求t的最大值呢？题目

4、约束条件只有，根据题意，所以结合，所以，所以，所以t的最大值是10，等号成立的条件是，经分析该条件可以成立，此时，即原题目的最小值为10.容易原理：如何绘制下图，本图使用visio软件绘制：第一步：绘制如下所示三个圆形:第二步：选中这三个圆形，点击“开发工具”中的“拆分”第三步：选中每一个部分，分别填充即可。第四步:如果想把1和3合并怎么办？选中1和3，点击开发工具下的“联合”得到如下图所示效果：