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

1、離散數學中許多有趣的問題By 孫一凡 老師簡介離散數學亦稱組合數學。自古的數學，算術與幾何便分別代表了離散與連續觀念的源頭。兩種思維相互發展，培育了數學世界。但自牛頓開創微積分以後，連續性數學便獨領風騷三百年。今日離散數學的假设干題材，雖可在數論、代數、機率、幾何等學科中發現其身影，但始終是理論深度不明的研讨課題。 本世紀以來 離散的工具與方法，逐漸在各個學科中被發展及运用，而產生出新的焦點及新的科學意識。一些彼此關連的研讨領域，開始匯聚。 特別自三十年代以後，計算科學在理論與實用上都有突破性的發展。這是因為電腦的出現。電腦利用離散的表示處理資訊，離散現象的重要開始被重視。此外，電腦幫人處理大

2、量的有限數及有限結構，跑出了很多新層次的問題需研讨。 離散數學包含了什麼? 包羅了許多學域，比較重要的包括以下幾種： 古典計算問題，包括有限集合上的各類陈列組合問題 以代數、拓樸方法建立組合學體系的研讨 以群論、有限幾何為主要工具的設計理論(Design Theory) 圖形、網路與超圖的理論(Hypergraphs)請修：組合設計初步請修：組合設計初步請修：圖論初步、離散專題請修：圖論初步、離散專題請修：離散數學請修：離散數學離散數學包含了什麼?最正确化、運籌學(Operation Research)與賽局理論(Game Theory)編碼(Coding Theory)與密碼理論(Crypt

3、ography)擬陣(Matroid)、廣義擬陣論(Greedoid)離散與計算幾何學演算法則的設計與分析請修：代數編碼學、密碼學請修：代數編碼學、密碼學請修：演算法請修：演算法離散數學有些什麼應用？ 在應用方面，最大的市場之一是資訊科學，已成為資訊系的必修課程。數位化的產物，如光碟、大哥大、衛星通訊等等都仰賴錯誤糾正碼(Error Correcting Code)設計以添加可靠性；提款卡、簽帳卡等也是密碼學的附產品；另外，DNA的定序問題，選舉權力的分析，生物食物網的平衡，實驗設計的安排，處處可見離散數學應用的例子。討論整數 也可說是組合數學的重要關鍵 整數Z與實數R不同，兩者分別代表了離散

4、觀念與連續觀念。 因此離散數學中，整數的觀念通常相當重要，整數與整數的關係也是如此，可以廣泛的應用在許多事上。正整數 : 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位同學中的每一位都換到他的鄰座上去，能否能辦到？提示當一聲令下，一切

5、同學都換到他們的鄰座時，本来坐 位子的同學會換到本来就坐 的位子，可是 . . . . ：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,

6、 2, 3, 4 7 1 3 1 6 2 44, 8, 1, 6, 5, 3, 2, 7 4 5 2 5 1 3 2Why？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. 假设a1a2 則|a1-a2|= a1-a2 a1a2 則|a1-a2|= a2-a1 4. 假設絕對值都拆掉了，上式會變成如 = (a1-a2)+(a4-a3)+(a6-a5)+(a7-

7、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：整數點只會有以下四種

8、奇偶性： (奇,奇) (偶,偶) (奇,偶) (偶,奇)根據鴿洞原理，5個整數點中必有某兩點的奇偶性一样！ (因為奇偶性總共只需四種，點有五個) 而當兩點(x1, y1), (x2, y2)有一样奇偶性時 x1+ x2 與 y1 + y2都是偶數 即 (x1+x2)/2 與 (y1+y2)/2皆為整數 (x1+x2)/2,(y1+y2)/2)為整數點性質 31. 奇數個奇數的和必為奇數2. 假设假设干個整數a1a2a3的連乘積 是奇數，則其中每個數ai都是奇數動動腦 4設 n 為一奇數。又設 a1,a2, ,an 是1,2, ,n 的恣意一種陈列。求證：(1- a1)(2- a2) (n- a

9、n)必為偶數。假設(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) a1a2an = n (ii) a1+a2+an = 0 求證： n 為 4 的倍數。假设n為奇數，且滿足 a1a2an = n則， a1、a2、an皆為奇數a1+a2+an 即為奇數個奇數的和(=奇數)0且因為a1+a2+an=0，所以a1、a2、an中 奇數

10、必為偶數個，則偶數也必為偶數個， 即a1、a2、an中偶數至少兩個， 所以 a1a2an 連乘積必為4的倍數！動動腦 6某博物館共有25間展覽室，如圖所示，這裡相鄰的展覽室之間都有門相通。參觀者自東北角大門口開始參觀，希望依次不重複地看遍每一間展覽室之後仍回到東北角大門去。請問參觀者有哪幾種路線可以參觀？如圖示，東北角的展覽室為藍色，無論選擇怎樣路線，看展覽的順序依序為藍1-橘1-藍2-橘2-藍3-橘12-藍13(因為藍展覽室有13間，橘展覽室有12間) 然後呢？ 藍13必須接到藍1啊！？矛盾！定理 1任何一個非完全平方數的正整數都有偶數個因數。如20的正因數有：1, 2, 4, 5, 10,

11、 2025的正因數有：1, 5, 25動動腦 7有一百盞燈，陈列成一列，從左至右依次標上 1,2,100 這些號碼。每一盞燈都有一根拉線開關。另外，還有一百個人。最初燈全是關著的，第一個人走過來把號碼為1的倍數的燈的開關拉一下；接著第二個人走過來把號碼為2的倍數的燈的開關拉一下；第三個人走過來把號碼為3的倍數的燈的開關拉一下；如此繼續著，最後那個人走過來把最後那盞燈的開關拉一下。這樣做過之後，請問留下哪些燈是亮著的？號碼為 k 的燈，會不會被第i個人所拉，端看i是不是k的因數，是，則此人拉，不是，則此人不拉！ 所以， 1. 假设 k 有 t 個因數則此盞燈共被拉了t次。 2. 燈本来全都是關的

12、，被拉奇數次的燈是亮的，被 拉偶數次的燈是關的 3. 所以最後亮著的燈為號碼 k 只需奇數個因數， 為完全平方數，即： 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 只需這10盞燈是亮的！動動腦 8在一條環形公路上，n個車站被n段公路連接了起來。車站所在地的海拔高度共有5米和10米兩種。相鄰車站假设海拔高度一样，則他們之間的公路是程度的；假设不同，則他們之間的公路是有坡的。有一個旅遊者開車在這條環形公路上沿順時針方向繞了一圈，發現有坡的公路段數與程度公路段數一樣多。求證：車站的個數 n 是 4 的倍數。因為：有坡的公路段數與程度公路段數一樣多，表示n為偶數，所以n個

13、路段中一半為程度路段、一半為有坡度路段。但是，有坡度路段中，一半為上坡、一半為下坡才回得來啊！，所以，n為4的倍數。12543612345動動腦 9有 n 個數 1, 2, , n，一切的數只能為1或-1。假设 12+23+n-1n+n1=0求證： n 是 4 的倍數。 提示：跟上一題有關係 把這 n 個數 1, 2, , n想成 n 個車站， 海拔10公尺的車站標為1，海拔5公尺的車站標為-1。 如此一來，12假设為1，表示兩車站同為1或同為-1 12假设為-1，則表示兩車站一為1一為-1，也就是 12為1表示該路段為程度路段， 12為-1表示該路段為有坡度路段， 12+23+n-1n+n1

14、 = 0表示兩種路段 數目一样，而有坡度的路段繞一圈後上坡下坡各一半 因此， n 是 4 的倍數。12 , 23 , , n-1n , n1當中 1的個數等於-1的個數，所以 n = 2k假设 12 =1 則 1=2 =1 或 1=2 = -1 表示從1到2符號沒有發生變化假设 12 =-1 則說明符號有發生變化從1開始，最後回到1，說明這一過程中發生了k次符號變化，但1與本身是同號的，所以k也為偶數。動動腦 10一百個人排成一列縱隊。從頭到尾報完數之後，凡報奇數的一概出列，只需報偶數的仍依次留在隊列之中，接著從頭至尾再次報數，凡報奇數者一概出列，留下報偶數者，接著第三次從頭到尾報數，如此進行

15、下去，請問最後留在隊列中的那個人，他在第一次報數時報多少號？提示：第一次留下誰？第二次之後留下誰？ 第三次之後留下誰？第一次留下了：2,4,6,8,10,12,14,16,18,20,第二次留下了：4,8,12,16,20,第三次留下了：8,16,也就是說，擁有2最多的數可以留到越後面，那麼1100中，誰有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與d使