容斥原理之最值問題

1、7-7-5.容斥原理之最值問題教學目標1. 了解容斥原理二量重疊和三量重疊的內(nèi)容；2. 掌握容斥原理的在組合計數(shù)等各個方面的應用知識要點一、兩量重疊問題在一些計數(shù)問題中，經(jīng)常遇到有關(guān)集合元素個數(shù)的計算求兩個集合并集的元素的個數(shù)，不能簡單地把兩個集合的元素個數(shù)相加，而要從兩個集合個數(shù)之和中減去重復計算的元素個數(shù)，即減去交集的元素個數(shù)，用式子可表示成：(其中符號“”讀作“并”，相當于中文“和”或者“或”的意思；符號“”讀作“交”，相當于中文“且”的意思)則稱這一公式為包含與排除原理，簡稱容斥原理圖示如下:表示小圓部分，表示大圓部分，表示大圓與小圓的公共部分，記為：，即陰影面積圖示如下:表示小圓部分

2、，表示大圓部分，表示大圓與小圓的公共部分，記為：，即陰影面積1先包含重疊部分計算了次，多加了次；2再排除把多加了次的重疊部分減去 包含與排除原理告訴我們，要計算兩個集合的并集的元素的個數(shù)，可分以下兩步進行：第一步：分別計算集合的元素個數(shù)，然后加起來，即先求(意思是把的一切元素都“包含”進來，加在一起)；第二步：從上面的和中減去交集的元素個數(shù)，即減去(意思是“排除”了重復計算的元素個數(shù))二、三量重疊問題類、類與類元素個數(shù)的總和類元素的個數(shù)類元素個數(shù)類元素個數(shù)既是類又是類的元素個數(shù)既是類又是類的元素個數(shù)既是類又是類的元素個數(shù)同時是類、類、類的元素個數(shù)用符號表示為：圖示如下：圖中小圓表示的元素的個數(shù)

3、，中圓表示的元素的個數(shù)，大圓表示的元素的個數(shù)1先包含：重疊部分、重疊了次，多加了次2再排除：重疊部分重疊了次，但是在進行 計算時都被減掉了3再包含：在解答有關(guān)包含排除問題時，我們常常利用圓圈圖(韋恩圖)來幫助分析思考例題精講【例 1】 “走美”主試委員會為三八年級準備決賽試題。每個年級道題，并且至少有道題與其他各年級都不同。如果每道題出現(xiàn)在不同年級，最多只能出現(xiàn)次。本屆活動至少要準備 道決賽試題?！究键c】容斥原理之最值問題 【難度】4星 【題型】填空【關(guān)鍵詞】走美杯，4年級，決賽，第9題【解析】 每個年級都有自己道題目，然后可以三至五年級共用道題目，六到八年級共用道題目，總共有（道）題目?！敬?/p>

4、案】題【例 2】 將113這13個數(shù)字分別填入如圖所示的由四個大小相同的圓分割成的13個區(qū)域中，然后把每個圓內(nèi)的7個數(shù)相加，最后把四個圓的和相加，問：和最大是多少？【考點】容斥原理之最值問題 【難度】4星 【題型】填空【解析】 越是中間，被重復計算的越多，最中心的區(qū)域被重復計算四次，將數(shù)字按從大到小依次填寫于被重復計算多的區(qū)格中，最大和為：13×4+（12+11+10+9）×3+（8+7+6+5）×2+（4+3+2+1）=240.【答案】【例 3】 如圖，5條同樣長的線段拼成了一個五角星如果每條線段上恰有1994個點被染成紅色，那么在這個五角星上紅色點最少有多少個

5、?【考點】容斥原理之最值問題 【難度】4星 【題型】填空【解析】 如下圖，下圖中“”位置均有兩條線段通過，也就是交點，如果這些交點所對應的線段都在“”位置恰有紅色點，那么在五角星上重疊的紅色點最多，所以此時顯現(xiàn)的紅色點最少，有1994×5-(2-1)×10=9960個【答案】【例 4】 某班共有學生48人，其中27人會游泳，33人會騎自行車，40人會打乒乓球那么，這個班至少有多少學生這三項運動都會？【考點】容斥原理之最值問題 【難度】4星 【題型】填空【解析】 （法1）首先看至少有多少人會游泳、自行車兩項，由于會游泳的有27人，會騎自行車的有33人，而總?cè)藬?shù)為48人，在會游

6、泳人數(shù)和會騎自行車人數(shù)確定的情況下，兩項都會的學生至少有人，再看會游泳、自行車以及乒乓球三項的學生人數(shù)，至少有人.該情況可以用線段圖來構(gòu)造和示意：（法2）設三項運動都會的人有人，只會兩項的有人，只會一項的有人，那么根據(jù)在統(tǒng)計中會項運動的學生被統(tǒng)計次的規(guī)律有以下等式：由第一條方程可得到，將其代入第二條式子得到：，即而第二條式子還能得到式子，即聯(lián)立和得到，即可行情況構(gòu)造同上【答案】【鞏固】某班有名學生，參加語文競賽的有人，參加數(shù)學競賽的有人，參加英語競賽的有人，每人最多參加兩科，那么參加兩科的最多有 人【考點】容斥原理之最值問題 【難度】4星 【題型】填空【解析】 根據(jù)題意可知，該班參加競賽的共有

7、人次由于每人最多參加兩科，也就是說有參加2科的，有參加1科的，也有不參加的，共是71人次要求參加兩科的人數(shù)最多，則讓這人次盡可能多地重復，而，所以至多有人參加兩科，此時還有1人參加1科那么是否存在35人參加兩科的情況呢？由于此時還有1人是只參加一科的，假設這個人只參加數(shù)學一科，那么可知此時參加語文、數(shù)學兩科的共有人，參加語文、英語兩科的共有人，參加數(shù)學、英語兩科的共有人也就是說，此時全班有15人參加語文、數(shù)學兩科，13人參加語文、英語兩科，7人參加數(shù)學、英語兩科，1人只參加數(shù)學1科，還有14人不參加檢驗可知符合題設條件所以35人是可以達到的，則參加兩科的最多有35人（當然本題中也可以假設只參加

8、一科的參加的是語文或英語）【答案】【鞏固】60人中有的人會打乒乓球，的人會打羽毛球，的人會打排球，這三項運動都會的人有人，問：這三項運動都不會的最多有多少人？【考點】容斥原理之最值問題 【難度】4星 【題型】填空【解析】 設只會打乒乓球和羽毛球兩項的人有人，只會打乒乓球和排球兩項的有人，只會打羽毛球和排球兩項的有人由于只會三項運動中的一項的不可能小于，所以、有如下關(guān)系：將三條關(guān)系式相加，得到，而60人當中會至少一項運動的人數(shù)有人，所以60人當中三項都不會的人數(shù)最多4人（當、分別取、時，不等式組成立）【答案】【例 5】 圖書室有100本書，借閱圖書者需在圖書上簽名已知這100本書中有甲、乙、丙簽

9、名的分別有33，44和55本，其中同時有甲、乙簽名的圖書為29本，同時有甲、丙簽名的圖書為25本，同時有乙、丙簽名的圖書為36本問這批圖書中最少有多少本沒有被甲、乙、丙中的任何一人借閱過?【考點】容斥原理之最值問題 【難度】4星 【題型】填空【解析】 設甲借過的書組成集合A，乙借過的書組成集合B，丙借過的書組成集合C=33, =44，=55，=29，=25，=36本題只需算出甲、乙、丙中至少有一人借過的書的最大值，再將其與100作差即可,當最大時，有最大值.也就是說當三人都借過的書最多時，甲、乙、丙中至少有一人借過的書最多而最大不超過、 6個數(shù)中的最小值，所以最大為25此時=33+44+55-

10、29-25-36+25=67，即三者至少有一人借過的書最多為67本，所以這批圖書中最少有33本沒有被甲、乙、丙中的任何一人借閱過【答案】【鞏固】甲、乙、丙都在讀同-一本故事書，書中有100個故事每個人都從某一個故事開始，按順序往后讀已知甲讀了75個故事，乙讀了60個故事，丙讀了52個故事那么甲、乙、丙3人共同讀過的故事最少有多少個?【考點】容斥原理之最值問題 【難度】4星 【題型】填空【解析】 考慮甲乙兩人情況，有甲乙都讀過的最少為：75+60-100=35個，此時甲單獨讀過的為75-35=40個，乙單獨讀過的為60-35=25個；欲使甲、乙、丙三人都讀過的書最少時，應將丙讀過的書盡量分散在某

11、端，于是三者都讀過書最少為52-40=12個【答案】【例 6】 某數(shù)學競賽共160人進入決賽，決賽共四題，做對第一題的有136人，做對第二題的有125人，做對第三題的有118人，做對第四題的有104人。在這次決賽中至少有_得滿分?！究键c】容斥原理之最值問題 【難度】5星 【題型】填空【關(guān)鍵詞】走美杯，5年級，決賽，第10題【解析】 設得滿分的人都做對3道題時得滿分的人最少，有136+125+118+104-1603=3(人)。【答案】人【例 7】 某班有46人，其中有40人會騎自行車，38人會打乒乓球，35人會打羽毛球，27人會游泳，則該班這四項運動都會的至少有  

12、0;      人?！究键c】容斥原理之最值問題 【難度】5星 【題型】填空【關(guān)鍵詞】希望杯，4年級，1試【解析】 不會騎車的6人，不會打乒乓球的8人，不會羽毛球的11人，不會游泳的19人，那么至少不會一項的最多只有6+8+11+19=44人，那么思想都會的至少44人【答案】人【例 8】 在陽光明媚的一天下午，甲、乙、丙、丁四人給100盆花澆水，已知甲澆了30盆，乙澆了75盆，丙澆了80盆，丁澆了90盆，請問恰好被3個人澆過的花最少有多少盆？【考點】容斥原理之最值問題 【難度】5星 【題型】填空【解析】 為了恰好被3個人澆過的花盆數(shù)量最少，那么被

13、四個人澆過的花、兩個人澆過的花和一個人澆過的花數(shù)量都要盡量多，那么應該可以知道被四個人澆過的花數(shù)量最多是30盆，那么接下來就變成乙澆了45盆，丙澆了50盆，丁澆60盆了，這時共有盆花，我們要讓這70盆中恰好被3個人澆過的花最少，這就是簡單的容斥原理了，恰好被3個人澆過的花最少有盆【答案】【鞏固】 甲、乙、丙同時給100盆花澆水已知甲澆了78盆，乙澆了68盆，丙澆了58盆，那么3人都澆過的花最少有多少盆?【考點】容斥原理之最值問題 【難度】4星 【題型】填空【解析】 只考慮甲乙兩人情況，有甲、乙都澆過的最少為：78+68-100=46盆，此時甲單獨澆過的為78-46=32盆，乙單獨澆過的為68-46=22盆；欲使甲、乙、丙三人都澆過的花最少時，應將丙澆過的花盡量分散在兩端于是三者都澆過花最少為58-32-22=4盆【答案】【鞏固】 在陽光明媚的一天下午，甲、乙、丙、丁四人給100盆花澆水，已知甲澆了30盆，乙澆了75盆，丙