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

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