《集合論、組合論方法.ppt》由會員分享，可在線閱讀，更多相關(guān)《集合論、組合論方法.ppt（15頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、專題8、集合論、組合論方法,集合法 對應(yīng)法,計數(shù)法（加法原理、容斥原理、乘法原理） 抽屜原理 圖論方法,組合論方法：,集合論方法：,容斥原理,設(shè)全集的子集A的基數(shù)用|A|表示,交集AB 用AB表示,則,抽屜原理,如果將n+1件物體放到n個抽屜里去，那么至少有一 個抽屜里放的物體不少于兩件。,抽屜原理3,抽屜原理2,抽屜原理1,如果將多于mn件物體任意放到n個抽屜中去，那么至少有一個抽屜里放的物體不少于m+1件。,如果把無限個物體任意放到有限個抽屜中去，那么至少有一個抽屜中物體的個數(shù)是無限的。,從1 到500 中的整數(shù)中，不能被3整除，不 能被5整除的數(shù)有多少個？,【解】： 5003=166（余

2、2） 5005=100 50015=33（余5） 500-166-100+33=267,一、集合論方法,,,,A,B,33,133,67,例題 1,集合論方法,例2,在 88 的方格棋盤上取兩個小方格，這兩個小 方格構(gòu)成的圖形如下圖1所示，它們有一個公共點(diǎn). 問 有多少種不同的取法？,解： 772=98(種),,,圖1,對應(yīng)法,例題3,在50 名女學(xué)生中，穿的都是紅裙子或者黃 裙子、白上衣或者花上衣. 已知：穿黃裙子的有31人 穿白上衣的有18人，穿紅裙子和花上衣的有14人， 問穿黃裙子和白上衣的有多少人？,因此，穿黃裙子和白上衣的13。,,32,5,19,18,13,例題4

3、,在邊長為 1 的正三角形中（包括邊界上） 任意放入5個點(diǎn)，求證：這5個點(diǎn)中必須有兩點(diǎn)， 它們之間的距離不大于 0.5 ？,【證明】: 依次連接這個三角形三邊的中點(diǎn)，把邊長為1 的三角形分成4個邊長為0.5 的三角形 .把5個點(diǎn)放入三角形中，因?yàn)?54，所以至少有一個三角形內(nèi)包括它的周邊有兩個或兩個以上的點(diǎn)，這樣的兩個點(diǎn)之間的距離不會超過0.5 。,,,,,抽屜原理,例題5,在圖中所示的 44 的方格中，有多少 個正方形？,二、組合論方法,,42 + 32 + 22 + 12 = 30 （個）,加法原理,例題6,袋中有25個紅球，24個藍(lán)球，23個黃球，15 個白球及14個黑球，如果要確保摸出

4、的球中有16個球 的顏色相同，至少要從袋中摸取多少個球？,【分析】：從最不利的情況考慮，開始摸出的 白球和黑球共 15+14=29，繼續(xù)去摸，有摸出 紅、黃、藍(lán)色球個15個，這種情況下要保證摸 出的球中有16個顏色相同，必須再摸一個。,抽屜原理,15 + 14 + 3 151= 75 （個）,例題7,某班參加田徑運(yùn)動會各項(xiàng)目的數(shù)統(tǒng)計如下 參加徑賽項(xiàng)目的有 15人，參加跳類項(xiàng)目的有 13人， 參加投擲類項(xiàng)目的有 14人； 既參加徑賽、又參加跳類項(xiàng)目的有 4人， 既參加跳類、又參加投擲類項(xiàng)目的有 5人， 既參加徑賽、又參加投擲類項(xiàng)目的有 6人; 三類項(xiàng)目都參加的有2人.,【解】： (151314)

5、 - (456) + 2 = 29 （人）,容斥原理,例8,在哥尼斯堡的普萊格爾河上有七座橋，將河中的兩個島B，與河岸，連接，問一個散步者能否從某一地點(diǎn)出發(fā) ，不重復(fù)的走遍每一座橋，并返回出發(fā)地?,不可能,,圖論方法,某小學(xué)的一次畫展上展出的畫中，有16幅不 是六年級的，有15幅不是五年級的。并且已知 五、六年級共有25幅畫參展，問一至四年級共 有多少幅畫參展？,練習(xí),【解】： （16+15）- 25 2 = 3,2. 如圖，從 56 的方格中，取出一個由三個 方格組成的“L”形，問有多少種不同的取法？,【解】： 29+25+37 -（15+13+16）+7=54,3、 從 1， 3， 5，

6、，29， 31 這16個奇數(shù)中，任取9個數(shù)，證明：其中一定有兩個數(shù)之和是 32.,證明： 抽屜原理,4. 已知三位數(shù)各位上數(shù)字的和等于10， 這樣的三位數(shù)一共有多少個？,解： 百位上為 1 時有 10 個 百位上為 2 時有 9 個 百位上為 3 時有 8 個 ................. 百位上為 9 時有 2 個 10 + 9 + 8 + ... + 3 + 2 = 54,5. 1818的小方格棋盤中，包含99個小方 格的正方形有多少個？ 6. 某年級有202人參加考試，滿分100分，且 得分都是整數(shù)，總得分為10101分，求證：至 少有3人得分相同。 7. 10個蘋果，每天至少吃1個，直到吃完，問 有多少種不同的吃蘋果的方案？,抽屜原理,1010=100,29 = 512,