小升初专题系列之容斥与染色

小学教育网

容斥与染色
染色问题基本解法：
三面涂色和顶点有关 8个顶点。
两面染色和棱长有关。即新棱长（棱长-2）×12
一面染色和表面积有关。同样用新棱长计算表面积公式（棱长-2）×（棱长-2）×6
0面染色和体积有关。用新棱长计算体积公式（棱长-2）×（棱长-2）×（棱长-2）
长方体的解法和立方体同理，即计算各种公式前长、宽、高都要先减2再利用公式计算。
容斥原理
　　在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
　 （1）如果被计数的事物有A、B两类，那么，A类或B类元素个数= A类元素个数+B类元素个数（既是A类又是B类的元素个数）。
（2）如果被计数的事物有A、B、C三类，那么，A类或B类或C类元素个数= A类元素个数+B类元素个数+C类元素个数-既是A类又是B类的元素个数（既是A类又是C类的元素个数-既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数）。
课后检测：
点击查看答案



1. 某班有40人，其中有33人会中国象棋，28人会国际象棋，36人会围棋。这个班至少有多少人三种都会？
解：∵总人数为40，其中有33人会中国象棋，28人会国际象棋，36人会围棋。∴有8人不会中国象棋，12人不会国际象棋，4人不会为其，共计24人。
∴有40-24=16人什么都会。

2. 某班有46人，其中有40人会骑车，38人会打乒乓球，35人会打羽毛球，27人会游泳，则这个班至少有多少入以上四项运动都会?
解：一共46人，有40人会骑车，所以就有46-40=6（人）不会骑车，同理有46-38=8（人）不会打乒乓球，有46-35=11（人）不会打羽毛球，有46-27=19（人）不会游泳。假设这个班每个人最多只有一项不会，此时四项都会的人最少。即有6+8+11+19=44（人）不是4项运动都会。而4项都会的人是：46-44=2（人）
答：这个班至少有2人以上四项运动都会。

3.一批商品，每件是1×2×8的长方体，现在有一批现成的木箱，尺寸是12×12×12，试问，能不能用这样的商品将木箱装满？
解：不能，因为12除不尽8。

4. 有六个点a.b.c.d.e.f，其中没有任何三点在同一条直线上，在每两点间用线段连接，如果这些线段中每一段或者涂上白色或者涂上黑色，证明至少有一个三角形的三边是同样颜色
证明：从a看，它连接的五条线至少有三条同X（可能黑，可能白）色，这三条连着的三个点（假设是b.c.d，其实是等价的）中共有三条连线，若有一条为X色（假设端点b.c），则有同色三角a.b.c，若都不是X色，则有同色三角b.c.d。

5. 8×8的国际象棋棋盘能不能被剪成7个2×2的正方形和9个4×1的长方形？如果可以，请给出一种剪法；如果不行，请说明理由。
解：如下图，对8×8的棋盘染色，则每一个4×1的长方形能盖住2白2黑小方格，每一个2×2的正方形能盖住1白3黑或3白1黑小方格。推知7个正方形盖住的黑格总数是一个奇数，但图中的黑格数为32，是一个偶数，故这种剪法是不存在的。

thread-215467-1-130.html (120.22 KB, 下载次数: 10)

2016-8-15 10:52 上传

点击文件名下载附件
thread-215467-1-130.html