|
第八講 容斥原理 在一些計(jì)數(shù)問題中，經(jīng)常遇到有關(guān)集合元素個(gè)數(shù)的計(jì)算。我們用|A|表示有限集A的元素個(gè)數(shù)。在并集的討論中，已經(jīng)知道，求兩個(gè)集合并集的元素的個(gè)數(shù)，不能簡單地把兩個(gè)集合的元素個(gè)數(shù)相加，而要從兩個(gè)集合個(gè)數(shù)之和中減去重復(fù)計(jì)算的元素個(gè)數(shù)，即減去交集的元素個(gè)數(shù)，用式子可表示成 |A∪B|=|A|+|B|-|A∩B| 我們稱這一公式為包含與排除原理，簡稱容斥原理。 包含與排除原理告訴我們，要計(jì)算兩個(gè)集合A、B的并集A∪B的元素的個(gè)數(shù)，可分以下兩步進(jìn)行： 第一步 分別計(jì)算集合A、B的元素個(gè)數(shù)，然后加起來，即先求|A|+|B|（意思是把A、B的一切元素都“包含”進(jìn)來，加在一起）； 第二步 從上面的和中減去交集的元素個(gè)數(shù)，即減去|A∩B|（意思是“排除”了重復(fù)計(jì)算的元素個(gè)數(shù)）。 例1 求不超過20的正整數(shù)中是2的數(shù)倍或3的倍數(shù)的數(shù)共有多少個(gè)。 分析與解：設(shè)I=｛1，2，3，…，19，20｝，A=｛I中2的倍數(shù)｝，B=｛I中3的倍數(shù)｝。 顯然，題目要求計(jì)算并集|A∪B|的元素個(gè)數(shù)，即求|A∪B|。 易知， A=｛2，4，6，…，18，20｝， 共有10個(gè)元素，即|A|=10， B=｛3，6，9，12，15，18｝， 共有6個(gè)元素，即|B|=6。 A∩B=｛I中既是2的倍數(shù)又是3的倍數(shù)｝ =｛6，12，18｝ 共有3個(gè)元素，即|A∩B|=3，所以 |A∪B|=|A|+|B|-|A∩B| =10+6-3=13 答：所求的數(shù)共有13個(gè)。 此題可直觀地圖示如下：
圖8-1中，A表示不超過20的正整數(shù)中2的倍數(shù)的集合。B表示不超過20的正整數(shù)中3的倍數(shù)的集合。在不超過20的正整數(shù)中既是2的倍數(shù)又是3的倍數(shù)的數(shù)有6，12，18，即A∩B中的數(shù)。 例2 某班統(tǒng)計(jì)考試成績，數(shù)學(xué)得90分上的有25人；語文得90分以上的有21人；兩科中至少有一科在90以上有38人。問兩科都在90分以上的有多少人？（1985年初一迎春杯數(shù)學(xué)競(jìng)賽試題） 解：設(shè)A=｛數(shù)學(xué)成績90分以上的學(xué)生）， B=｛語文成績90分以上的學(xué)生｝。 那么，集合A∪B表示兩科中至少有一科在90分以上的學(xué)生，由題意知 |A|=25，|B|=21，A∪B=38。 現(xiàn)在要求兩科都在90分以上的學(xué)生人數(shù)，即求|A∩B|。由容斥原理得 |A∩B|=|A|+|B|-|A∪B|=25+21-38=8 答：兩科都在90分以上的學(xué)生有8人。 在計(jì)算面積的問題中，有時(shí)也要用到容斥原理。 例3 邊長為2的正方形與邊長為3的正方形，如圖8—2放在桌面上，它們所蓋住的面積有多大？ 分析與解：如果把兩個(gè)正方形的面積加起來，得 22+32=13 就會(huì)發(fā)現(xiàn)，多計(jì)算了一塊陰影部分面積。這塊面積是1.52=2.25。應(yīng)該從上面的和中減去這一部分。因此，兩個(gè)正方形所蓋住的面積應(yīng)是
22+32-1.52 =13-2.25=10.75 答：兩個(gè)正方形所蓋住的面積是10.75。 例4 有100位旅客，其中有10人既不懂英語又不懂俄語，有75人懂英語，83人懂俄語。問既懂英語又懂俄語的有多少人？（1985年小學(xué)迎春杯數(shù)學(xué)競(jìng)賽試題） 分析與解：設(shè)A=｛懂英語的旅客｝，B=｛懂俄語的旅客｝。那么，英語和俄語這兩種語言中至少懂一種的旅客的集合為A∪B，而兩種語言都懂的旅客的集合為A∩B。題目要求|A∩B|。 由題意知，|A|=75，|B|=83，|A∪B|=100-10=90。由容斥原理，得 |A∩B|=|A|+|B|-|A∪B| =75+83-90=68 答：既懂英語又懂俄語的旅客有68人。 對(duì)于任意三個(gè)有限集合A、B、C，我們可以將上面的容斥原理推廣得到如下的公式： |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|。 三個(gè)集合的容斥原理告訴我們，要計(jì)算并集A∪B∪C的元素個(gè)數(shù)，可以分三步進(jìn)行： 第一步 求|A|+|B|+|C|； 第二步 減去|A∩B|，|A∩C|，|B∩C|； 第三步 加上|A∩B∩C|。 結(jié)合圖8—3還可以作出如下說明。由于A∪B∪C一般可分成如圖的七個(gè)部分，或者說分成了七個(gè)不相交的子集。其中Ⅰ、Ⅱ、Ⅲ部分的元素僅屬于某個(gè)集合，而Ⅳ、V、Ⅵ部分的元素分別屬于某兩個(gè)集合，第Ⅶ部分則是三個(gè)集合的交集由于A∪B∪C的元素分別來自集合A、B、C，因此，先計(jì)算|A|+|B|+|C|。在這個(gè)和里，Ⅰ、Ⅱ、Ⅲ部分的元素只計(jì)算了一次，而Ⅳ、V、Ⅵ部分的元素各計(jì)算了兩次，第Ⅶ部分（A∩B∩C）的元素計(jì)算了三次。在第二步減去|A∩B|，|A∩C|，|B∩C|后得 |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|。
這樣顯然消除了IV、V、VI部分的重復(fù)計(jì)算，但同時(shí)連續(xù)三次減去了第Ⅶ部分，于是第Ⅶ部分的元素個(gè)數(shù)都被減去了，因此必須補(bǔ)上第Ⅶ部分的元素個(gè)數(shù)，即再加上|A∩B∩C|，綜上所述得 |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|。 例5 某校組織棋類比賽，分成圍棋、中國象棋和國際象棋三個(gè)組進(jìn)行。參加圍棋比賽的共有42人，參加中國象棋比賽的共有51人，參加國際象棋比賽的共有30人。同時(shí)參加了圍棋和中國象棋比賽的共有13人，同時(shí)參加了圍棋和國際象棋比賽的7人，同時(shí)參加了中國象棋和國際象棋比賽的11人，其中三種棋賽都參加的3人。問參加棋類比賽的共有多少人？ 解法1：設(shè)A=｛參加圍棋比賽的人｝，B=｛參加中國象棋比賽的人｝，C=｛參加國際象棋比賽的人｝，那么參加棋類比賽的人的集合為A∪B∪C。由題意知： |A|=42，|B|=，|C|=30， |A∩B|=13，|A∩C|=7，|B∩C|=11， |A∩B∩C|=3。 由容斥原理得 |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∪C|-|B∩C|+|A∩B∩C| =42+51+30-13-7-11+3 =95（人） 答：參加棋類比賽的共有95人。 解法2：利用文氏圖逐個(gè)填寫各區(qū)域所表示的集合元素的個(gè)數(shù)，然后求出最后結(jié)果。
設(shè)A、B、C分別表示參加圍棋、中國象棋和國際象棋比賽的人的集合。其文氏圖分割成七個(gè)互不相交的區(qū)域。區(qū)域Ⅶ（即A∩B∩C）表示三種棋賽都參加的數(shù)的集合。由題意應(yīng)填數(shù)字3。區(qū)域IV表示僅參加圍棋和中國象棋兩項(xiàng)比賽的人的集合，其人數(shù)為13-3=10（人）。區(qū)域Ⅵ表示僅參加圍棋和國際象棋兩項(xiàng)比賽的人的集合，其人數(shù)為7-3=4（人）。區(qū)域Ⅰ表示只參加圍棋一項(xiàng)比賽的人的集合，其人數(shù)為42-10-4-3=25（人）。同理可把區(qū)域Ⅱ、Ⅲ、V所表示的集合的人數(shù)逐個(gè)算出，分別填入相應(yīng)的區(qū)域內(nèi)（圖8—4）。由此得出參加棋類比賽的總?cè)藬?shù)為 25+30+15+15+10+8+4=3=95 說明：解法2簡單直觀，不易出錯(cuò)。由于各個(gè)區(qū)域所表示的集合的元素個(gè)數(shù)都計(jì)算出來了，因此提供了較多的信息，易于回答各種方式的提問。 例6 邊長分別為6，5，2的三個(gè)正方形，如圖8—5所示放在桌面上。問它們蓋住的面積是多大？
分析與解：這個(gè)問題可用容斥原理來解。設(shè)R表示正方形區(qū)域ABCD，R1表示正方形區(qū)域A1B1C1D1，R2表示正方形區(qū)域A2B2C2D2。那么R∩R1表示正方形區(qū)域BOD1M，R∩R2表示矩形區(qū)域A2FND2，R1∩R2表示矩形區(qū)域A2B2GE，R∩R1∩R2表示正方形區(qū)域A2FOE個(gè)正方形所蓋住的部分為R∪R1∪R2。如果用|R|表示區(qū)域R的面積，那么根據(jù)容斥原理可得 |R∪R1∪R2|=|R|+|R1|+|R2|-|R∩Rl| -|R∩R2|-|R1∩R2|+|R∩R1∩R2| =62+52+22-（32+2×1+1×2）+12 =53 答：三個(gè)正方形所蓋住的面積為53。 例7 某班學(xué)生手中分別拿有紅、黃、藍(lán)三種顏色的球。已知手中有紅球的共有34人，手中有黃球的共有26人，手中有藍(lán)球的共有18人。其中手中有紅、黃、藍(lán)三種球的有6人。而手中只有紅、黃兩種球的有9人，手中只有黃、藍(lán)兩種球的有4人，手中只有紅、藍(lán)兩球的有3人，那么這個(gè)班共有多少人？（1986年初一迎春杯數(shù)學(xué)競(jìng)賽試題） 分析與解：此題用填寫文氏圖各區(qū)域元素個(gè)數(shù)的方法來解較為簡便，設(shè)A、B、C分別表示手中有紅球、黃球、藍(lán)球的人的集合。由題意可逐一填出各區(qū)域元素的個(gè)數(shù)（如圖）。所以全班共有 16+7+5+9+4+3+6 =50（人） 答：這個(gè)班共有50人。 這個(gè)題目也可以列式計(jì)算如下： （34+26+18）-（9+4+3）-2×6=50（人）  例8 求1到200的自然數(shù)中不能被2、3、5中任何一個(gè)數(shù)整除的數(shù)有多少？ 解： 設(shè)A=｛1到200中間能被2整除的數(shù)｝， B=｛1到200中間能被3整除的數(shù)｝， C=｛1到200中間能被5整除的數(shù)｝。 那么，A∩B=｛1到200中間能被2×3整除的數(shù)｝， A∩C=｛1到200中間能被2×5整除的數(shù)｝， B∩C=｛1到200中間能被3×5整除的數(shù)｝， A∩B∩C=｛1到200中間能被2×3×5整除的數(shù)｝。 設(shè)［x］表示小于等于x的最大整數(shù)，那么 ?。麬｜=［200/2］=100，｜B｜=［200/3］=66， ?。麮｜=［200/5］=40，｜A∩B｜=［200/6］=33， ?。麬∩C｜=［200/10］=20，｜B∩C｜=［200/15］=13， ｜A∩B∩C｜=［200/30］=6。 根據(jù)容斥原理，1到200的自然數(shù)中至少能被2，3，5中一個(gè)數(shù)整除的數(shù)共有 |A∪B∪C|=|A|+|B|+|C|-|A∩B| =|A∩C|-|B∩C|+|A∩B∩C| =100+66+40-33-20-13+6=146（個(gè)） 所以1到200的自然數(shù)中不能被2，3，5中任何一個(gè)數(shù)整除的數(shù)共有 200-146=54（個(gè)） 習(xí)題八 1.某班有團(tuán)員23人。這個(gè)班里男生共20人，問這個(gè)班女生團(tuán)員比男生非團(tuán)員多多少人？ 2.紙片面積為7，一張邊長為2的正方形紙片，把這兩張紙片放在桌面上覆蓋的面積為8，問兩張紙片重合部分的面積是多少？ 3.從1到100的自然數(shù)中， ?。?）不能被6和10整除的數(shù)有多少個(gè)？ ?。?）至少能被2，3，5中一個(gè)數(shù)整除的數(shù)有多少個(gè)？ 4.盛夏的一天，有10個(gè)同學(xué)去冷飲店，向服務(wù)員交了一份需要冷飲的統(tǒng)計(jì)表：要可樂、雪碧、果汁的各有5人；可樂、雪碧都要的有3人；可樂、果汁都要的有2人；雪碧、果汁都要的有2人；三樣都要的只有1人。證明其中一定有1人這三種飲料都沒有要。 5.對(duì)100個(gè)學(xué)生課外學(xué)科活動(dòng)的調(diào)查結(jié)果如下：32人參加數(shù)學(xué)小組；20人參加英語小組，45人參加生物小組。其中15人既參加了數(shù)學(xué)小組又參加了生物小組；7人既參加了英語小組又參加了數(shù)學(xué)小組；10人既參加了英語小組又參加了生物小組。還有30人沒有參加上述任何一個(gè)學(xué)科小組。 ?。?）求三個(gè)學(xué)科小組都參加的人數(shù)。 ?。?）在文氏圖的八個(gè)區(qū)域內(nèi)填入相應(yīng)的學(xué)生人數(shù)。其中A、B、C分別表示參加數(shù)學(xué)、英語和生物小組的學(xué)生的集合。被調(diào)查的100個(gè)學(xué)生的集合為全集I。
測(cè)試題（一） 1.在□里填上適當(dāng)?shù)臄?shù)。 2.化簡。 3.計(jì)算 4.在100名選手間進(jìn)行乒乓球單打淘汰賽，每場(chǎng)能分勝負(fù)。問冠軍產(chǎn)生時(shí)，共舉行了幾場(chǎng)比賽。 5.有一座樓高19層，相鄰兩層之間都有19級(jí)臺(tái)階，小紅從一層走到13層，一共要登多少級(jí)臺(tái)階？ 6.學(xué)校第一次買7個(gè)籃球3個(gè)足球共花256元，第二次買4個(gè)籃球3個(gè)足球共花172元，1個(gè)籃球、1個(gè)足球各多少元？ 7.下面各數(shù)中，那個(gè)數(shù)是分別被3、5、7除后所得余數(shù)依次為1、1、5的最小自然數(shù)。 ?。ˋ）166（B）151（C）145（D）以上都不對(duì)。 8.若數(shù)列a1，a2…，a1993，…中，從第三項(xiàng)開始，每一項(xiàng)為前二項(xiàng)之和，已知a1=12，a2=13，問第1993項(xiàng)（a1993）被3除的余數(shù)是多少？ 9.前106個(gè)自然數(shù)中，既非完全平方數(shù)又非完全立方數(shù)的數(shù)有幾個(gè)？ 10.左下圖是由20個(gè)棱長都是1厘米的小正方體拼成的幾何體，求它的表面積是多少？
11.右上圖是在一個(gè)邊長為4厘米的正方體的前后、左右、上下各面的中心位置上，挖去一個(gè)底面圓半徑為1厘米，高為1.5厘米圓柱體后，得到的一 12.唐僧師徒四人路過一村，發(fā)現(xiàn)有人說實(shí)話，有人說假話。一天唐僧命孫悟空找來四人，問他們是說實(shí)話的還是說假話的人？四人回答如下：“甲說：“我們四人全說假話。”乙說：“我們四人中只有一人說假話。”丙說：“我們四人中有兩人說假話。”丁說：“我是說實(shí)話的人。”請(qǐng)判斷丁是說實(shí)話還是說假話？ 13.在桌子上有七張紙片，從中取出若干張，每張都剪成七塊，放在桌子上；再從桌子上取出若干張，每張又都剪成七塊，都放在桌子上；……問能否在某一時(shí)刻，在桌子上出現(xiàn)1990塊？1991塊？1992塊？1993塊？ |
|
|
