小学小学数学专题之容斥与染色

2010-05-12 11:00:35 　来源：网络资源文章作者：匿名

　　染色问题基本解法：

　　三面涂色和顶点有关 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，是一个偶数，故这种剪法是不存在的。