容斥問題大作戰(zhàn)

阿貝爾博士的數(shù)學(xué)小課堂開講啦！

本期主講內(nèi)容是容斥問題，主講嘉賓們已經(jīng)摩拳擦掌、躍躍欲試了，他們分別是：成語小王子；詩詞女俠客；引經(jīng)據(jù)典怪。

阿貝爾博士人稱小浣熊，就倆字：干脆。話不多說，先了解一下容斥原理的基本思想：

在先不考慮重疊的情況下，把包含于某一內(nèi)容中的所有對象的數(shù)目計算出來，然后再把計數(shù)時重復(fù)計算的數(shù)目排斥出去，使得計算的結(jié)果既無重復(fù)也無遺漏。

這個原理是不是有點復(fù)雜呢？沒關(guān)系，看例子就懂啦！下面，容斥原理中最常見的兩個問題：

二元容斥

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

三元容斥

如果被計數(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ù)。

哇，字也太多了吧！都讀暈了！如此復(fù)雜的容斥原理，我們該如何理解？

阿貝爾博士有方法——畫圖唄！

既屬于A又屬于B，我們用符號“∩”表示；屬于A或B，我們用符號“∪”表示，這樣就有了下面的圖——

怎么樣？轉(zhuǎn)換完圖形后，是不是既清晰又養(yǎng)眼？簡直是拯救“一見長題就暈癥”于水火之中啊！這就是大名鼎鼎的“韋恩圖”啦！

敲黑板：韋恩圖——用于顯示元素集合重疊區(qū)域的圖示。

看懂韋恩圖，容斥問題也就迎刃而解了。

一次期末考試，某班有15人數(shù)學(xué)得滿分，有12人語文得滿分，并且有4人語、數(shù)都是滿分，那么這個班至少有一門得滿分的同學(xué)有多少人？

早就迫不及待了，就讓我先來拋磚引玉、舉一反三、循循善誘、海納百川……

這是道簡單的二元容斥問題，包含數(shù)學(xué)和語文都得滿分以及至少有一門得滿分的學(xué)生。我們可以根據(jù)已知直接畫出韋恩圖。

A類是數(shù)學(xué)得滿分的人，有15人；B類是語文得滿分的人，有12人。既是A類又是B類（A∩B）的就是數(shù)學(xué)、語文都得滿分的人，有4人。

根據(jù)二元容斥公式：至少有一門得滿分的人A∪B=A+B-A∩B=15+12-4=23人。

孔子云：“三人行，必有我?guī)熝伞！鼻懊娴募一锾嚎疲莩鈫栴}的花樣還多著呢！嗯，就讓為師來“誨人不倦”吧。

某校六（1）班學(xué)生，每人在暑假里都參加體育訓(xùn)練隊，其中參加足球隊的有25人，參加排球隊的有22人，參加游泳隊的有34人，足球、排球都參加的有12人，足球、游泳都參加的有18人，排球、游泳都參加的有14人，三項都參加的有17人。那么這個班至少有一項參加的同學(xué)有多少人？

三元容斥看起來復(fù)雜，但只要畫出韋恩圖，難題立馬變簡單。

A類（參加足球隊）：25；

B類（參加排球隊）：22；

C類（參加游泳隊）：34。

A∩B=12；A∩C=18；

B∩C=14；A∩B∩C=17。

再帶入三元容斥公式，至少有一項參加的人A∪B

∪C=A+B+C-A∩B-A∩C-B∩C+A∩B∩C=25+22

+34-12-18-14+17=54人。

“巾幗不讓須眉”，前面的怪物同學(xué)別看了本《論語》就覺得天下無敵啦，要知道“山外青山樓外樓”！

某學(xué)校六年級共有學(xué)生200人，學(xué)號分別是：1，2，……100。學(xué)校在該年級做了一個用手機、平板電腦、筆記本電腦上網(wǎng)人數(shù)的調(diào)查，結(jié)果出現(xiàn)了一個非常有趣的現(xiàn)象：學(xué)號是2的倍數(shù)的學(xué)生用手機上網(wǎng)，學(xué)號是4的倍數(shù)的學(xué)生用平板電腦上網(wǎng)，學(xué)號是5的倍數(shù)的學(xué)生用筆記本電腦上網(wǎng)。問：這個學(xué)校的六年級學(xué)生中，有多少個學(xué)生不用這三種設(shè)備上網(wǎng)呢？

這個三元容斥問題要復(fù)雜不少，直接畫韋恩圖可有些摸不到頭腦，我們要先計算出至少用這三種設(shè)備中的一種上網(wǎng)的人數(shù)，再用總數(shù)減去這些人數(shù)，就是不用這三種設(shè)備上網(wǎng)的人數(shù)。

A（學(xué)號為2的倍數(shù)）（用手機上網(wǎng)）：200÷2=100（人）；

B（學(xué)號為4的倍數(shù)）（用平板電腦上網(wǎng)）：200÷4=50（人）；

C（學(xué)號是5的倍數(shù)）（用筆記本電腦上網(wǎng)）：200÷5=40（人）；

A∩B（學(xué)號為2×4=8的倍數(shù)）：200÷8=25（人）；

A∩C（學(xué)號為2×5=10的倍數(shù)）：200÷10=20（人）；

B∩C（學(xué)號為4×5=20的倍數(shù)）：200÷20=10（人）；

A∩B∩C（學(xué)號為2×4×5=40的倍數(shù)）：200÷40=5（人）。

所以，根據(jù)三元容斥公式，至少用這三種設(shè)備中的一種上網(wǎng)的人A∪B∪C=A+B+C-A∩B-A∩C-B∩C+A∩B∩C=100+50+40-25-20-10+5=140（人）。

那么，不用這三種設(shè)備上網(wǎng)的人為：200-140=60（人）。

算與不算，題就在那里

某班全體學(xué)生進行短跑、游泳、籃球三個項目的測試，有4名學(xué)生在這三個項目上都沒有達到優(yōu)秀，其余每人至少有一個項目達到了優(yōu)秀。這部分學(xué)生達到優(yōu)秀的項目、人數(shù)如下表：

這個班的學(xué)生人數(shù)是多少？