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