離散數(shù)學(xué)中許多有趣的問(wèn)題

1、離散數(shù)學(xué)中許多有趣的問(wèn)題By 孫一凡 老師簡(jiǎn)介離散數(shù)學(xué)亦稱組合數(shù)學(xué)。自古的數(shù)學(xué)，算術(shù)與幾何便分別代表了離散與連續(xù)觀念的源頭。兩種思維相互發(fā)展，造就了數(shù)學(xué)世界。但自牛頓開(kāi)創(chuàng)微積分以後，連續(xù)性數(shù)學(xué)便獨(dú)領(lǐng)風(fēng)騷三百年。今日離散數(shù)學(xué)的若干題材，雖可在數(shù)論、代數(shù)、機(jī)率、幾何等學(xué)科中發(fā)現(xiàn)其身影，但始終是理論深度不明的研究課題。 本世紀(jì)以來(lái) 離散的工具與方法，逐漸在各個(gè)學(xué)科中被發(fā)展及使用，而產(chǎn)生出新的焦點(diǎn)及新的科學(xué)意識(shí)。一些彼此關(guān)連的研究領(lǐng)域，開(kāi)始匯聚。 特別自三十年代以後，計(jì)算科學(xué)在理論與實(shí)用上都有突破性的發(fā)展。這是因?yàn)殡娔X的出現(xiàn)。電腦利用離散的表示處理資訊，離散現(xiàn)象的重要開(kāi)始被重視。此外，電腦幫人處理大量

2、的有限數(shù)及有限結(jié)構(gòu)，跑出了很多新層次的問(wèn)題需研究。 離散數(shù)學(xué)包含了什麼? 包羅了許多學(xué)域，比較重要的包括下列幾種：1.古典計(jì)算問(wèn)題，包括有限集合上的各類排列組合問(wèn)題2.以代數(shù)、拓樸方法建立組合學(xué)體系的研究3.以群論、有限幾何為主要工具的設(shè)計(jì)理論(Design Theory)4.圖形、網(wǎng)路與超圖的理論(Hypergraphs)請(qǐng)修：組合設(shè)計(jì)初步請(qǐng)修：組合設(shè)計(jì)初步請(qǐng)修：圖論初步、離散專題請(qǐng)修：圖論初步、離散專題請(qǐng)修：離散數(shù)學(xué)請(qǐng)修：離散數(shù)學(xué)離散數(shù)學(xué)包含了什麼?5. 最佳化、運(yùn)籌學(xué)(Operation Research)與賽局理論(Game Theory)6. 編碼(Coding Theory)與密碼

3、理論(Cryptography)7. 擬陣(Matroid)、廣義擬陣論(Greedoid)8. 離散與計(jì)算幾何學(xué)9. 演算法則的設(shè)計(jì)與分析請(qǐng)修：代數(shù)編碼學(xué)、密碼學(xué)請(qǐng)修：代數(shù)編碼學(xué)、密碼學(xué)請(qǐng)修：演算法請(qǐng)修：演算法離散數(shù)學(xué)有些什麼應(yīng)用？ 在應(yīng)用方面，最大的市場(chǎng)之一是資訊科學(xué)，已成為資訊系的必修課程。數(shù)位化的產(chǎn)物，如光碟、大哥大、衛(wèi)星通訊等等都仰賴錯(cuò)誤糾正碼(Error Correcting Code)設(shè)計(jì)以增加可靠性；提款卡、簽帳卡等也是密碼學(xué)的附產(chǎn)品；另外，DNA的定序問(wèn)題，選舉權(quán)力的分析，生物食物網(wǎng)的平衡，實(shí)驗(yàn)設(shè)計(jì)的安排，處處可見(jiàn)離散數(shù)學(xué)應(yīng)用的例子。討論整數(shù) 也可說(shuō)是組合數(shù)學(xué)的重要關(guān)鍵 整數(shù)

4、（Z）與實(shí)數(shù)（R）不同，兩者分別代表了離散觀念與連續(xù)觀念。 因此離散數(shù)學(xué)中，整數(shù)的觀念通常相當(dāng)重要，整數(shù)與整數(shù)的關(guān)係也是如此，可以廣泛的應(yīng)用在許多事上。正整數(shù) : 1,2,3,4,5,6, 零 : 0負(fù)整數(shù) : -1,-2,-3,-4, 單數(shù)(奇數(shù)) : 1,3,5, 雙數(shù)(偶數(shù)) : 0,2,4,6, 先看一些整數(shù)的性質(zhì) 來(lái)熱熱身！性質(zhì) 1 :奇數(shù)： (odd) 被2除餘1的數(shù)字 任何奇數(shù)都可表為 2n+1 的形式偶數(shù)： (even)可被2整除的數(shù)字 任何偶數(shù)都可表為 2n 的形式動(dòng)動(dòng)腦 1某班49位同學(xué)，坐成七行七列。每個(gè)座位的前後左右稱做它的鄰座。要同時(shí)讓這49位同學(xué)中的每一位都換到他的

5、鄰座上去，是否能辦到？提示當(dāng)一聲令下，所有同學(xué)都換到他們的鄰座時(shí)，原本坐 位子的同學(xué)會(huì)換到原本就坐 的位子，可是 . . . . ：24個(gè) ：25個(gè) 所以，不可能！不可能！性質(zhì) 2 :奇數(shù) + 奇數(shù) = 偶數(shù)偶數(shù) + 偶數(shù) = 偶數(shù)奇數(shù) + 偶數(shù) = 奇數(shù)奇數(shù) - 奇數(shù) = 偶數(shù)偶數(shù) - 偶數(shù) = 偶數(shù)奇數(shù) - 偶數(shù) = 奇數(shù)動(dòng)動(dòng)腦 2設(shè) 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| 這樣一直做下去，最後得

6、到的整數(shù)一定會(huì)為偶數(shù)。例如：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？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| = ? 如何將絕對(duì)值拆掉？3. 若a1a2 則|a1-a2|= a1-a2 a1a2 則|a1-a2|= a2-a1 4. 假設(shè)絕對(duì)值都拆掉了，上式會(huì)變成如 = (

7、a1-a2)+(a4-a3)+(a6-a5)+(a7-a8) = (a1+a4+a6+a7)-(a2+a3+a5+a8) 之類的 (總之，有4個(gè)數(shù)字在前括號(hào)中，另外4 個(gè)數(shù)字在後括號(hào)中)5. (a1+a4+a6+a7)+(a2+a3+a5+a8) = 36 因?yàn)锳+B=偶數(shù)，則A,B必同為偶數(shù)或同為 奇數(shù)，所以A-B必為奇-奇或偶-偶 = 偶數(shù)6. 如此一來(lái)，上一列的總和為偶數(shù)，下一列 的總和也必為偶數(shù)，則最後的必為偶數(shù)動(dòng)動(dòng)腦 3在平面上任意標(biāo)出五個(gè)整數(shù)座標(biāo)的點(diǎn)。證明：其中必至少有兩個(gè)點(diǎn)，它們的連線的中點(diǎn)也是整數(shù)座標(biāo)的點(diǎn)。 提示1：(x1,y1)與(x2,y2)的連線中點(diǎn)座標(biāo)為 (x1+x2)

8、/2,(y1+y2)/2)提示2：整數(shù)點(diǎn)只會(huì)有以下四種奇偶性： (奇,奇) (偶,偶) (奇,偶) (偶,奇)根據(jù)鴿洞原理，5個(gè)整數(shù)點(diǎn)中必有某兩點(diǎn)的奇偶性相同！ (因?yàn)槠媾夹钥偣仓挥兴姆N，點(diǎn)有五個(gè)) 而當(dāng)兩點(diǎn)(x1, y1), (x2, y2)有相同奇偶性時(shí) x1+ x2 與 y1 + y2都是偶數(shù) 即 (x1+x2)/2 與 (y1+y2)/2皆為整數(shù) (x1+x2)/2,(y1+y2)/2)為整數(shù)點(diǎn)性質(zhì) 31. 奇數(shù)個(gè)奇數(shù)的和必為奇數(shù)2. 如果若干個(gè)整數(shù)a1a2a3的連乘積 是奇數(shù)，則其中每個(gè)數(shù)ai都是奇數(shù)動(dòng)動(dòng)腦 4設(shè) n 為一奇數(shù)。又設(shè) a1,a2, ,an 是1,2, ,n 的任意一種

9、排列。求證：(1- a1)(2- a2) (n- an)必為偶數(shù)。假設(shè)(1- a1)(2- a2) (n- an)為奇數(shù)則 1- a1 , 2- a2 , , n- an 都是奇數(shù) (1- a1)+(2- a2)+(n- an) =1+2+n - (a1+a2+an) =1+2+n - (1+2+n) = 0 產(chǎn)生矛盾！動(dòng)動(dòng)腦 5n 個(gè)整數(shù) a1, a2, ,an 滿足以下等式 (i) a1a2an = n (ii) a1+a2+an = 0 求證： n 為 4 的倍數(shù)。若n為奇數(shù)，且滿足 a1a2an = n則， a1、a2、an皆為奇數(shù)a1+a2+an 即為奇數(shù)個(gè)奇數(shù)的和(=奇數(shù))0且因?yàn)?/p>

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

11、。如20的正因數(shù)有：1, 2, 4, 5, 10, 2025的正因數(shù)有：1, 5, 25動(dòng)動(dòng)腦 7有一百盞燈，排列成一列，從左至右依次標(biāo)上 1,2,100 這些號(hào)碼。每一盞燈都有一根拉線開(kāi)關(guān)。另外，還有一百個(gè)人。最初燈全是關(guān)著的，第一個(gè)人走過(guò)來(lái)把號(hào)碼為1的倍數(shù)的燈的開(kāi)關(guān)拉一下；接著第二個(gè)人走過(guò)來(lái)把號(hào)碼為2的倍數(shù)的燈的開(kāi)關(guān)拉一下；第三個(gè)人走過(guò)來(lái)把號(hào)碼為3的倍數(shù)的燈的開(kāi)關(guān)拉一下；如此繼續(xù)著，最後那個(gè)人走過(guò)來(lái)把最後那盞燈的開(kāi)關(guān)拉一下。這樣做過(guò)之後，請(qǐng)問(wèn)留下哪些燈是亮著的？號(hào)碼為 k 的燈，會(huì)不會(huì)被第i個(gè)人所拉，端看i是不是k的因數(shù)，是，則此人拉，不是，則此人不拉！ 所以， 1. 如果 k 有 t 個(gè)

12、因數(shù)則此盞燈共被拉了t次。 2. 燈原本全都是關(guān)的，被拉奇數(shù)次的燈是亮的，被 拉偶數(shù)次的燈是關(guān)的 3. 所以最後亮著的燈為號(hào)碼 k 只有奇數(shù)個(gè)因數(shù)， 為完全平方數(shù)，即： 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 只有這10盞燈是亮的！動(dòng)動(dòng)腦 8在一條環(huán)形公路上，n個(gè)車站被n段公路連接了起來(lái)。車站所在地的海拔高度共有5米和10米兩種。相鄰車站若海拔高度相同，則他們之間的公路是水平的；若不同，則他們之間的公路是有坡的。有一個(gè)旅遊者開(kāi)車在這條環(huán)形公路上沿順時(shí)針?lè)较蚶@了一圈，發(fā)現(xiàn)有坡的公路段數(shù)與水平公路段數(shù)一樣多。求證：車站的個(gè)數(shù) n 是 4 的倍數(shù)。因?yàn)椋河衅碌墓范?/p>

13、數(shù)與水平公路段數(shù)一樣多，表示n為偶數(shù)，所以n個(gè)路段中一半為水平路段、一半為有坡度路段。但是，有坡度路段中，一半為上坡、一半為下坡（才回得來(lái)?。。?，所以，n為4的倍數(shù)。12543612345動(dòng)動(dòng)腦 9有 n 個(gè)數(shù) 1, 2, , n，所有的數(shù)只能為1或-1。如果 12+23+n-1n+n1=0求證： n 是 4 的倍數(shù)。 提示：跟上一題有關(guān)係 把這 n 個(gè)數(shù) 1, 2, , n想成 n 個(gè)車站， 海拔10公尺的車站標(biāo)為1，海拔5公尺的車站標(biāo)為-1。 如此一來(lái)，12若為1，表示兩車站同為1或同為-1 12若為-1，則表示兩車站一為1一為-1，也就是 12為1表示該路段為水平路段， 12為-1表示該

14、路段為有坡度路段， 12+23+n-1n+n1 = 0表示兩種路段 數(shù)目相同，而有坡度的路段繞一圈後上坡下坡各一半 因此， n 是 4 的倍數(shù)。12 , 23 , , n-1n , n1當(dāng)中 1的個(gè)數(shù)等於-1的個(gè)數(shù)，所以 n = 2k如果 12 =1 則 1=2 =1 或 1=2 = -1 表示從1到2符號(hào)沒(méi)有發(fā)生變化如果 12 =-1 則說(shuō)明符號(hào)有發(fā)生變化從1開(kāi)始，最後回到1，說(shuō)明這一過(guò)程中發(fā)生了k次符號(hào)變化，但1與本身是同號(hào)的，所以k也為偶數(shù)。動(dòng)動(dòng)腦 10一百個(gè)人排成一列縱隊(duì)。從頭到尾報(bào)完數(shù)之後，凡報(bào)奇數(shù)的一律出列，只有報(bào)偶數(shù)的仍依次留在隊(duì)列之中，接著從頭至尾再次報(bào)數(shù)，凡報(bào)奇數(shù)者一律出列，

15、留下報(bào)偶數(shù)者，接著第三次從頭到尾報(bào)數(shù)，如此進(jìn)行下去，請(qǐng)問(wèn)最後留在隊(duì)列中的那個(gè)人，他在第一次報(bào)數(shù)時(shí)報(bào)多少號(hào)？提示：第一次留下誰(shuí)？第二次之後留下誰(shuí)？ 第三次之後留下誰(shuí)？第一次留下了：2,4,6,8,10,12,14,16,18,20,第二次留下了：4,8,12,16,20,第三次留下了：8,16,也就是說(shuō)，擁有2最多的數(shù)可以留到越後面，那麼1100中，誰(shuí)有2的次數(shù)最多呢？ 答案是：64 = 26定理 2 偶數(shù)的平方可以被 4 整除。奇數(shù)的平方被 8 除，餘數(shù)為 1。因?yàn)?2k)2 = 4k2 (2h+1)2 = 4h2+4h+1 = 4h(h+1)+1 h與h+1中必有一個(gè)為偶數(shù)，所以 4h(h+1)+1 = 8m+1動(dòng)動(dòng)腦 11求證：x2+1=8yn 沒(méi)有整數(shù)解。若 x 是偶數(shù)明顯有問(wèn)題！若 x 是奇數(shù)，則 x2 被 8 除餘 1所以 x2+1 被 8 除餘 2，但是右式為 8 的倍數(shù)動(dòng)動(dòng)腦 12求證：正整數(shù)a與b，ab為偶數(shù) 若且唯若存在正