小學(xué)小學(xué)數(shù)學(xué)專題之容斥與染色

2010-05-12 11:00:35 　來源：網(wǎng)絡(luò)資源文章作者：匿名

　　染色問題基本解法：

　　三面涂色和頂點有關(guān) 8個頂點。

　　兩面染色和棱長有關(guān)。即新棱長(棱長-2)×12

　　一面染色和表面積有關(guān)。同樣用新棱長表面積公式(棱長-2)×(棱長-2)×6

　　0面染色和體積有關(guān)。用新棱長體積公式(棱長-2)×(棱長-2)×(棱長-2)

　　長方體的解法和立方體同理，即各種公式前長、寬、高都要先減2再利用公式。

　　容斥原理：

　　在計數(shù)時，必須注意無一重復(fù)，無一遺漏。為了使重疊部分不被重復(fù)，人們研究出一種新的計數(shù)方法，這種方法的基本思想是：先不考慮重疊的情況，把包含于某內(nèi)容中的所有對象的數(shù)目先出來，然后再把計數(shù)時重復(fù)的數(shù)目排斥出去，使得的結(jié)果既無遺漏又無重復(fù)，這種計數(shù)的方法稱為容斥原理。

　　(1)如果被計數(shù)的事物有A、B兩類，那么，A類或B類元素個數(shù)= A類元素個數(shù)+B類元素個數(shù)(既是A類又是B類的元素個數(shù))。

　　(2)如果被計數(shù)的事物有A、B、C三類，那么，A類或B類或C類元素個數(shù)= A類元素個數(shù)+B類元素個數(shù)+C類元素個數(shù)-既是A類又是B類的元素個數(shù)(既是A類又是C類的元素個數(shù)-既是B類又是C類的元素個數(shù)+既是A類又是B類而且是C類的元素個數(shù))。

　　容斥與染色問題例題：

　　1. 某班有40人，其中有33人會中國象棋，28人會國際象棋，36人會圍棋。這個班至少有多少人三種都會?

　　解：∵總?cè)藬?shù)為40，其中有33人會中國象棋，28人會國際象棋，36人會圍棋。∴有8人不會中國象棋，12人不會國際象棋，4人不會為其，共計24人。

　　∴有40-24=16人什么都會。

　　2. 某班有46人，其中有40人會騎車，38人會打乒乓球，35人會打羽毛球，27人會游泳，則這個班至少有多少入以上四項運(yùn)動都會?

　　解：一共46人，有40人會騎車，所以就有46-40=6(人)不會騎車，同理有46-38=8(人)不會打乒乓球，有46-35=11(人)不會打羽毛球，有46-27=19(人)不會游泳。假設(shè)這個班每個人較多只有一項不會，此時四項都會的人較少。即有6+8+11+19=44(人)不是4項運(yùn)動都會。而4項都會的人是：46-44=2(人)

　　答：這個班至少有2人以上四項運(yùn)動都會。

　　3.一批商品，每件是1×2×8的長方體，現(xiàn)在有一批現(xiàn)成的木箱，尺寸是12×12×12，試問，能不能用這樣的商品將木箱裝滿?

　　解：不能，因為12除不盡8。

　　4. 有六個點a.b.c.d.e.f，其中沒有任何三點在同一條直線上，在每兩點間用線段連接，如果這些線段中每一段或者涂上白色或者涂上黑色，證明至少有一個三角形的三邊是同樣顏色

　　證明：從a看，它連接的五條線至少有三條同X(可能黑，可能白)色，這三條連著的三個點(假設(shè)是b.c.d，其實是等價的)中共有三條連線，若有一條為X色(假設(shè)端點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個正方形蓋住的黑格總數(shù)是一個奇數(shù)，但圖中的黑格數(shù)為32，是一個偶數(shù)，故這種剪法是不存在的。