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

離 散 數 學 中 許 多 有 趣 的 問 題By 孫 一 凡 老 師 簡 介 離 散 數 學 亦 稱 組 合 數 學 。 自 古 的 數學 ， 算 術 與 幾 何 便 分 別 代 表 了 離 散 與 連 續 觀念 的 源 頭 。 兩 種 思 維 相 互 發 展 ， 造 就 了 數 學 世 界 。 但 自牛 頓 開 創 微 積 分 以 後 ， 連 續 性 數 學 便 獨 領 風騷 三 百 年 。 今 日 離 散 數 學 的 若 干 題 材 ， 雖 可在 數 論 、 代 數 、 機 率 、 幾 何 等 學 科 中 發 現 其身 影 ， 但 始 終 是 理 論 深 度 不 明 的 研 究 課 題 。 本 世 紀 以 來 離散 的 工 具與方 法 ， 逐漸在 各個學科 中 被發展 及 使 用 ， 而產生 出 新 的 焦點及 新 的 科學意識。 一 些 彼 此關連的 研 究領域 ，開始匯聚 。 特別自 三 十 年 代 以 後 ，計算 科學在 理論與實用 上 都 有 突 破 性 的發展 。這是 因為電腦的 出現。電腦利 用離散 的 表 示處理資訊，離散現象 的 重 要開始 被 重視。 此 外 ，電腦幫人處理大 量 的 有 限數及 有 限結構， 跑 出 了 很 多 新層次 的問題需 研 究 。 離 散 數 學 包 含 了 什 麼 ? 包羅了許多學域 ， 比較重 要 的 包 括 下 列幾種：1.古 典計算問題， 包 括 有 限 集 合 上 的 各類排 列組合問題2.以 代數、 拓樸方 法 建 立組合學體系 的 研 究3.以 群論、 有 限幾何為主 要 工 具 的設計理論(Design Theory)4.圖形 、網路與超圖的 理論(Hypergraphs)請 修 ： 組 合 設 計 初 步請 修 ： 圖 論 初 步 、 離 散 專 題請 修 ： 離 散 數 學 離 散 數 學 包 含 了 什 麼 ?5. 最 佳 化 、運籌學(Operation Research)與賽局 理論(Game Theory)6.編碼(Coding Theory)與密碼理論(Cryptography)7.擬陣(Matroid)、廣義擬陣論(Greedoid)8.離散與計算幾何學9. 演 算 法則的設計與分 析請 修 ： 代 數 編 碼 學 、 密 碼 學請 修 ： 演 算 法 離 散 數 學 有 些 什 麼 應 用 ？ 在應用 方 面 ， 最 大 的 市場之 一 是資訊科學，已 成為資訊系 的 必 修課程 。數位 化 的產物 ，如 光 碟 、 大 哥 大 、衛星 通訊等 等 都 仰賴錯誤糾正碼(Error Correcting Code)設計以 增加 可 靠 性 ； 提 款 卡 、簽帳卡 等 也 是 密碼學的附產品 ； 另 外 ， 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, 4 7 1 3 1 6 2 4 4, 8, 1, 6, 5, 3, 2, 7 4 5 2 5 1 3 2 Why？ 1. a1+ a2+ a3+ + a8 = 1+ + 8 = 36 2. 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-a2 a1 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, 20 25的 正 因 數 有 ： 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 543 61 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最 多 的 數 可 以 留 到 越 後 面 ，那 麼 1100中 ， 誰 有 2的 次 數 最 多 呢 ？ 答 案 是 ： 64 = 2 6 定 理 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與 d使 得 a2+b2+c2 = d2。 試 想 ： 若 a,b,c皆 為 奇 數 ， 則 a2、 b2與 c2皆 為 除 8餘 1， 也 就 是 合 起 來 除 8餘 3， 此 時 d為 奇 數 或 偶 數 皆 不 合 。 若 a,b 為 奇 數 ， c為 偶 數 ， 則 左 式 為 (8m+2)+(4k)=4(2m+k)+2為 偶 數 ， 故 d不 能 是 奇 數 ， 但 是 若 d為 偶 數 則 右 式 為 4的 倍 數 ， 而 左 式 除 4餘 2， 也 不 合 ， 也 就 是 說 ， a2+b2+c2 = d2要 成 立 的 話 ， a,b不 能 全 為 奇 數 。ab為 偶 數 若 且 唯 若 存 在 正 整 數 c與 d使 得 a2+b2+c2 = d2。 先 預 祝 大 家 聖 誕 快 樂