組合數(shù)學(xué)_16028.ppt

組合數(shù)學(xué)初步 第十章鴿籠原理第十一章排列與組合第十二章生成函數(shù)與遞推關(guān)系 組合數(shù)學(xué) 組合論 組合數(shù)學(xué) 組合論 應(yīng)用數(shù)學(xué)學(xué)科 對于算法研究變得日益重要 計(jì)算機(jī)算法分類 數(shù)值計(jì)算 方程組求解 積分計(jì)算非數(shù)值計(jì)算 搜索 排序 組合優(yōu)化 主要是組合算法 設(shè)計(jì)和分析組合算法的基礎(chǔ)是組合數(shù)學(xué) 組合數(shù)學(xué)的四個(gè)方面 判定所提出問題的解是否存在的存在性問題確定有解問題其不同解的個(gè)數(shù)的計(jì)數(shù)問題對可解問題去把解構(gòu)造出來的構(gòu)造性算法從問題的多種構(gòu)造性算法中擇優(yōu)改進(jìn)的優(yōu)化問題 講授內(nèi)容 組合數(shù)學(xué)中的存在性問題和計(jì)數(shù)問題 組合數(shù)學(xué) 經(jīng)典教材 組合數(shù)學(xué) 第3版 盧開澄 盧華明著 清華大學(xué)出版社 有課件 可拷貝 組合數(shù)學(xué) 英文版 第3版 美 RichardA Brualdi 譯者 馮舜璽 羅平 裴偉東 校 盧開澄 馮舜璽 PrenticeHall 機(jī)械工業(yè)出版社 組合數(shù)學(xué) 一 組合數(shù)學(xué)的歷史和發(fā)展原因二 組合數(shù)學(xué)兩類一般性問題三 組合學(xué)另外兩種問題四 組合數(shù)學(xué)的定義 一 組合數(shù)學(xué)的歷史和發(fā)展原因 1 組合數(shù)學(xué)的歷史淵源扎根于數(shù)學(xué)娛樂和游戲之中 2 組合數(shù)學(xué)的歷史和發(fā)展原因1 計(jì)算機(jī)的發(fā)展 程序的基礎(chǔ)往往是求解問題的組合學(xué)算法 2 組合數(shù)學(xué)對于過去很少與數(shù)學(xué)正式接觸的學(xué)科的適用性 二 組合數(shù)學(xué)兩類一般性問題 組合數(shù)學(xué)涉及將一個(gè)集合的物體排列成滿足一些指定規(guī)則的格式 1 排列的存在性 排列在什么樣的 充分和必要 條件下能夠?qū)崿F(xiàn) 2 排列的計(jì)數(shù)和分類 如果一個(gè)排列是可能的 那么就會存在多種方法實(shí)現(xiàn)它 此時(shí) 就可以計(jì)數(shù)并將它們分類 組合學(xué)問題形式 能否排列 存在一個(gè) 嗎 能用多少方法 計(jì)算 的數(shù)目 三 組合學(xué)另外兩種問題 研究一個(gè)已知的排列構(gòu)造一個(gè)最優(yōu)的排列 四 組合數(shù)學(xué)的定義 組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在 計(jì)數(shù) 分析和優(yōu)化等問題的一門學(xué)科 第十章鴿籠原理 10 1鴿籠原理的簡單形式10 2鴿籠原理的加強(qiáng)形式 10 1鴿籠原理的簡單形式 1 問題的引入實(shí)例 某次會議有n位代表參加 每位代表認(rèn)識其他代表中某些人 則至少有兩個(gè)人認(rèn)識的人數(shù)是一樣的 10 1鴿籠原理的簡單形式 2 鴿籠定理10 1n 1只鴿子飛回n個(gè)籠子 至少有一個(gè)鴿籠含有不少于2只鴿子 證明方法 反證 例 367人中至少有 人的生日相同 例 10雙手套中任取11只 其中至少有兩只是完整配對的 3 鴿籠的擴(kuò)展 抽象 定理10 2s s 1 個(gè)元素分成t個(gè)組 那么必存在一個(gè)組至少含有 s t 這里 為 上整數(shù) 記號 個(gè)元素 證明方法 反證法 證明 若每個(gè)組至多含有 s t 1 元素 則t個(gè)組共有元素t s t 1 因?yàn)閟 t s t s t 1 所以有t s t 1 s 這就導(dǎo)致矛盾 所以必存在一個(gè)組至少含有 s t 個(gè)元素 4 實(shí)例1 例10 1設(shè)f是D到R的函數(shù) 這里 D R 令i D R 則D中存在i個(gè)元素d1 d2 di 使得f d1 f d2 f di 證明方法 此問題相當(dāng)于定理10 2 把 D 個(gè)元素分到 R 個(gè)組中去 證明 在這 R 個(gè)組中有一個(gè)組至少含有i D R 個(gè)元素 在同一組中對應(yīng)的函數(shù)值是相等的 所以在D中至少存在i個(gè)元素d1 d2 di 使得f d1 f d2 f di 2 例10 2在n 1個(gè)小于或等于2n的互不相等的正整數(shù)中 必存在兩個(gè)互質(zhì)的數(shù) 證明 把1 2 2n這2n個(gè)數(shù)分成n個(gè)組 1 2 3 4 2n 1 2n 則問題歸結(jié)為從n個(gè)組中取n 1個(gè)數(shù) 由定理10 1知 至少有2個(gè)數(shù)取自同一組 由于這兩個(gè)數(shù)是相鄰的正整數(shù) 故互質(zhì) 3 例10 31 2 2n中任取n 1個(gè)互不相同的數(shù)中 必存在兩個(gè)數(shù) 其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù) 證明 因?yàn)槿魏握麛?shù)n可以表示成n 2a b 這里a 0 1 2 且b為奇數(shù) 設(shè)取出的n 1個(gè)數(shù)為k1 k2 kn 1 則ki 2ai bi 由于b1 b2 bn 1是奇數(shù) 共有n 1個(gè) 而在 1 2 2n 中只有n個(gè)不同的奇數(shù) 所以必存在i j 使得bi bj 不妨設(shè)ki kj 則有ki kj 2ai aj為正整數(shù) 因此ki是kj的倍數(shù) 4 例10 4一個(gè)國際象棋選手為參加國際比賽 突擊訓(xùn)練77天 要求每天至少下一盤棋 每周至多下12盤棋 證明 無論如何安排總可以使他在這77天里有連續(xù)幾天共下21盤棋 證明 用ai表示從第1天到第i天下棋的總盤數(shù) i 1 2 77 由于規(guī)定每天至少下一盤棋 每周至多下12盤棋 所以1 a1 a2 a77 12 77 7 132構(gòu)造新序列 a1 21 a2 21 a77 21則有這樣的序列 a1 a2 a77 a1 21 a2 21 a77 21共有154個(gè) 但每個(gè)不超過153 所以必存在i j j i 使得ai aj 21 則有ai aj 21 即在j 1 j 2 j i j 的連續(xù)i j天中下了21盤棋 學(xué)生思考題 證明對于k 1 2 21存在連續(xù)若干天 在此期間國際象棋大師將恰好下完k局棋 k 21為上題處理的情況 能否推斷 存在連續(xù)若干天 在此期間國際象棋大師將恰好下完22局棋 5 中國余數(shù)定理令m和n為二互素的正整數(shù) 并令a和b為兩整數(shù) 且0 a m 1以及0 b n 1 于是 存在一個(gè)正整數(shù)x 使得x除以m的余數(shù)為a 并且x除以n的余數(shù)為b 即x可以寫成x pm a的同時(shí)又可以寫成x qn b的形式 這里 p和q是兩個(gè)整數(shù) 證明 考慮n個(gè)整數(shù)a m a 2m a n 1 m a 這些整數(shù)中的每一個(gè)除以m都余a 假設(shè)其中的兩個(gè)除以n有相同的余數(shù)r 令這兩個(gè)數(shù)為im a和jm a 其中0 i j n 1 因此 存在兩整數(shù)qi和qj 使得im a qin r及jm a qjn r 則有 j i m qj qi n 所以n是 j i m的一個(gè)因子 由于n與m沒有除1以外的公因子 因此n是j i的一個(gè)因子 然而 0 i j n 1意味著0 j i n 1 也就是說n不可能是j i的因子 該矛盾產(chǎn)生于我們的假設(shè) a m a 2m a n 1 m a中有兩個(gè)除以n有相同的余數(shù) 因此 這n個(gè)數(shù)中每個(gè)除以n有不同的余數(shù) 根據(jù)鴿巢原理 n個(gè)整數(shù)0 1 2 n 1中每一個(gè)作為余數(shù)都要出現(xiàn) 特別是數(shù)b也是如此 令p為整數(shù) 滿足0 p n 1 且使數(shù)x pm a除以n余數(shù)為b 則對于某個(gè)適當(dāng)?shù)膓 x qn b 因此 x pm a且x qn b 從而x具有所要求的性質(zhì) 學(xué)生思考題 舉例證明 當(dāng)m和n不互素時(shí) 中國余數(shù)定理的結(jié)論未必成立 解題要點(diǎn) 確定哪些對象為 鴿子 哪些對象為 鴿籠 練習(xí) 10 2鴿籠原理的加強(qiáng)形式 1定理10 3設(shè)q1 q2 qn都是正整數(shù) 若把q1 q2 qn n 1個(gè)元素分成n個(gè)組 則必然發(fā)生 或者第一組中至少有q1個(gè)元素 或者第二組中至少有q2個(gè)元素 或者第n組中至少有qn個(gè)元素 證明方法 反證法 證明 若結(jié)論不成立 則對于i 1 2 n 第i組中至多有qi 1個(gè)元素 則n個(gè)組的元素個(gè)數(shù)的總和不超過q1 q2 qn n個(gè) 這就導(dǎo)致矛盾 2推論1 推論10 1若將n r 1 1個(gè)元素分成n個(gè)組 則至少有一個(gè)組含有r個(gè)或更多的元素 這里n r皆為正整數(shù) 2 推論10 2若n個(gè)正整數(shù)m1 m2 mn的平均數(shù)滿足不等式 則m1 m2 mn中至少有一個(gè)不小于r 3例題1 例10 5兩個(gè)同心圓盤的每個(gè)圓周均分為200段 從大盤上任選100段涂上紅色 其余涂上藍(lán)色 而在小盤的每個(gè)小段上任意涂上紅色或藍(lán)色 證明 在旋轉(zhuǎn)小盤時(shí)可以找到某個(gè)位置 使得小盤上至少有100個(gè)小段與大盤上對應(yīng)段顏色相同 證明 固定大盤 對小盤上任一段 在它旋轉(zhuǎn)過程中 可有200個(gè)可能旋轉(zhuǎn)位置 與大盤上的所有段構(gòu)成200種顏色組合 其中同色的有100組 因小盤上共有200段 故小盤上的所有段在旋轉(zhuǎn)一周后 與大盤對應(yīng)段構(gòu)成的同色組共有20000個(gè) 而旋轉(zhuǎn)一周后 共可轉(zhuǎn)去200段 設(shè)i段的同色組為mi I 1 2 200 而總的同色組就是m1 m2 m200 20000 因此200個(gè)整數(shù)m1 m2 m200的平均數(shù)滿足不等式 20000 200 100 100 1 所以 由推論10 2 某個(gè)位置 使得小盤上至少有100個(gè)小段與大盤上對應(yīng)段顏色相同 習(xí)題解析 鴿籠原理用于判斷是否存在滿足鴿籠原理?xiàng)l件的對象 若鴿籠原理的條件成立 則存在滿足條件的對象 運(yùn)用鴿籠原理時(shí)必須確定哪些對象相當(dāng)于鴿子 而哪些對象相當(dāng)于鴿籠 鴿籠原理形式 設(shè)函數(shù)f是從有限集X到有限集Y的映射 且 X Y 則必存在x1 x2 X x1 x2 滿足f x1 f x2 鴿籠原理形式例題1 20個(gè)處理器連成網(wǎng)絡(luò) 證明至少有兩個(gè)處理器與相同數(shù)目的處理器直接相連 解題分析 20個(gè)處理器編號分別為1 2 3 20 定義域X 1 2 3 20 ai表示與第i個(gè)處理器直接相連的處理器的數(shù)目 f X 證明 對于某兩個(gè)i j i j ai aj 解 X 1 2 3 20 Y 0 1 2 19 0和19不能同時(shí)作為函數(shù)值存在 即不存在兩個(gè)i j i j ai 0 aj 19 所以 X 20 Y 20 根據(jù)鴿籠原理形式1 命題成立 2 列表中有80件物品 每個(gè)物品的屬性為 可用 或 不可用 共有45個(gè) 可用 的物品 證明至少有兩件可用物品的編號差恰為9 解題分析 ai表示第i個(gè)可用物品的編號 證明 對于某兩個(gè)i j i j ai aj 9 證明 考慮下列兩組數(shù)字 a1 a2 a45a1 9 a2 9 a45 9這兩組共90個(gè)數(shù)字 取值范圍為1 89 因?yàn)榈谝唤M數(shù)字兩兩不同 第二組數(shù)字也是兩兩不同 所以必存在兩個(gè)i j i j ai aj 9 習(xí)題解析 10 1在邊長為2的正三角形中任意放置5個(gè)點(diǎn) 證明至少有兩個(gè)點(diǎn)之間的距離不大于1 解題要點(diǎn) 確定鴿子和鴿籠 將三角形分成邊長為1的4個(gè)正三角形 10 4將一個(gè)圓盤分為36段 將1 2 36這36個(gè)數(shù)字任意標(biāo)在每一段上 使得每一段恰有一個(gè)數(shù)字 證明 必存在相繼的3段 它們的數(shù)字之和不小于56 證明 設(shè)36個(gè)小扇形分別為a1 a2 a36 ai中放的數(shù)為xi i 1 2 36 1 xi 36 且當(dāng)時(shí)i j xi xj 將36個(gè)小扇形合并成12個(gè)大扇形 A1 a1a2a3 A2 a4a5a6 A12 a34a35a36 并設(shè)Aj中3數(shù)之和為yj j 1 2 12 則 將18 37個(gè)元素分配給12個(gè)扇形 由鴿巢原理 至少存在一個(gè)扇形 分配給它的元素個(gè)數(shù)至少是 18 37 12 56 所以命題成立 例設(shè)a1 a2 a3為任意 個(gè)整數(shù) b1 b2 b3為a1 a2 a3的任一排列 則a1 b1 a2 b2 a3 b3中至少有一個(gè)是偶數(shù) 證明 由鴿巢原理 a1 a2 a3為任意 個(gè)整數(shù) 設(shè)這 個(gè)數(shù)被 除的余數(shù)為xxy 于是b1 b2 b3中被 除的余數(shù)有 個(gè)x 一個(gè)y 這樣a1 b1 a2 b2 a3 b3被 除的余數(shù)必