 |
||
容斥与染色--专题系列
http://www.yiaoshu.com - 发布时间：2009-09-07 - 所在栏目：
奥数辅导
容斥与染色
染色问题基本解法：
三面涂色和顶点有关 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，是一个偶数，故这种剪法是不存在的。
下一篇文章： 行程问题--专题系列
上一篇文章： 给家长的几点建议：一二年级如何学好奥数？
