离散数学中许多有趣的问题.ppt

離散數學中許多有趣的問題 By孫一凡老師 簡介 離散數學 亦稱 組合數學 自古的數學 算術與幾何便分別代表了離散與連續觀念的源頭 兩種思維相互發展 造就了數學世界 但自牛頓開創微積分以後 連續性數學便獨領風騷三百年 今日離散數學的若干題材 雖可在數論 代數 機率 幾何等學科中發現其身影 但始終是理論深度不明的研究課題 本世紀以來 離散的工具與方法 逐漸在各個學科中被發展及使用 而產生出新的焦點及新的科學意識 一些彼此關連的研究領域 開始匯聚 特別自三十年代以後 計算科學在理論與實用上都有突破性的發展 這是因為電腦的出現 電腦利用離散的表示處理資訊 離散現象的重要開始被重視 此外 電腦幫人處理大量的有限數及有限結構 跑出了很多新層次的問題需研究 離散數學 包含了什麼 包羅了許多學域 比較重要的包括下列幾種 古典計算問題 包括有限集合上的各類排列組合問題以代數 拓樸方法建立組合學體系的研究以群論 有限幾何為主要工具的設計理論 DesignTheory 圖形 網路與超圖的理論 Hypergraphs 請修 組合設計初步 請修 圖論初步 離散專題 請修 離散數學 離散數學 包含了什麼 最佳化 運籌學 OperationResearch 與賽局理論 GameTheory 編碼 CodingTheory 與密碼理論 Cryptography 擬陣 Matroid 廣義擬陣論 Greedoid 離散與計算幾何學演算法則的設計與分析 請修 代數編碼學 密碼學 請修 演算法 離散數學有些什麼應用 在應用方面 最大的市場之一是資訊科學 已成為資訊系的必修課程 數位化的產物 如光碟 大哥大 衛星通訊等等都仰賴錯誤糾正碼 ErrorCorrectingCode 設計以增加可靠性 提款卡 簽帳卡等也是密碼學的附產品 另外 DNA的定序問題 選舉權力的分析 生物食物網的平衡 實驗設計的安排 處處可見離散數學應用的例子 討論整數也可說是組合數學的重要關鍵 整數 Z 與實數 R 不同 兩者分別代表了離散觀念與連續觀念 因此離散數學中 整數的觀念通常相當重要 整數與整數的關係也是如此 可以廣泛的應用在許多事上 正整數 1 2 3 4 5 6 零 0負整數 1 2 3 4 單數 奇數 1 3 5 雙數 偶數 0 2 4 6 先看一些整數的性質 來熱熱身 性質1 奇數 odd 被2除餘1的數字任何奇數都可表為2n 1的形式偶數 even 可被2整除的數字任何偶數都可表為2n的形式 動動腦1某班49位同學 坐成七行七列 每個座位的前後左右稱做它的鄰座 要同時讓這49位同學中的每一位都換到他的鄰座上去 是否能辦到 提示 當一聲令下 所有同學都換到他們的鄰座時 原本坐位子的同學會換到原本就坐的位子 可是 24個 25個 所以 不可能 性質2 奇數 奇數 偶數偶數 偶數 偶數奇數 偶數 奇數奇數 奇數 偶數偶數 偶數 偶數奇數 偶數 奇數 動動腦2設a1 a2 a3 a8是1 2 3 8的一種任意排列 如 1 8 7 6 5 2 3 4 令b1 a1 a2 b2 a3 a4 b4 a7 a8 c1 b1 b2 c2 b3 b4 c1 c2 這樣一直做下去 最後得到的整數 一定會為偶數 例如 1 8 7 6 5 2 3 47131624 4 8 1 6 5 3 2 74525132 Why 1 a1 a2 a3 a8 1 8 362 b1 a1 a2 b2 a3 a4 b3 a5 a6 b4 a7 a8 則b1 b2 b3 b4 a1 a2 a3 a4 a5 a6 a7 a8 如何將絕對值拆掉 3 若a1 a2則 a1 a2 a1 a2a1 a2則 a1 a2 a2 a1 4 假設絕對值都拆掉了 上式會變成如 a1 a2 a4 a3 a6 a5 a7 a8 a1 a4 a6 a7 a2 a3 a5 a8 之類的 總之 有4個數字在前括號中 另外4個數字在後括號中 5 a1 a4 a6 a7 a2 a3 a5 a8 36因為A B 偶數 則A B必同為偶數或同為奇數 所以A B必為奇 奇或偶 偶 偶數6 如此一來 上一列的總和為偶數 下一列的總和也必為偶數 則最後的 必為偶數 動動腦3在平面上任意標出五個整數座標的點 證明 其中必至少有兩個點 它們的連線的中點也是整數座標的點 提示1 x1 y1 與 x2 y2 的連線中點座標為 x1 x2 2 y1 y2 2 提示2 整數點只會有以下四種奇偶性 奇 奇 偶 偶 奇 偶 偶 奇 根據鴿洞原理 5個整數點中必有某兩點的奇偶性相同 因為奇偶性總共只有四種 點有五個 而當兩點 x1 y1 x2 y2 有相同奇偶性時x1 x2與y1 y2都是偶數即 x1 x2 2與 y1 y2 2皆為整數 x1 x2 2 y1 y2 2 為整數點 性質3 1 奇數個奇數的和必為奇數2 如果若干個整數a1a2a3 的連乘積是奇數 則其中每個數ai都是奇數 動動腦4設n為一奇數 又設a1 a2 an是1 2 n的任意一種排列 求證 1 a1 2 a2 n an 必為偶數 假設 1 a1 2 a2 n an 為奇數則1 a1 2 a2 n an都是奇數 1 a1 2 a2 n an 1 2 n a1 a2 an 1 2 n 1 2 n 0 產生矛盾 動動腦5n個整數a1 a2 an滿足以下等式 i a1a2 an n ii a1 a2 an 0求證 n為4的倍數 若n為奇數 且滿足a1a2 an n則 a1 a2 an皆為奇數a1 a2 an即為奇數個奇數的和 奇數 0 且因為a1 a2 an 0 所以a1 a2 an中奇數必為偶數個 則偶數也必為偶數個 即a1 a2 an中偶數至少兩個 所以a1a2 an連乘積必為4的倍數 動動腦6某博物館共有25間展覽室 如圖所示 這裡相鄰的展覽室之間都有門相通 參觀者自東北角大門口開始參觀 希望依次不重複地看遍每一間展覽室之後仍回到東北角大門去 請問參觀者有哪幾種路線可以參觀 如圖示 東北角的展覽室為藍色 無論選擇怎樣路線 看展覽的順序依序為藍1 橘1 藍2 橘2 藍3 橘12 藍13 因為藍展覽室有13間 橘展覽室有12間 然後呢 藍13必須接到藍1啊 矛盾 定理1 任何一個非完全平方數的正整數都有偶數個因數 如20的正因數有 1 2 4 5 10 2025的正因數有 1 5 25 動動腦7有一百盞燈 排列成一列 從左至右依次標上1 2 100這些號碼 每一盞燈都有一根拉線開關 另外 還有一百個人 最初燈全是關著的 第一個人走過來把號碼為1的倍數的燈的開關拉一下 接著第二個人走過來把號碼為2的倍數的燈的開關拉一下 第三個人走過來把號碼為3的倍數的燈的開關拉一下 如此繼續著 最後那個人走過來把最後那盞燈的開關拉一下 這樣做過之後 請問留下哪些燈是亮著的 號碼為k的燈 會不會被第i個人所拉 端看i是不是k的因數 是 則此人拉 不是 則此人不拉 所以 1 如果k有t個因數則此盞燈共被拉了t次 2 燈原本全都是關的 被拉奇數次的燈是亮的 被拉偶數次的燈是關的3 所以最後亮著的燈為號碼k只有奇數個因數 為完全平方數 即 1 4 9 16 25 36 49 64 81 100只有這10盞燈是亮的 動動腦8在一條環形公路上 n個車站被n段公路連接了起來 車站所在地的海拔高度共有5米和10米兩種 相鄰車站若海拔高度相同 則他們之間的公路是水平的 若不同 則他們之間的公路是有坡的 有一個旅遊者開車在這條環形公路上沿順時針方向繞了一圈 發現有坡的公路段數與水平公路段數一樣多 求證 車站的個數n是4的倍數 因為 有坡的公路段數與水平公路段數一樣多 表示n為偶數 所以n個路段中一半為水平路段 一半為有坡度路段 但是 有坡度路段中 一半為上坡 一半為下坡 才回得來啊 所以 n為4的倍數 1 2 5 4 3 6 1 2 3 4 5 動動腦9有n個數 1 2 n 所有的數只能為1或 1 如果 1 2 2 3 n 1 n n 1 0求證 n是4的倍數 提示 跟上一題有關係 把這n個數 1 2 n想成n個車站 海拔10公尺的車站標為1 海拔5公尺的車站標為 1 如此一來 1 2若為1 表示兩車站同為1或同為 1 1 2若為 1 則表示兩車站一為1一為 1 也就是 1 2為1表示該路段為水平路段 1 2為 1表示該路段為有坡度路段 1 2 2 3 n 1 n n 1 0表示兩種路段數目相同 而有坡度的路段繞一圈後上坡下坡各一半 因此 n是4的倍數 1 2 2 3 n 1 n n 1當中1的個數等於 1的個數 所以n 2k如果 1 2 1則 1 2 1或 1 2 1表示從 1到 2符號沒有發生變化如果 1 2 1則說明符號有發生變化從 1開始 最後回到 1 說明這一過程中發生了k次符號變化 但 1與本身是同號的 所以k也為偶數 動動腦10一百個人排成一列縱隊 從頭到尾報完數之後 凡報奇數的一律出列 只有報偶數的仍依次留在隊列之中 接著從頭至尾再次報數 凡報奇數者一律出列 留下報偶數者 接著第三次從頭到尾報數 如此進行下去 請問最後留在隊列中的那個人 他在第一次報數時報多少號 提示 第一次留下誰 第二次之後留下誰 第三次之後留下誰 第一次留下了 2 4 6 8 10 12 14 16 18 20 第二次留下了 4 8 12 16 20 第三次留下了 8 16 也就是說 擁有2最多的數可以留到越後面 那麼1 100中 誰有2的次數最多呢 答案是 64 26 定理2 偶數的平方可以被4整除 奇數的平方被8除 餘數為1 因為 2k 2 4k2 2h 1 2 4h2 4h 1 4h h 1 1 h與h 1中必有一個為偶數 所以4h h 1 1 8m 1 動動腦11求證 x2 1 8yn沒有整數解 若x是偶數明顯有問題 若x是奇數 則x2被8除餘1所以x2 1被8除餘2 但是右式為8的倍數 動動腦12求證 正整數a與b ab為偶數若且唯若存在正整數c