1、7-7-4容斥原理之數論問題7-7-4.容斥原理之數論問題.題庫page 3 of 8教師版mj加昨教學目標1 . 了解容斥原理二量重疊和三量重疊的內容；2 .掌握容斥原理的在組合計數等各個方面的應用.趾M蚱 知識要點一、兩量重疊問題在一些計數問題中，經常遇到有關集合元素個數的計算.求兩個集合并集的元素的個數， 不能簡單地把兩個集合的元素個數相加，而要從兩個集合個數之和中減去重復計算的元素個數，即減去交集的元素個數， 用式子可表示成：AljB = A+B-API B （其中符號“ U ”讀作 “并”，相當于中文“和”或者“或”的意思；符號“ n ”讀作“交”，相當于中文“且”的意思.）則稱這一

2、公式為包含與排除原理， 簡稱容斥原理.圖示如下：A表示小圓部分，B 表示大圓部分，C表示大圓與小圓的公共部分， 記為：AB,即陰影面積.圖示如下：A表 示小圓部分，B表示大圓部分，C表示大圓與小圓的公共部分， 記為：API B,即陰影面積.1 .先包含一一A + B重疊部分AB計算了 2次，多加了 1次;2 .再排除一一A+B -Ap B把多加了 1次的重疊部分 AB減去.包含與排除原理告訴我們，要計算兩個集合A B的并集AL.B的元素的個數，可分以下兩步進行：第一步：分別計算集合 A、B的元素個數，然后加起來，即先求 A + B （意思是把A B的一 切元素都“包含”進來，加在一起 ）；第二

3、步：從上面的和中減去交集的元素個數，即減去C=AP|B （意思是“排除” 了重復計算的元素個數）.二、三量重疊問題A類、B類與C類元素個數的總和 =A類元素的個數 +B類元素個數+C類元素個數- 既是A類又是B類的元素個數 -既是B類又是C類的元素個數-既是A類又是C類的元素個數十同時是 A類、B類、C類的元素個數.用符號表示為：A UB UC =A+B +C AQB BQC -ApC +Af! BRC .圖示如下： 4V圖中小圓表示 A的元素的個數，中圓表示 B的元素的個數, 大圓表示C的元素的個數.cfp1.先包含：重疊部分2.再排除：重疊部分ABCAB、BC、CA重疊了 2次，多加了 1

4、次.A B C -AQB -BpC -AQ CAPI Bn C重疊了 3次，但是在進行A+B+C_AP|BBp|CAP1C計算時都被減掉了.產包含：A+B+c-AnB-Bnc-Anc+AnBriC_JI加巨例題精講在解答有關包含排除問題時，我們常常利用圓圈圖（韋恩圖）來幫助分析思考.例1在1 100的全部自然數中，不是 3的倍數也不是5的倍數的數有多少個?【考點】容斥原理之數論問題【難度】2星【題型】解答【解析】如圖，用長方形表示1 100的全部自然數，A圓表示1 100中3的倍數，B圓表示 1100中5的倍數，長方形內兩圓外的部分表示既不是3的倍數也不是5的倍數的數.由100-3=33川1可

5、知，1100中3的倍數有33個；由100 + 5 =20可知，1100中5的倍數 有20個；由100 + （3父5） =6|10可知，1 100既是3的倍數又是5的倍數的數有6個.由包含排除法，3或5的倍數有：33+20-6 =47（個）.從而不是3的倍數也不是5的倍數的 數有 100 -47 =53（個）.【答案】53【鞏固】 在自然數1100中，能被3或5中任一個整除的數有多少個？【考點】容斥原理之數論問題【難度】2星【題型】解答【解析】100+3 =33|1 , 100+5 =20, 100-（3X5） =6巾10.根據包含排除法，能被 3或5 中任一個整除的數有 33 +20 -6 =

6、47（個）.【答案】47【鞏固】 在前100個自然數中，能被 2或3整除的數有多少個？【考點】容斥原理之數論問題【難度】2星【題型】解答【解析】如圖所示，A圓內是前100個自然數中所有能被 2整除的數，B圓內是前100個自 然數中所有能被3整除的數，C為前100個自然數中既能被 2整除也能被3整除的 前100個自然數中能被 2整除的數有：100+2=50（個）.由100+323怖 知，前100個自然 數中能被3整除的數有：33個.由100-（2x3） =16山4知，前100個自然數中既能被 2整除 也能被3整除的數有16個.所以A中有50個數，B中有33個數，C中有16個數.因為A, B都包含

7、C ,根據包含排 除法得到，能被2或3整除的數有：50 +33-16=67（個）.【答案】67【例2】 在從1至1000的自然數中，既不能被 5除盡，又不能被7除盡的數有多少個？【考點】容斥原理之數論問題【難度】2星【題型】解答【解析】11000之間，5的倍數有,000 1=200個，7的倍數有 竿=142 個，因為既是5的倍數，又是7的倍數的數一定是 35的倍數，所以這樣的數有1000 1=28一 35所以既不能被5除盡，又不能被 7除盡的數有1000-200-142+-28=686個.【答案】686【鞏固】 求在1至100的自然數中能被 3或7整除的數的個數.【考點】容斥原理之數論問題【難

8、度】2星【題型】解答【解析】 記 A: 1100中3的倍數，100+3=33山川1 ,有33個；B: 1100中7的倍數,100+7=14|用|2,有14個；AB： 1100中3和7的公倍數，即21的倍數，100+21=4|川16 ,有4個. 依據公式，1100中3的倍數或7的倍數共有33+144 =43個，則能被3或7整除的數的 個數為43個.【答案】43【例3】 以105為分母的最簡真分數共有多少個？它們的和為多少？【考點】容斥原理之數論問題【難度】4星【題型】解答【解析】 以105為分母的最簡真分數的分子與105互質，105=3X 5X7,所以也是求1到105不是3、5、7倍數的數有多少

9、個，3的倍數有35個，5的倍數有21個，7的倍數 有15個，15的倍數有7個，21的倍數有5個，35的倍數有3個，105的倍數有1 個，所以105以內與105互質的數有105-35-21-15+7+5+3-1=48 個，顯然如果 n 與105互質，那么（105-n）與n互質，所以以105為分母的48個最簡真分數可兩 個兩個湊成1 ,所以它們的和為 24.【答案】48個，和24【鞏固】 分母是385的最簡真分數有多少個？并求這些真分數的和【考點】容斥原理之數論問題【難度】4星【題型】解答【解析】385=5X 7X 11,不超過385的正整數中被5整除的數有77個；被7整除的數有55 個；被11整

10、除的數有35個；被77整除的數有5個；被35整除的數有11個；被 55整除的數有7個；被 385整除的數有 1個；最簡真分數的分子可以有385-77-55-35+5+11+7-1=240.對于某個分數 a/385如果是最簡真分數的話，那么 （385-a） /385也是最簡真分數，所以最簡真分數可以每兩個湊成整數1,所以這些真分數的和為120.【答案】240個，120個例4在1至2008這2008個自然數中，恰好是 3、5、7中兩個數的倍數的數共有個.【考點】容斥原理之數論問題【難度】3星【題型】填空【關鍵詞】西城實驗【解析】1到2008這2008個自然數中，3和5的倍數有，型081=133個，

11、3和7的倍數有一 15產008 1=95個,5和7的倍數有/0叫=57個,3、5和7的倍數有0叫=19個.所21 35IL105以，恰好是3、5、7中兩個數的倍數的共有 13319 +9519+5719 = 228個.【答案】228個例5求1到100內有 個數不能被2、3、7中的任何一個整除?！究键c】容斥原理之數論問題【難度】3星【題型】填空【關鍵詞】學而思杯，4年級，第12題【解析】 被2整除的有50個，被3整除的有33個，被7整除的有14個同時被2和3整除的有16個，同時被2和7整除的有7個，同時被3和7整除的有4個同時被 2 和 3 和 7 整除的有 2 個，100（50+33+1416

12、7 4 +2 ）=10072 =28 個【答案】28個?！纠?】 在從1到1998的自然數中，能被 2整除，但不能被 3或7整除的數有多少個？【考點】容斥原理之數論問題【難度】3星【題型】解答【解析】 戶表示取商的整數部分.例如，.7=3.要注意的是，符號 I 與十、父、一b.2小符號一樣，也是一種運算，叫取整運算.本題中，先求出能被 2整除的數有多少個，再分別求出能被2和3、能被2和7分別整除的數的個數，那么用能被2整除的數的個數減去能被 2和3整除的數的個數，再減去能被2和7整除的數的個數，所得的差是不是所求的得數呢？仔細想想你會發現不是的，因為它多減了能同時被2、3、7整除的數.故能被2

13、整除的有：1998 + 2 =999（個）.能被2和3同時整除的有：1998-（2父3） =333（個）.能被2和7同時整除的有：1998-（2父7）=142.能被2、3、7同時整除的有：1998 - （2X3X7） =47（個）.所以，能被2整除，但不能被 3或7整除的數有999 333-142 +47 =571 （個）. 【答案】571個【例7】50名同學面向老師站成一行.老師先讓大家從左至右按1, 2, 3,，49, 50依次報數；再讓報數是 4的倍數的同學向后轉，接著又讓報數是6的倍數的同學向后轉.問：現在面向老師的同學還有多少名？【考點】容斥原理之數論問題【難度】3星【題型】解答【關

14、鍵詞】華杯賽，初賽，第 13題【解析】 在轉過兩次后，面向老師的同學分成兩類：第一類是標號既不是 4的倍數，又不是6的倍數；第二類是標號既是 4的倍數又是6的倍數.1-50之間，4的倍數有.|5° 1=12, 6的倍數有.|50 1=8,即是4的倍數又是6的倍數的數一定是12的倍數，所以有 廬01=4.于是，第一類同學有 50- 12-8+4=34人，第二 .12類同學有4人，所以現在共有34+4=38名同學面向老師.【答案】38名【例8】 體育課上，60名學生面向老師站成一行，按老師口令，從左到右報數：1,2,3,60,然后，老師讓所報的數是4的倍數的同學向后轉，接著又讓所報的數是

15、5的倍數的同學向后轉，最后讓所報的數是6的倍數的同學向后轉，現在面向老師的學生有 人。【考點】容斥原理之數論問題【難度】3星【題型】填空【關鍵詞】希望杯，六年級，二試，第 15題，4分【解析】 可知其中4的倍數有15個，5的倍數有12個，6的倍數有10個，同時是4和5 的倍數的有3個，同時是5和6的倍數的有2個，同時是4和6的倍數的有5個， 同時是4、5、6的倍數的數有1個，現在背向老師的有 15+12+10-3-2-5+1=28 個， 面向老師的學生有 60-28=32人。轉過兩次的有：3- 1+2 1+5 1 = 7。最后面向老師的學生數=32+7= 39個。【答案】39個【例9】 有20

16、00盞亮著的電燈，各有一個拉線開關控制著，現按其順序編號為1,2,3,，2000,然后將編號為2的倍數的燈線拉一下， 再將編號為3的倍數的燈線拉一下， 最后將編號為5的倍數的燈線拉一下，三次拉完后，亮著的燈有多少盞？【考點】容斥原理之數論問題【難度】3星【題型】解答【解析】 三次拉完后，亮著的燈包括不是2、3、5的倍數的數以及是 6、10、15的倍數但不是30的倍數的數.12000這2000個正整數中，2的倍數有1000個，3的倍數有 666個，5的倍數有400個，6的倍數有333個，10的倍數有200個，15的倍數有 133 個，30 的倍數有 66 個，亮著的燈一共有 2000-1000-

17、666- 400+2X （333+200+133） -4X66=1002 盞.【答案】1002盞【鞏固】2006盞亮著的電燈，各有一個拉線開關控制，按順序編號為1,2,3,，2006。將編號為2的倍數的燈的拉線各拉一下；再將編號為3的倍數的燈的拉線各拉一下，最后將編號為5的倍數的燈的拉線各拉一下。拉完后這著的燈數為 （）盞?！究键c】容斥原理之數論問題【難度】3星【題型】填空【關鍵詞】走美杯，五年級，第 11題，六年級，第11題【解析】 因為燈在開始的時候是亮著的，所以拉了兩次或者沒拉的燈最后還是亮的.這道題實際上是求1到2006中不能被2、3、5整除的數和只能同時被 2、3、5中2個數整除的數

18、的總個數.我們可以求得被 2整除的數有2006 + 2 =1003（盞）,被3整除的數有2006 +3=668|2,共668（盞），被5整除的數有2006 +5=401中1 ,共401（盞）.其中，同時被2、3整除的數有2006-（2 X3）=334102,共334（盞）；同時被 3、5 整除的有 2006 + （3乂5）=133|11,共 133（盞）；同時被2、5整除的數有2006 +（2黑5） =200|6,共200（盞）；同時被2、3、5整除的數有2006 +（2父3 m 5） =66|26 ,共66（盞），所以，只能同時被 2、3、5中2個數整除的數的個數為 334 +133 +20

19、0-3父66 =469（盞）,不能被2、3、5整除的數的7-7-4.容斥原理之數論問題.題庫教師版page 6 0f 8個數為 2006 (1003+668+401)(334+133+200)+66=535(盞)所以，最后亮著的燈一共為469 +535 =1004(盞).【答案】1004盞【鞏固】 寫有1到100編號的燈100盞，亮著排成一排，每一次把編號是3的倍數的燈拉一次開關，第二次把編號是 5的倍數的燈拉一次開關，那么亮著的燈還有多少盞？【考點】容斥原理之數論問題【難度】3星【題型】解答7-7-4.容斥原理之數論問題.題庫page 9 of 8教師版因為燈在開始的時候是亮著的，所以拉了兩

20、次或者沒拉的燈最后還是亮的.燈有10 0-=6(1001003 5盞)，取后鳧著的燈一共為 53+6(3t 20 6)盞5)3,拉兩= 59(盞)沒拉的次的有59盞【例10】200名同學編為1至200號面向南站成一排.第 1次全體同學向右轉(轉后所有 的同學面朝西)；第2次編號為2的倍數的同學向右轉；第 3次編號為3的倍數 的同學向右轉；第 200次編號為200的倍數的同學向右轉；這時，面向東 的同學有 名.【考點】容斥原理之數論問題【難度】3星【題型】填空【關鍵詞】迎春杯，五年級，初賽， 10題【解析】只有約數個數被4除余3的數，最后面向東.約數個數為3的數有22、32、52、72、112、

21、132 ,共8個數.約數個數為7的數有26, 1個，約數個數為15的數有32 24 =144 , 1個一共有8個滿足條件的編號.【答案】8名【例11】下編號是1、2、3、36號白36名學生按編號順序面向里站成一圈.第一次，編號是1的同學向后轉，第二次，編號是2、3的同學向后轉，第三次，編號是4、 5、6的同學向后轉，第 36次，全體同學向后轉.這時，面向里的同學還有 名.【考點】容斥原理之數論問題【難度】3星【題型】填空【關鍵詞】迎春杯，中年級，復試， 10題【解析】整個過程中一共轉了 1+2+3+4- +36=66 6人次，每轉過72人次所有學生的朝向就會 和原來一樣，那么 666+72=9

22、18,于是應該有 18名同學面朝里，18名同學面朝 夕卜?！敬鸢浮?8名【例12】在游藝會上，有100名同學抽到了標簽分別為1至100的獎券.按獎券標簽號發放獎品的規則如下：(1)標簽號為2的倍數，獎2支鉛筆；(2)標簽號為3的倍數，獎3支鉛筆；(3)標簽號既是2的倍數，又是3的倍數可重復領獎；(4)其他標簽號均獎1支鉛筆.那么游藝會為該項活動準備的獎品鉛筆共有多少支？【考點】容斥原理之數論問題【難度】4星【題型】解答【解析】1100, 2的倍數有|1°° 1=50, 3的倍數有匕33個，因為既是2的倍數，又是3的倍數的數一定是 6的倍數，所以標簽為這樣的數有理 1=16個

23、.于是，既, 6不是2的倍數，又不是 3的倍數的數在1100中有100-50-33+16=33 .所以，游 藝會為該項活動準備的獎品鉛筆共有：50X2+33X 3+33X 1=232 支.【答案】232支【例13】在一根長木棍上，有三種刻度線，第一種刻度線將木棍分成十等份；第二種將木 棍分成十二等份；第三種將木棍分成十五等份；如果沿每條刻度線將木棍鋸斷， 則木棍總共被鋸成 段.【考點】容斥原理之數論問題【難度】3星【題型】填空【解析】假設木棍長60cm ,則沿第一種刻度線鋸成的木棍每段長60-10 =6cm ,沿第二種刻度線鋸成的木棍每段長60 M 12 = 5cm,沿第三種刻度線鋸成的木棍每

24、段長60 十14 = 4cm.因為，沿三種刻度線可將木棍分別鋸成10、12、15段；沿第一、二種重合的刻度線可將木棍鋸成6046,5 =2段，沿第一、三種重合的刻度線可將木棍鋸成6046,4 =5段，沿第二、三種重合的刻度線可將木棍鋸成60 + 5, 4 = 3段；沿三種刻度重合的刻度線可將木棍鋸成60 - 6,5, 4 = 1段.應該減去重復計算的沿任意兩種重合的刻度線鋸成的段數，應加上多減去的沿三種刻度重合的刻度線鋸成的段數.所以，沿每條刻度線將木棍鋸斷，則木棍總共被鋸成10 y2 +15 -2 -5 -3 +1 =28 段.【答案】28段【例14】一根101厘米長的木棒，從同一端開始，第一次每隔2厘米畫一個刻度，第二次每隔3厘米畫一個刻度，第三次每隔5厘米畫一個刻度，如果按刻度把木棒截斷， 那么可以截出 段.【考點】容斥原理之數論問題【難度】4星【題型】填空【關鍵詞】101中學【解析】 要求出截出的段數，應當先求出木