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

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

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

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

4、的球中有16個(gè)球 的顏色相同，至少要從袋中摸取多少個(gè)球？,【分析】：從最不利的情況考慮，開(kāi)始摸出的 白球和黑球共 15+14=29，繼續(xù)去摸，有摸出 紅、黃、藍(lán)色球個(gè)15個(gè)，這種情況下要保證摸 出的球中有16個(gè)顏色相同，必須再摸一個(gè)。,抽屜原理,15 + 14 + 3 151= 75 （個(gè)）,例題7,某班參加田徑運(yùn)動(dòng)會(huì)各項(xiàng)目的數(shù)統(tǒng)計(jì)如下 參加徑賽項(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,在哥尼斯堡的普萊格爾河上有七座橋，將河中的兩個(gè)島B，與河岸，連接，問(wèn)一個(gè)散步者能否從某一地點(diǎn)出發(fā) ，不重復(fù)的走遍每一座橋，并返回出發(fā)地?,不可能,,圖論方法,某小學(xué)的一次畫(huà)展上展出的畫(huà)中，有16幅不 是六年級(jí)的，有15幅不是五年級(jí)的。并且已知 五、六年級(jí)共有25幅畫(huà)參展，問(wèn)一至四年級(jí)共 有多少幅畫(huà)參展？,練習(xí),【解】： （16+15）- 25 2 = 3,2. 如圖，從 56 的方格中，取出一個(gè)由三個(gè) 方格組成的“L”形，問(wèn)有多少種不同的取法？,【解】： 29+25+37 -（15+13+16）+7=54,3、 從 1， 3， 5，

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