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

離散數學中許多有趣的問題By孫一凡老師簡介•「離散數學」亦稱「組合數學」。自古的數學，算術與幾何便分別代表了離散與連續觀念的源頭。•兩種思維相互發展，造就了數學世界。但自牛頓開創微積分以後，連續性數學便獨領風騷三百年。今日離散數學的若干題材，雖可在數論、代數、機率、幾何等學科中發現其身影，但始終是理論深度不明的研究課題。本世紀以來離散的工具與方法，逐漸在各個學科中被發展及使用，而產生出新的焦點及新的科學意識。一些彼此關連的研究領域，開始匯聚。特別自三十年代以後，計算科學在理論與實用上都有突破性的發展。這是因為電腦的出現。電腦利用離散的表示處理資訊，離散現象的重要開始被重視。此外，電腦幫人處理大量的有限數及有限結構，跑出了很多新層次的問題需研究。「離散數學」包含了什麼?•包羅了許多學域，比較重要的包括下列幾種：1.古典計算問題，包括有限集合上的各類排列組合問題2.以代數、拓樸方法建立組合學體系的研究3.以群論、有限幾何為主要工具的設計理論(DesignTheory)4.圖形、網路與超圖的理論(Hypergraphs)請修：組合設計初步請修：圖論初步、離散專題請修：離散數學「離散數學」包含了什麼?5.最佳化、運籌學(OperationResearch)與賽局理論(GameTheory)6.編碼(CodingTheory)與密碼理論(Cryptography)7.擬陣(Matroid)、廣義擬陣論(Greedoid)8.離散與計算幾何學9.演算法則的設計與分析請修：代數編碼學、密碼學請修：演算法離散數學有些什麼應用？•在應用方面，最大的市場之一是資訊科學，已成為資訊系的必修課程。數位化的產物，如光碟、大哥大、衛星通訊等等都仰賴錯誤糾正碼(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,4•7131•62•4•4,8,1,6,5,3,2,7•4525•13•2Why？•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的倍數。12543612345•動動腦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與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。先預祝大家聖誕快樂