资源描述
離散數學中許多有趣問題By 孫一凡 老師第1页簡介離散數學亦稱組合數學。自古數學，算術與幾何便分別代表了離散與連續觀念源頭。兩種思維相互發展，造就了數學世界。但自牛頓開創微積分以後，連續性數學便獨領風騷三百年。今日離散數學若干題材，雖可在數論、代數、機率、幾何等學科中發現其身影，但始終是理論深度不明研究課題。第2页本世紀以來 離散工具與方法，逐漸在各個學科中被發展及使用，而產生出新焦點及新科學意識。一些彼此關連研究領域，開始匯聚。特別自三十年代以後，計算科學在理論與實用上都有突破性發展。這是因為電腦出現。電腦利用離散表示處理資訊，離散現象主要開始被重視。另外，電腦幫人處理大量有限數及有限結構，跑出了很多新層次問題需研究。第3页離散數學包含了什麼?包羅了許多學域，比較主要包含以下幾種：1.古典計算問題，包含有限集合上各類排列組合問題2.以代數、拓樸方法建立組合學體系研究3.以群論、有限幾何為主要工具設計理論(Design Theory)4.圖形、網路與超圖理論(Hypergraphs)請修：組合設計初步請修：組合設計初步請修：圖論初步、離散專題請修：圖論初步、離散專題請修：離散數學請修：離散數學第4页離散數學包含了什麼?5.最正确化、運籌學(Operation Research)與賽局理論(Game Theory)6.編碼(Coding Theory)與密碼理論(Cryptography)7.擬陣(Matroid)、廣義擬陣論(Greedoid)8.離散與計算幾何學9.演算法則設計與分析請修：代數編碼學、密碼學請修：代數編碼學、密碼學請修：演算法請修：演算法第5页離散數學有些什麼應用？在應用方面，最大市場之一是資訊科學，已成為資訊系必修課程。數位化產物，如光碟、大哥大、衛星通訊等等都仰賴錯誤糾正碼(Error Correcting Code)設計以增加可靠性；提款卡、簽帳卡等也是密碼學附產品；另外，DNA定序問題，選舉權力分析，生物食物網平衡，實驗設計安排，處處可見離散數學應用例子。第6页討論整數 也可說是組合數學主要關鍵整數（Z）與實數（R）不一样，兩者分別代表了離散觀念與連續觀念。所以離散數學中，整數觀念通常相當主要，整數與整數關係也是如此，能够廣泛應用在許多事上。第7页正整數:1,2,3,4,5,6,零 :0負整數:-1,-2,-3,-4,單數(奇數):1,3,5,雙數(偶數):0,2,4,6,先看一些整數性質 來熱熱身！第8页性質 1:奇數：(odd)被2除餘1數字 任何奇數都可表為 2n+1 形式偶數：(even)可被2整除數字 任何偶數都可表為 2n 形式第9页動動腦 1某班49位同學，坐成七行七列。每個座位前後左右稱做它鄰座。要同時讓這49位同學中每一位都換到他鄰座上去，是否能辦到？提醒第10页當一聲令下，全部同學都換到他們鄰座時，原本坐 位子同學會換到原本就坐 位子，可是.：24個 ：25個 所以，不可能！不可能！第11页性質 2:奇數+奇數=偶數偶數+偶數=偶數奇數+偶數=奇數奇數-奇數=偶數偶數-偶數=偶數奇數-偶數=奇數第12页動動腦 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|這樣一直做下去，最後得到整數一定會為偶數。第13页比如：1,8,7,6,5,2,3,4 7 1 3 1 6 2 44,8,1,6,5,3,2,7 4 5 2 5 1 3 2Why？第14页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 第15页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.如此一來，上一列總和為偶數，下一列 總和也必為偶數，則最後必為偶數第16页動動腦 3在平面上任意標出五個整數座標點。證明：其中必最少有兩個點，它們連線中點也是整數座標點。提醒1：(x1,y1)與(x2,y2)連線中點座標為 (x1+x2)/2,(y1+y2)/2)提醒2：整數點只會有以下四種奇偶性：(奇,奇)(偶,偶)(奇,偶)(偶,奇)第17页根據鴿洞原理，5個整數點中必有某兩點奇偶性相同！(因為奇偶性總共只有四種，點有五個)而當兩點(x1,y1),(x2,y2)有相同奇偶性時 x1+x2 與 y1+y2都是偶數 即(x1+x2)/2 與(y1+y2)/2皆為整數 (x1+x2)/2,(y1+y2)/2)為整數點第18页性質 31.奇數個奇數和必為奇數2.假如若干個整數a1a2a3連乘積 是奇數，則其中每個數ai都是奇數第19页動動腦 4設 n 為一奇數。又設 a1,a2,an 是1,2,n 任意一種排列。求證：(1-a1)(2-a2)(n-an)必為偶數。第20页假設(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 產生矛盾！第21页動動腦 5n 個整數 a1,a2,an 滿足以下等式 (i)a1a2an=n (ii)a1+a2+an=0 求證：n 為 4 倍數。第22页若n為奇數，且滿足 a1a2an=n則，a1、a2、an皆為奇數a1+a2+an 即為奇數個奇數和(=奇數)0 且因為a1+a2+an=0，所以a1、a2、an中 奇數必為偶數個，則偶數也必為偶數個，即a1、a2、an中偶數最少兩個，所以 a1a2an 連乘積必為4倍數！第23页動動腦 6某博物館共有25間展覽室，如圖所表示，這裡相鄰展覽室之間都有門相通。參觀者自東北角大門口開始參觀，希望依次不重複地看遍每一間展覽室之後仍回到東北角大門去。請問參觀者有哪幾種路線能够參觀？第24页如圖示，東北角展覽室為藍色，無論選擇怎樣路線，看展覽順序依序為藍1-橘1-藍2-橘2-藍3-橘12-藍13(因為藍展覽室有13間，橘展覽室有12間)然後呢？藍13必須接到藍1啊！？矛盾！第25页定理 1任何一個非完全平方數正整數都有偶數個因數。如20正因數有：1,2,4,5,10,2025正因數有：1,5,25第26页動動腦 7有一百盞燈，排列成一列，從左至右依次標上 1,2,100 這些號碼。每一盞燈都有一根拉線開關。另外，還有一百個人。最初燈全是關著，第一個人走過來把號碼為1倍數燈開關拉一下；接著第二個人走過來把號碼為2倍數燈開關拉一下；第三個人走過來把號碼為3倍數燈開關拉一下；如此繼續著，最後那個人走過來把最後那盞燈開關拉一下。這樣做過之後，請問留下哪些燈是亮著？第27页號碼為 k 燈，會不會被第i個人所拉，端看i是不是k因數，是，則此人拉，不是，則此人不拉！所以，1.假如 k 有 t 個因數則此盞燈共被拉了t次。2.燈原本全都是關，被拉奇數次燈是亮，被 拉偶數次燈是關 3.所以最後亮著燈為號碼 k 只有奇數個因數，為完全平方數，即：1,4,9,16,25,36,49,64,81,100 只有這10盞燈是亮！第28页動動腦 8在一條環形公路上，n個車站被n段公路連接了起來。車站所在地海拔高度共有5米和10米兩種。相鄰車站若海拔高度相同，則他們之間公路是水平；若不一样，則他們之間公路是有坡。有一個旅遊者開車在這條環形公路上沿順時針方向繞了一圈，發現有坡公路段數與水平公路段數一樣多。求證：車站個數 n 是 4 倍數。第29页因為：有坡公路段數與水平公路段數一樣多，表示n為偶數，所以n個路段中二分之一為水平路段、二分之一為有坡度路段。不过，有坡度路段中，二分之一為上坡、二分之一為下坡（才回得來啊！），所以，n為4倍數。12543612345第30页動動腦 9有 n 個數 1,2,n，全部數只能為1或-1。假如 12+23+n-1n+n1=0求證：n 是 4 倍數。提醒：跟上一題有關係第31页 把這 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=0表示兩種路段 數目相同，而有坡度路段繞一圈後上坡下坡各二分之一 所以，n 是 4 倍數。第32页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也為偶數。第33页動動腦 10一百個人排成一列縱隊。從頭到尾報完數之後，凡報奇數一律出列，只有報偶數仍依次留在隊列之中，接著從頭至尾再次報數，凡報奇數者一律出列，留下報偶數者，接著第三次從頭到尾報數，如此進行下去，請問最後留在隊列中那個人，他在第一次報數時報多少號？第34页提醒：第一次留下誰？第二次之後留下誰？第三次之後留下誰？第一次留下了：2,4,6,8,10,12,14,16,18,20,第二次留下了：4,8,12,16,20,第三次留下了：8,16,也就是說，擁有2最多數能够留到越後面，那麼1100中，誰有2次數最多呢？答案是：64=26第35页定理 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第36页動動腦 11求證：x2+1=8yn 沒有整數解。若 x 是偶數明顯有問題！若 x 是奇數，則 x2 被 8 除餘 1所以 x2+1 被 8 除餘 2，不过右式為 8 倍數第37页動動腦 12求證：正整數a與b，ab為偶數 若且唯若存在正整數c與d使得 a2+b2+c2=d2。第38页試想：若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。第39页先預祝大家聖誕快樂第40页
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
