名校真題精講共講計數與組合專題學生

1、第6講 計數與組合專題 一、 計數問題1、枚舉法枚舉法就是把所有可能得情況一一列舉出來，然后數一下總共有幾種情況2、加乘原理（1）加法原理分類如果完成一件事有幾類方式，在每一類方式中又有不同的方法，那么把每類的方法數相加就得到所有的方法數（2）乘法原理分步如果完成一件事有幾個步驟，在每一個步驟中又有不同的方法，那么把每步的方法數相乘就得到所有的方法數3、排列組合（1）排列從m個不同元素中取出n個（），并按照一定的順序排成一列，其方法數叫做從m個不同元素中取出n個的排列數，記作.其計算方法為：即從m開始遞減地連乘n個數(2)組合從m個不同元素中取出n個（）組成一組（不計順序），其方法數叫做從m個

2、不同元素中取出n個不同的組合數，記作.其計算方法為：4、分類法與排除法（1）分類法：分來法解決問題的基本思想是通過分類拆解把一個復雜問題轉化成幾個相對簡單的小問題來解決（2）排除法：當題目中滿足要求的情況較多，分類法不好解決時，可以嘗試用排除法，把不符合要求的情況去掉，剩下的就是符合的5、容斥原理（1）理解簡單容斥原理（兩個之間的重疊）與復雜容斥原理（三個之間的重疊）（2）用文氏圖幫助解題6、遞推方法（1）上樓梯模型（2）傳球法列表寫出每一步中具體的方法數（3）幾何圖形分平面增量分析7、插板法用于求解“把m個相同的球放到n個不同的盒子中”這類問題（1）注意：球必須是相同的，盒子必須是不同的（2

3、）如果要求每個盒子至少一個球，那么方法數為（把n-1個板插到m-1個空隙中）（3）如果要求每個盒子可以為空，那么方法數為（先借n個球，然后按照每個盒子至少1個去放，最后從每個盒子中拿出1個還回去）（4）方程的正整數解共組（把n個球放到3個盒子中，每個盒子至少1個）（5）方程的自然數解共組（把n個球放到3個盒子中，每個盒子可以為空）8、與旋轉、翻轉相關的計數這類問題要想清楚是否有重復，重復了多少一般求解時，要先固定一些對象，使其不能旋轉或翻轉二、 統(tǒng)籌規(guī)劃1、安排工序問題2、最短路線或最短時間問題3、排隊等候問題4、集合問題5、貨物調度問題三、 游戲對策（1）必勝策略往往是考慮“如何讓對方輸”，

4、即必勝方行動時如何進行一次適當操作，把必輸狀態(tài)留給對方（2）游戲對策中往往會利用對稱性來解決問題，如桌子上放硬幣問題（輪流在圓桌上放硬幣，到誰放的時候放不下了他就輸了先手方把第一個硬幣用來占領圓桌中心點即可，之后后手方再怎么放，先手方都能在桌上找到一個對稱的空位點可以放置硬幣）四、 邏輯推理解答推理問題常用的方法有：排除法、假設法、反證法一般可以從以下幾方面考慮：1. 選準突破口，分析時綜合幾個條件進行判斷；2. 根據題中條件，在推理過程中，不斷排除不可能的情況，從而得出要求的結論；3. 對可能出現的情況作出假設，然后再根據條件推理，如果得到的結論和條件不矛盾，說明假設正確；4. 遇到比較復雜

5、的推理問題，可以借助圖表進行分析常見題型：去偽存真題：有人說真話有人說假話，有人說真話；或每人說的一部分對，一部分錯注意適當選擇假設等方法幫助解題條件分析題：用列表或作圖的方法，對條件進行歸納整理體育比賽類問題：要注意搞清比賽規(guī)則，特別是積分規(guī)則，對陣方式若是畫對陣關系圖，注意箭頭表勝負，虛線表示平局例如：若是2分賽制，則獲勝隊2分，平局各1分，失敗不得分，那么總得分為“”；而3分賽制時，獲勝隊得3分，平局各得1分，失敗不得分那么此時總分為“”五、 抽屜原理1、最不利原則2、抽屜原理六、 最值問題常用結論：（1）兩數和一定，差越小，積越大（2）當幾個數和一定是，越接近乘積越大（3）兩點之間線段

6、最短（4）在周長一定的封閉圖形中，圓的面積最大；在面積一定的封閉圖形中，圓的周長最小七、 構造論證1、構造往往用于說明“能”，即給出可能情況；論證往往用于說明“否”，即為什么不行2、常見題型：（1）構造或論證：這類題目中通常會以“能否”等詞匯發(fā)問解答時，如果是“能”，就要構造出可行情況；如果是答“不能”，要論證為什么（2）構造與論證：常見于求最值的問題，以求最大值問題，得出最大值后要先論證不能得更大的值了，然后構造最大值對應的可行情況，說明這個最大值可以達到 一、枚舉法例1. 在所有三位數中，各位數字之和不超過4的共有_個二、加乘原理與排列組合例2. 將1、2、3、4、5這五個數字填入下面的五

7、個方格中，使得陰影方格中填入的數大于相鄰方格中的數，共有_種填法例3. 用0、1、2、3、4這五個數字能組成_個沒有重復數字的四位偶數例4. 從19選出7個數字分別填入圖中7個圓圈中，使得每條線段兩端點處所填的數，上面比下面的大，那么符合要求的共_種三、容斥原理例5. 如圖，數一數，圖中共有多少個長方體？四、概率初步例6. 某軍官參加射擊比賽，他的射擊命中率是80%那么他連打3槍，恰好有2槍命中的概率是_例7. 甲、乙兩人玩擲硬幣，出現正面甲得1分，反面乙得1分先得10分者為勝比賽進行一段時間后，甲得9分，乙得6分，那么甲獲勝概率是_五、遞推計數例8. 在一個平面上畫3個三角形、1個圓、1條直

8、線，最多可以把平面分成_個部分例9. 在世界杯的一場小組賽中，巴西隊以7:5擊敗南非隊，如果巴西隊在比賽中從未落后過，那么這場比賽共有_種不同的進球順序六、對應計數例10. （1）中關村一小六年級A班的30名同學投票選舉優(yōu)秀少先隊員，投票采用不記名方式，每人只能投1票且不能投棄權票（誰都不選）如果候選人共3人，那么投票共_種不同的可能（2）如果這30名學生可以投棄權票，那么投票結果共_種不同的可能七、與翻轉、旋轉有關的計數問題例11. 用7種顏色為一個正方體的6個面染色，要求每個面只能用1種顏色，且6個面的顏色互不相同那么共有_種不同的染色方式八、統(tǒng)籌規(guī)劃例12. 北京、上海、杭州三地同時研制

9、成了大型電子計算機若干臺，除本地應用外，北京可以支援外地10臺，上?？梢灾г獾?臺，杭州可以支援外地6臺現在決定給武漢6臺，重慶8臺，深圳6臺若每臺計算機的運費如下表，表中運費單位是“百元”上海、北京和杭州制造的機器完全相同，應該怎樣調運，才能使總的運費最??？最省的運費是_萬元終點起 點 武漢重慶深圳北京7912上海879杭州6108九、游戲對策例13. 2010根火柴，甲、乙輪流取，規(guī)定每次只可以取1、3、4根如果以取完火柴的人為勝，甲先取，那么誰有必勝策略？策略是什么？十、邏輯推理例14. 老師在3個盒子里各放了一個彩色球，讓小明、小亮、小強、小佳四人猜一下各個盒子里放的是什么顏色的球小

10、明說：“1號盒里的是黃球，2號盒里的是黑球，3號盒里的是紅球”小亮說：“1號盒里的是橙球，2號盒里的是黑球，3號盒里的是綠球”小強說：“1號盒里的是紫球，2號盒里的是黃球，3號盒里的是藍球”小佳說：“1號盒里的是橙球，2號盒里的是綠球，3號盒里的是紫球”老師說：“你們中有一人恰好猜對了兩個，其余三人每人猜對一個”那么第三個箱子中放的是_球例15. 在一列國際列車上，有A、B、C、D四位不同國籍的旅客，他們分別穿藍、黑、灰、褐色的大衣，每邊兩個人面對面地坐在同一張桌子上已知：（1）英國人坐B先生左側；（2）A先生穿褐色大衣；（3）穿黑色大衣的坐在德國人右側；（4）D先生的對面坐著美國旅客；（5）

11、俄國旅客穿著灰色大衣那么A、B、C、D分別是哪國人？分別穿什么顏色的衣服？例16. 5支球隊進行單循環(huán)比賽，每兩隊之間比一場，獲勝者得3分，負者0分，平手各得1分最后5支球隊積分各不相同，第三名得了7分，并且和第一名打平請問：這5支球隊的得分從高到低依次是多少？十一、抽屜原理例17. 有一個不透明的魔法口袋，里面裝有大小、形狀完全相同的小球，分為紅、黃、藍、白、黑五種顏色，每種顏色的小球都有足夠多個n個人在口袋里取球，每人隨意取3個，無論怎么取，都一定有5個人取到的球種類完全相同，那么n至少是_十二、最值問題例18. 將1、2、3、4、5、6分別填在正方體的6個表面上，計算具有公共棱的兩個面上

12、的數的乘積，這樣的乘積共有12個，這12個乘積的和最大是_十三、構造論證例19. 把圖中的圓圈任意涂上紅色或藍色問：能否使得每一條直線上的紅圈個數都是奇數？ 例20. 有3堆小石子，每次允許進行如下操作：從每堆中取走同樣數目的小石子，或是將其中的某一石子數是偶數的堆中的一半石子移入另外的一堆開始時，第一堆有1989塊石子，第二堆有989塊石子，第三堆有89塊石子問能否做到：(1)某2堆石子全部取光？(2)3堆中的所有石子都被取走？作業(yè)1. 在所有的三位數中，能夠被9整除，而且三個數字恰好能構成等差數列（可以改變順序，如567、756）的共有_個作業(yè)2. 在40007000內有_個沒有重復數字的

13、5的倍數作業(yè)3. 有甲、乙、丙、丁四人過河，河上有一條小船，每次只能坐兩個人，這樣每次就必須有一人把船劃回來接剩下的人那么四人過河有_方式作業(yè)4. 如圖，圖中只含一個的長方形有_個？作業(yè)5. 一次吃自助餐，有10道菜，每人有4個盤子可以選菜，要求每個盤子只能裝1種菜，但是可以重復選菜（比如某道菜很好吃，我可以把2個盤子都裝這1種菜），那么共有_種選菜方案作業(yè)6. （第六屆高思杯 六年級，參加了高思杯但是當時沒做出來的同學，看看自己現在是否會做了）正方體的八個頂點分別標記為A、B、C、D、E、F、G、H現在用四種顏色給頂點染色，要求有棱相連的兩個頂點的顏色不同，一共有_不同的染色方法（旋轉或翻轉

14、后相同算不同的染法）作業(yè)7. 把23表示成若干個互不相同的自然數之和，那么這些自然數的乘積最大是_作業(yè)8. ：一個新建的5層樓房的一個單元 每層有東西兩套房；各層房號如圖所示，現已有趙、錢、孫、李、周五個人入住一天他們在社區(qū)花園里聊天：趙說：“我家是第3個入住的，第1個入住的就住我對門”錢說：“只有我一家住在最高層”孫說：“我家入住時，我家的同側的上一層和下一層都已經有人入住了”李說：“我家是五家中最后一個入住的，我家樓下那層全空著”周說：“我家住在106號，104號空著，108號也空著”他們說的就是真話，設第1、2、3、4、5家入住的房號的個位數字依次為A、B、C、D、E，那么五位數_ 作業(yè)9. 六