第7講容斥原理

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

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

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

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

4、是3的倍數(shù)，也不是5的倍數(shù)。 不難知道3的倍數(shù)有3，6，9，…，99共33個(gè)；5的倍數(shù)有5，10，15，…，100共20個(gè)，其中既是3的倍數(shù)同時(shí)又是5的倍數(shù)即15的倍數(shù)有15，30，45．…，90共6個(gè)。根據(jù)容斥原理，3或5的倍數(shù)有33+20-6 =47（個(gè)）． 從而，既不是3的倍數(shù)也不是5的倍數(shù)的數(shù)共有100-47=53（個(gè)） 答：既不是3的倍數(shù)也不是5的倍數(shù)的數(shù)共有53個(gè)。 下面的圖7-3能幫助我們看清這一點(diǎn)。 在運(yùn)用容斥原理時(shí)，要善于使用形象的圖示幫助理解題意，搞清數(shù)量關(guān)系和邏輯關(guān)系。 之所以產(chǎn)生計(jì)數(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)生交叉重疊。 一般地，對(duì)n個(gè)事物，如果我們采用兩種不同的分類標(biāo)準(zhǔn)：按性質(zhì)A分類與按性質(zhì)B分類，那么具有性質(zhì)A或性質(zhì)B的事物個(gè)數(shù)等于具有性質(zhì)A的事物的個(gè)數(shù)nA與具有性質(zhì)B的事物個(gè)數(shù)nB的和減去同時(shí)具有性質(zhì)A和性質(zhì)B的事物個(gè)數(shù)nAB。從圖7-4中可以比較清楚地看到這一點(diǎn)。 如果采用三種不同的分類標(biāo)準(zhǔn)：A性質(zhì)、B性質(zhì)和C性質(zhì)，要計(jì)算具有性質(zhì)A或B或C的事物個(gè)數(shù)將會(huì)更復(fù)雜些。這是因?yàn)楹?jiǎn)單地把具有性質(zhì)A的事物nA個(gè)，具有性質(zhì)B的事物nB個(gè)，具有性質(zhì)C的事物nc個(gè)相加得和nA+nB+nC，那么同時(shí)具

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

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

8、100的自然數(shù)中既非3，4也不是5的倍數(shù)有100 - 60= 40（個(gè)）。 答：既不是3，4也不是5的倍數(shù)的數(shù)有40個(gè)。 例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 在一根長(zhǎng)的木棍上有三種刻度線，第一種刻度線將木棍分成十等份，第二種將木棍分成十二等份，第三種將木棍分成十五等份。如果沿每條刻度線將木棍鋸斷，木棍總共被鋸成多少段？ 分析與解很顯然，要計(jì)算木棍被鋸成多少段，只需計(jì)算出木棍上共有多少條不同的刻度線，因10，12，15的最小公倍數(shù)為60，可以假設(shè)木棍長(zhǎng)為60個(gè)單位，則在木棍上的刻度線可以分為下述三類： 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段。 在上面的一些例子中，我們講了一組事物以兩個(gè)性質(zhì)或三個(gè)性質(zhì)為標(biāo)準(zhǔn)分類時(shí)的計(jì)數(shù)問(wèn)題，它們可以用相應(yīng)的容斥原

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

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

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

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