第7講容斥原理

《第7講容斥原理》由會員分享，可在線閱讀，更多相關(guān)《第7講容斥原理（4頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、容斥原理 解答一個含有數(shù)量關(guān)系的問題時，只要 把題目由日常語言譯成代數(shù)語言就行了。 ——牛頓 在應(yīng)用加法原理時，關(guān)鍵在于把所要計數(shù)的對象分為若干個不重不漏的類，使得每類便于計數(shù)。但是具體問題往往是復(fù)雜的，常常難以分為不重不漏的類，而要把條理分清楚就得用加法原理的推廣——容斥原理，先請看一個例子。 某校同學(xué)參加全市的數(shù)學(xué)和語文學(xué)科競賽，結(jié)果有23人獲得數(shù)學(xué)競賽優(yōu)勝獎，有15人獲得語文競賽優(yōu)勝獎，其中有8人兩門學(xué)科競賽都獲得優(yōu)勝獎，問：這個學(xué)校有多少名學(xué)生獲獎？ 分析與解顯然，不能把23和15相加所得

2、的和38當(dāng)作獲獎的學(xué)生總數(shù)，因為有8人既得了數(shù)學(xué)優(yōu)勝獎，又得了語文優(yōu)勝獎，所以在這38人中他們被重復(fù)計算了一次，應(yīng)該扣除掉．所以獲獎學(xué)生數(shù)應(yīng)該是23+15-8=30（人）。 像上例這樣有重復(fù)包含的情況，在解題時應(yīng)該考慮排除由于重復(fù)或相互包含而引起多加或多減的數(shù)學(xué)問題，就是包含與排除問題，也稱作重疊問題。 如圖7 -1所示，兩張面積分別為A、B的圓紙片 蓋在桌面上，它們重疊的部分的面積為C，則它們所 蓋住的桌面的面積S，等于它們的面積之和(A+B) 減去它們相互包含（重疊的部分）的面積C。即 S=A+B-C。 這就是解決包含與排除問題的重要原理—

3、—容斥原理，即當(dāng)兩個計數(shù)部分有重復(fù)時，為了不重復(fù)地計數(shù)，應(yīng)從它們的和中減去重復(fù)部分。 例1 如圖7-2，在邊長為1的正方形中，以其一 對相對頂點為圓心，邊長為半徑作圓弧，則圖中陰影部 分的面積是 解:正方形可以看作是兩個的圓重疊而成的，而 圖7—2重疊部分是陰影部分，所以有 正方形面積=圓面積+圓面積-陰影部分面積， 從而有 l=π + π一陰影部分面積． 故陰影部分面積=-1 例2在l到100的全部自然數(shù)中，不是3的倍數(shù)也不是5的倍數(shù)的數(shù)有多少個？ 分析與解從1到100的全部自然數(shù)中除去3或5的倍數(shù)，剩下的數(shù)既不

4、是3的倍數(shù)，也不是5的倍數(shù)。 不難知道3的倍數(shù)有3，6，9，…，99共33個；5的倍數(shù)有5，10，15，…，100共20個，其中既是3的倍數(shù)同時又是5的倍數(shù)即15的倍數(shù)有15，30，45．…，90共6個。根據(jù)容斥原理，3或5的倍數(shù)有33+20-6 =47（個）． 從而，既不是3的倍數(shù)也不是5的倍數(shù)的數(shù)共有100-47=53（個） 答：既不是3的倍數(shù)也不是5的倍數(shù)的數(shù)共有53個。 下面的圖7-3能幫助我們看清這一點。 在運用容斥原理時，要善于使用形象的圖示幫助理解題意，搞清數(shù)量關(guān)系和邏輯關(guān)系。 之所以產(chǎn)生計數(shù)上的重復(fù)，原因在于我們采用了兩種分類標(biāo)準(zhǔn)：第一分

5、類標(biāo)準(zhǔn)是3的倍數(shù)與不是3的倍數(shù)，第二種分類標(biāo)準(zhǔn)是5的倍數(shù)與不是5的倍數(shù)，由于標(biāo)準(zhǔn)不同，結(jié)果產(chǎn)生交叉重疊。 一般地，對n個事物，如果我們采用兩種不同的分類標(biāo)準(zhǔn)：按性質(zhì)A分類與按性質(zhì)B分類，那么具有性質(zhì)A或性質(zhì)B的事物個數(shù)等于具有性質(zhì)A的事物的個數(shù)nA與具有性質(zhì)B的事物個數(shù)nB的和減去同時具有性質(zhì)A和性質(zhì)B的事物個數(shù)nAB。從圖7-4中可以比較清楚地看到這一點。 如果采用三種不同的分類標(biāo)準(zhǔn)：A性質(zhì)、B性質(zhì)和C性質(zhì)，要計算具有性質(zhì)A或B或C的事物個數(shù)將會更復(fù)雜些。這是因為簡單地把具有性質(zhì)A的事物nA個，具有性質(zhì)B的事物nB個，具有性質(zhì)C的事物nc個相加得和nA+nB+nC，那么同時具

6、有性質(zhì)A及B，B及C或C及A的事物都分別被加了兩次，用nAB,nBC，nCA分別表示它們的個數(shù)，于是作差 （nA+nB+nC）-（nAB+nBC+nCA） 但這樣一來，假設(shè)存在同時具有性質(zhì)A，B，C的事物nABC個。那么它們在nA，nB，nC，中被加3次，卻又在nAB,nBC，nCA刪中被減3次，其實沒有被計算在內(nèi)，因此還應(yīng)補上，正確結(jié)果是 （nA+nB+nC）一（nAB+nBC+nCA）+nABC 這是較前面所述更為復(fù)雜些的容斥原理 的一種形式，如圖7-5所示。 例3在l到100的自然數(shù)中，既不是3的倍數(shù)也不是4與5的倍數(shù)的數(shù)有多少個？

7、 分析與解只需求出是3或4，5的倍數(shù)有多少個，問題也隨之解決了。 3的倍數(shù)有3，6，9，…，99，共33個； 4的倍數(shù)有4，8，12，…，100，共25個； 5的倍數(shù)有5，10，15，…，l00，共20個。 我們還應(yīng)注意下面這些數(shù)： 3與4的公倍數(shù)有l(wèi)2，24，…，96，共8個； 3與5的公倍數(shù)有l(wèi)5，30，…，90，共6個； 4與5的公倍數(shù)有20，40，…，100，共5個； 3，4，5的公倍數(shù)有1個：60。 根據(jù)容斥原理，l到100的自然數(shù)中，3，4或5的倍數(shù)共有 (33+25+20)-(8+6+5)+1=60（個）． 因此，1到

8、100的自然數(shù)中既非3，4也不是5的倍數(shù)有100 - 60= 40（個）。 答：既不是3，4也不是5的倍數(shù)的數(shù)有40個。 例4 如圖7-6，A，B，C分別是面積為12，28，I6平方厘米的三張不同形狀的紙片，它們疊放在一起蓋住的總面積為38平方厘米。若A與B，B與C，C與A的公共部分的面積分別為8，7，6平方厘米，求A，B，C三張紙片的公共部分的面積（圖中陰影部分）。 解設(shè)所求三張紙片的公共部分的面積為x，則由容斥原理有 38 =12+28+16-8-7-6+x 解得x=3（平方厘米）。 答：A，B，C三張紙片的公共部分的面積為

9、3平方厘米。 例5 在一根長的木棍上有三種刻度線，第一種刻度線將木棍分成十等份，第二種將木棍分成十二等份，第三種將木棍分成十五等份。如果沿每條刻度線將木棍鋸斷，木棍總共被鋸成多少段？ 分析與解很顯然，要計算木棍被鋸成多少段，只需計算出木棍上共有多少條不同的刻度線，因10，12，15的最小公倍數(shù)為60，可以假設(shè)木棍長為60個單位，則在木棍上的刻度線可以分為下述三類： 6×l，6×2，…，6×9（第一種刻度線）； 5×l，5×2，…，5×11（第二種刻度線）； 4×l，4×2，…，4×14（第三種刻度線）． 由于6和5的最小公倍數(shù)是30

10、，因此，第一種與第二種刻度線重疊的有 -1 =2-1=1（條）； 6和4的最小公倍數(shù)是12，因此，第一種與第三種刻度線重疊的有 -1=5-1=4（條）； 5和4的最小公倍數(shù)是20，因此，第二種與第三種刻度線重疊的有-l =3-1=2（條）； 最后，三種刻度線均重疊的有 -1=1-1=0（條）； 根據(jù)容斥原理，木棍上共有刻度線 (9+11+14)-(1+4+2)+0=27（條）。 答：如果沿每條刻度線將木棍鋸斷，木棍總共被鋸成28段。 在上面的一些例子中，我們講了一組事物以兩個性質(zhì)或三個性質(zhì)為標(biāo)準(zhǔn)分類時的計數(shù)問題，它們可以用相應(yīng)的容斥原

11、理來解決，喜歡動腦筋、找規(guī)律的同學(xué)會問，如果有四個性質(zhì)或更多的性質(zhì)時，容斥原理是怎樣的呢？經(jīng)過觀察和思考，你可以發(fā)現(xiàn)這樣一條規(guī)律： 具有所有性質(zhì)中至少一個性質(zhì)的事物總數(shù)為 W=n2+n3-n4+…+nk 其中，n1表示具有一個性質(zhì)的事物總數(shù)（包括重復(fù)），n2表示具有兩個性質(zhì)的事物總數(shù)（包括重復(fù)）；n3表示具有三個性質(zhì)的事物總數(shù)（包括重復(fù)）；n4表示具有四個性質(zhì)的事物總數(shù)（包括重復(fù)）；…nk表示具有所有性質(zhì)的事物總數(shù)（包括重復(fù)）。注意，在算式中，加與減交替，這就是一般形式的容斥原理。 習(xí)題： 1．一個班有45個學(xué)生，統(tǒng)計借課外書的情況是：全班學(xué)生都借有語文或數(shù)學(xué)課

12、外書，借語文課外書的有39人，借數(shù)學(xué)課外書的有32人．語文、數(shù)學(xué)兩種課外書都借的有 人。 2．有長8厘米、寬6厘米的長方形與邊長為5厘米的正方形，如圖7-7，放在桌面上（陰影是圖形的重疊部分），那么這兩個圖形蓋住桌面的面積是____平方厘米。 3．在1-100的自然數(shù)中，是5的倍數(shù)或是7的倍數(shù)的數(shù)有 個。 4．某區(qū)100個外語教師懂英語或俄語，其中懂英語的75人，既懂英語又懂俄語的20人，那么懂俄語的教師為 人。

13、 5．六一班有學(xué)生46人，其中會騎自行車的17人，會游泳的14人，既會騎車又會游泳的4人，兩樣都不會的有 人。 6． 在l至10000中不能被5或7整除的數(shù)共有 個。 7．某班共有30名男生，其中20人參加足球隊，12人參加籃球隊，10人參加排球隊，已知沒有一個人同時參加3個隊，且每人至少參加一個隊，有6人既參加足球隊又參加籃球隊，有2人既參加籃球隊又參加排球隊，那么既參加足球隊又參加排球隊的有 人。

14、 8.在100名學(xué)生中，音樂愛好者有56人，體育愛好者有75人，那么，既愛好音樂又愛好體育的人最少有 人，最多有 人。 9．某進(jìn)修班有50人，開甲、乙、丙三門進(jìn)修課，選修甲這門課的有38人，選修乙這門課的有35人，選修丙這門課的有31人，兼選甲、乙兩門課的有29人，兼選甲、丙兩門課的有28人，兼選乙、丙兩門課的有26人，甲、乙、丙三科均選的有24人．問：三科均未選的人數(shù)是多少？ 10．如圖7-8所示，，A，B，C分別代表面積為8，9. 11的三張不同形狀的紙片，它們重疊放在一起蓋住的面積是18，且A與B，B與C，C與A公共部分的面積分別是5，3，4，求，A，B，C三個圖形公共部分（陰影部分）的面積。 4