七年級(jí)數(shù)學(xué)競(jìng)賽系列講座(15)容斥原理一、 一、知識(shí)要點(diǎn)1、容斥原理 在計(jì)數(shù)時(shí)，常常遇到這樣的情況，作合并運(yùn)算時(shí)會(huì)把重復(fù)的部分多算，需要減去；作排除運(yùn)算時(shí)會(huì)把重復(fù)部分多減，需要加上，這就是容斥原理。它的基本形式是： 記A、B是兩個(gè)集合，屬于集合A的東西有個(gè)，屬于集合B的東西有個(gè)，既屬于集合A又屬于集合B的東西記為，有個(gè)；屬于集合A或?qū)儆诩螧的東西記為，有個(gè)，則有：=+-AÇBAB容斥原理可以用一個(gè)直觀的圖形來(lái)解釋。如圖，左圓表示集合A，右圓表示集合B，兩圓的公共部分表示，兩圓合起來(lái)的部分表示，由圖可知：=+- 容斥原理又被稱作包含排除原理或逐步淘汰原則。 二、 二、例題精講例1 在1到200的整數(shù)中，既不能被2整除，又不能被3整除的整數(shù)有多少個(gè)？分析：根據(jù)容斥原理，應(yīng)是200減去能被2整除的整數(shù)個(gè)數(shù)，減去能被3整除的整數(shù)個(gè)數(shù)，還要加上既能被2整除又能被3整除，即能被6整除的整數(shù)個(gè)數(shù)。解：在1到200的整數(shù)中，能被2整除的整數(shù)個(gè)數(shù)為：2´1，2´2，2´100，共100個(gè)； 在1到200的整數(shù)中，能被3整除的整數(shù)個(gè)數(shù)為：3´1，3´2，3´66，共66個(gè)；在1到200的整數(shù)中，既能被2整除又能被3整除，即能被6整除的整數(shù)個(gè)數(shù)為： 6´1，6´2，6´33，共33個(gè)；所以，在1到200的整數(shù)中，既不能被2整除，又不能被3整除的整數(shù)個(gè)數(shù)為：200-100-66+33=67(個(gè)) 例2 求1到100的自然數(shù)中，所有既不是2的倍數(shù)又不是3的倍數(shù)的整數(shù)之和S。解：1到100的自然數(shù)中，所有自然數(shù)的和是：1+2+3+100=50501到100的自然數(shù)中，所有2的倍數(shù)的自然數(shù)和是：2´1+2´2+2´50=2´(1+2+3+50)= 2´1275=25501到100的自然數(shù)中，所有3的倍數(shù)的自然數(shù)和是：3´1+3´2+3´33=3´(1+2+3+33)= 3´561=16831到100的自然數(shù)中，所有既是2的倍數(shù)又是3的倍數(shù)，即是6的倍數(shù)的自然數(shù)和是：6´1+6´2+6´16=6´(1+2+3+16)= 6´136=816所以，1到100的自然數(shù)中，所有既不是2的倍數(shù)又不是3的倍數(shù)的整數(shù)之和S=5050-2550-1683+816=1633 例3求不大于500而至少能被2、3、5中一個(gè)整除的自然數(shù)的個(gè)數(shù)。ABC分析：如圖，用3個(gè)圓A、B、C分別表示不大于500而能被2、3、5整除的自然數(shù)， 表示既能被2整除又能被3整除的自然數(shù) 表示既能被2整除又能被5整除的自然數(shù) 表示既能被3整除又能被5整除的自然數(shù) 表示既能被2整除又能被3整除，還能被5整除的自然數(shù)由圖可看出：屬于A、B、C之一的數(shù)的個(gè)數(shù)為：+-(+)+解：不大于500且能被2整除的自然數(shù)的個(gè)數(shù)是：250不大于500且能被3整除的自然數(shù)的個(gè)數(shù)是：166不大于500且能被5整除的自然數(shù)的個(gè)數(shù)是：100不大于500既能被2整除又能被3整除，即能被6整除的自然數(shù)的個(gè)數(shù)是：83不大于500既能被2整除又能被5整除，即能被10整除的自然數(shù)的個(gè)數(shù)是：50不大于500既能被3整除又能被5整除，即能被15整除的自然數(shù)的個(gè)數(shù)是：33不大于500既能被2整除又能被3整除，還能被5整除，即能被30整除的自然數(shù)的個(gè)數(shù)是：16由容斥原理得：不大于500而至少能被2、3、5中一個(gè)整除的自然數(shù)的個(gè)數(shù)是： 250+166+100-(83+50+33)+16=366 例4 求前200個(gè)正整數(shù)中，所有非2、非3、非5的倍數(shù)的數(shù)之和。解：前200個(gè)正整數(shù)的和是：1+2+3+200=20100前200個(gè)正整數(shù)中，所有2的倍數(shù)的正整數(shù)和是：2´1+2´2+2´100=2´(1+2+3+100)= 2´5050=10100前200個(gè)正整數(shù)中，所有3的倍數(shù)的正整數(shù)和是：3´1+3´2+3´66=3´(1+2+3+66)= 6633前200個(gè)正整數(shù)中，所有5的倍數(shù)的正整數(shù)和是：5´1+5´2+5´40=5´(1+2+3+40)= 4100前200個(gè)正整數(shù)中，所有既是2的倍數(shù)又是3的倍數(shù)，即是6的倍數(shù)的正整數(shù)和是：6´1+6´2+6´33=6´(1+2+3+33)= 3366前200個(gè)正整數(shù)中，所有既是2的倍數(shù)又是5的倍數(shù)，即是10的倍數(shù)的正整數(shù)和是：10´1+10´2+10´33=10´(1+2+3+20)= 2100前200個(gè)正整數(shù)中，所有既是3的倍數(shù)又是5的倍數(shù)，即是15的倍數(shù)的正整數(shù)和是：15´1+15´2+15´13=15´(1+2+3+13)= 1365前200個(gè)正整數(shù)中，所有既是2的倍數(shù)又是3的倍數(shù)還是5的倍數(shù)，即是30的倍數(shù)的正整數(shù)和是：30´1+30´2+30´6=30´(1+2+3+4+5+6)= 630所以，前200個(gè)正整數(shù)中，所有非2、非3、非5的倍數(shù)的數(shù)之和是S=20100-(10100+6633+4100)+(3366+2100+1365)-630=630 例5 某班的全體學(xué)生進(jìn)行了短跑、游泳、籃球三個(gè)項(xiàng)目的測(cè)試，有4名學(xué)生在這三個(gè)項(xiàng)目都沒(méi)有達(dá)到優(yōu)秀，其余每人至少有一個(gè)項(xiàng)目達(dá)到優(yōu)秀，這部分學(xué)生達(dá)到優(yōu)秀的項(xiàng)目、人數(shù)如下表：短跑游泳籃球短跑、游泳游泳、籃球籃球、短跑短跑、游泳、籃球1718156652求這個(gè)班的學(xué)生數(shù)。(第三屆華杯賽復(fù)賽試題)解：有4名學(xué)生在這三個(gè)項(xiàng)目都沒(méi)有達(dá)到優(yōu)秀，在每個(gè)單項(xiàng)上達(dá)到優(yōu)秀的人數(shù)分別是17、18、15，因而，總?cè)藬?shù)是17+18+15+4=54。但其中有人獲得兩項(xiàng)優(yōu)秀，所以上面的計(jì)數(shù)產(chǎn)生了重復(fù)，重復(fù)人數(shù)應(yīng)當(dāng)減去，即總?cè)藬?shù)變?yōu)椋?4-6-6-5=37又考慮到獲得三項(xiàng)優(yōu)秀的人，他們一開(kāi)始被重復(fù)計(jì)算了三次，但在后來(lái)又被重復(fù)減去了三次，所以最后還要將他們加進(jìn)去。即這個(gè)班學(xué)生數(shù)為：37+2=39。 例6 從1到1000000這一百萬(wàn)個(gè)自然數(shù)中，能被11整除而不能被13整除的數(shù)多還是能被13整除而不能被11整除的數(shù)多？(第20屆全俄九年級(jí)試題)解：設(shè)1到1000000這一百萬(wàn)個(gè)自然數(shù)中，能被11整除而不能被13整除的數(shù)有m個(gè)， 能被13整除而不能被11整除的數(shù)有n個(gè)，既能被11又能被13整除的數(shù)有p個(gè)。 而在1到1000000這一百萬(wàn)個(gè)自然數(shù)中，能被11整除數(shù)有90909個(gè)，m+p=90909 在1到1000000這一百萬(wàn)個(gè)自然數(shù)中，能被13整除數(shù)有76923個(gè)，n+p=76923 m+p> n+p m>n，即能被11整除而不能被13整除的數(shù)比能被13整除而不能被11整除的數(shù)多。 例7 50名學(xué)生面向老師站成一行，老師先讓大家從左到右按1，2，3，依次報(bào)數(shù)，再讓報(bào)數(shù)是4的倍數(shù)的同學(xué)向后轉(zhuǎn)，接著又讓報(bào)數(shù)是6的倍數(shù)同學(xué)向后轉(zhuǎn)，問(wèn)此時(shí)還有多少同學(xué)面向老師？(1995年華杯賽試題)分析：首先沒(méi)有轉(zhuǎn)的同學(xué)仍面向老師，即報(bào)數(shù)既不是4的倍數(shù)，也不是6的倍數(shù)的同學(xué)仍面向老師，其次，報(bào)數(shù)既是4的倍數(shù)，也是6的倍數(shù)，即是12的倍數(shù)同學(xué)連續(xù)轉(zhuǎn)了兩次，仍面向老師。解：報(bào)數(shù)是4的倍數(shù)的同學(xué)有12個(gè)，報(bào)數(shù)是6的倍數(shù)的同學(xué)有8個(gè)，報(bào)數(shù)是12的倍數(shù)的同學(xué)有4個(gè)， 所以根據(jù)容斥原理得：報(bào)數(shù)既不是4的倍數(shù)，也不是6的倍數(shù)的同學(xué)有50-12-8+4=34個(gè)。報(bào)數(shù)既是4的倍數(shù)，也是6的倍數(shù)，即是12的倍數(shù)同學(xué)有4個(gè)。所以此時(shí)還應(yīng)有34+4=38個(gè)同學(xué)面向老師。評(píng)注：若將同學(xué)數(shù)50改成n，問(wèn)此時(shí)還有多少同學(xué)面向老師？可以得出一個(gè)一般的結(jié)論： 例8 已知某校共有學(xué)生900名，其中男生528人，高中學(xué)生312人，團(tuán)員670人，高中男生192人，男團(tuán)員336人，高中團(tuán)員247人，高中男團(tuán)員175人，試問(wèn)這些數(shù)據(jù)統(tǒng)計(jì)有無(wú)錯(cuò)誤？解：用I表示全校學(xué)生，A表示該校男生，B表示該校高中學(xué)生，C表示團(tuán)員，則有： =900，=528，=312，=670， 且=192，=336，=247，=175 這樣，初中女生的非團(tuán)員數(shù)是：-+-=900-528-312-670+192+336+247-175= -10<0因人數(shù)做到負(fù)數(shù)，所以數(shù)據(jù)統(tǒng)計(jì)有錯(cuò)誤。 例9 從自然數(shù)序列：1，2，3，4，中依次劃去3的倍數(shù)和4的倍數(shù)，但其中5的倍數(shù)均保留。劃完后剩下的數(shù)依次組成一個(gè)新的序列：1，2，5，7，求該序列中第2002個(gè)數(shù)。分析：因?yàn)?，4，5的最小公倍數(shù)是60，所以可將自然數(shù)序列：1，2，3，4，以60的倍數(shù)來(lái)分段，先考慮1到60的整數(shù)，其中3的倍數(shù)有20個(gè)，4的倍數(shù)有15個(gè)，既是3的倍數(shù)又是4的倍數(shù)的數(shù)有5個(gè)，則劃去3的倍數(shù)和4的倍數(shù)還剩60-20-15+5=30個(gè)，又還要保留其中的5的倍數(shù)6個(gè)，這樣還剩36個(gè)，即1到60的整數(shù)中，劃完后剩下36個(gè)，由此推得，每60個(gè)一段中，劃完后剩下36個(gè)。因2002=36´55+22，說(shuō)明2002是56段中的第22個(gè)數(shù)。解：先考慮1到60的整數(shù) 在1到60的整數(shù)中，3的倍數(shù)有20個(gè)，4的倍數(shù)有15個(gè)，既是3的倍數(shù)又是4的倍數(shù)的數(shù)有5個(gè)，所以劃去3的倍數(shù)和4的倍數(shù)還剩60-20-15+5=30個(gè)。 又因?yàn)槠渲?的倍數(shù)有6個(gè)，需要保留，所以劃完后剩下30+6=36個(gè)因?yàn)?，4，5的最小公倍數(shù)是60，所以每60個(gè)整數(shù)一段中，劃完后均剩下36個(gè)。 因?yàn)?002=36´55+22，所以第2002個(gè)數(shù)是56段中的第22個(gè)數(shù)。因?yàn)榈谝欢沃械牡?2個(gè)數(shù)是37，所以該序列中第2002個(gè)數(shù)是55´60+37=3337。三、 三、鞏固練習(xí)選擇題1、在1到40這四十個(gè)自然數(shù)中選一些數(shù)組成數(shù)集，使其中任何一個(gè)數(shù)不是另一個(gè)數(shù)的2倍，則這個(gè)數(shù)集最多有( )個(gè)數(shù)。A、20 B、26 C、30 D、402、甲、乙、丙、丁四人排成一排照相，甲不排在首位，丁不排在末位，有( )種不同的排法。A、14 B、13 C、12 D、113、從1到1000中，能被2，3，5之一整除的整數(shù)有( )個(gè) A、767 B、734 C、701 D、6984、從1到200中，能被7整除但不能被14整除的整數(shù)有( )個(gè)A、12 B、13 C、14 D、155、A、B、C是面積分別為150、170、230的三張不同形狀的紙片，它們重疊放在一起的覆蓋面積是350，且A與B、B與C、A與C的公共部分面積分別是100、70、90。則A、B、C的公共部分面積是( )A、12 B、13 C、60 D、156、50束鮮花中，有16束插放著月季花，有15束插放著馬蹄蓮，有21束插放著白蘭花，有7束中既有月季花又有馬蹄蓮，有8束中既有馬蹄蓮又有白蘭花，有10束中既有月季花又有白蘭花，還有5束鮮花中，月季花、馬蹄蓮、白蘭花都有。則50束鮮花中，這三種花都沒(méi)有的花束有( )A、17 B、18 C、19 D、20填空題7、一張正方形的紙片面積是50平方厘米，一張圓形的紙片面積是40平方厘米。兩張紙片覆蓋在桌面上的面積是60平方厘米，則這兩張紙片重合部分的面積是 。8、某班有學(xué)生45人，已知其次考試數(shù)學(xué)30人優(yōu)秀，物理28人優(yōu)秀，數(shù)理兩科都優(yōu)秀的有20人。則數(shù)理兩科至少有一科優(yōu)秀的有 人，一科都未達(dá)到優(yōu)秀的有 人。9、某班有學(xué)生50人，參加數(shù)學(xué)興趣小組的有35人，參加語(yǔ)文興趣小組的有30人，每人至少參加一個(gè)組，則兩個(gè)組都參加的有 人。10、一個(gè)數(shù)除以3余2，除以4余1，則這個(gè)數(shù)除以12的余數(shù)是 。11、每邊長(zhǎng)是10厘米的正方形紙片，正中間挖一個(gè)正方形的洞，成為一個(gè)邊寬是1厘米的方框。把5個(gè)這樣的方框放在桌上，成為如圖這樣的圖形。則桌面上被這些方框蓋住的部分面積是 平方厘米。12、200以內(nèi)的正偶數(shù)中與5互質(zhì)的數(shù)有 個(gè)。解答題ABCD13、在線段AB上取兩個(gè)點(diǎn)以C、D， 已知AB=25，AD=19，CB=17，求CD長(zhǎng)。14、求1到200的自然數(shù)中，所有既不是2的倍數(shù)又不是3的倍數(shù)的整數(shù)之和S。15、100名學(xué)生面向老師站成一行，老師先讓大家從左到右按1，2，3，依次報(bào)數(shù)，再讓報(bào)數(shù)是3的倍數(shù)的學(xué)生向后轉(zhuǎn)，接著又讓報(bào)數(shù)是7的倍數(shù)學(xué)生向后轉(zhuǎn)，問(wèn)此時(shí)還有多少學(xué)生面向老師？這些面向老師的學(xué)生的報(bào)數(shù)號(hào)的總和是多少？16、求前500個(gè)正整數(shù)中非5、非7、非11的倍數(shù)的數(shù)的個(gè)數(shù)。17、某校初一年級(jí)有120名學(xué)生，參加體育、文學(xué)、數(shù)學(xué)興趣小組的人數(shù)之和為135，其中，既參加了體育興趣小組又參加了文學(xué)興趣小組有15人，既參加了體育興趣小組又參加了數(shù)學(xué)興趣小組有10人，既參加了文學(xué)興趣小組又參加了數(shù)學(xué)興趣小組有8人，三個(gè)興趣小組都參加的有4人，求三個(gè)興趣小組都沒(méi)有參加的人數(shù)。18、某班語(yǔ)文、數(shù)學(xué)、外語(yǔ)三門(mén)考試成績(jī)統(tǒng)計(jì)結(jié)果如下：課程語(yǔ)文數(shù)學(xué)外語(yǔ)語(yǔ)、數(shù)數(shù)、外語(yǔ)、外至少一門(mén)得滿分人數(shù)911853418問(wèn)：語(yǔ)文、數(shù)學(xué)、外語(yǔ)三門(mén)考試都得滿分的人數(shù)是多少？19、求出分母是111的最簡(jiǎn)真分?jǐn)?shù)的和。20、有1997盞亮著的電燈，各有一個(gè)拉線開(kāi)關(guān)控制著?，F(xiàn)將其順序編號(hào)為1，2，3，1997。將編號(hào)為2的倍數(shù)的燈線拉一下，再將編號(hào)為3的倍數(shù)的燈線拉一下，最后將編號(hào)為5的倍數(shù)的燈線拉一下，拉完后還有幾盞燈是亮的？5