<4D F736F F D203033A4DAB4B5A564A454A8A4A7CEAABAB458ADD3A9CABDE82E444F43>

Size: px

Start display at page:

Download "<4D F736F F D203033A4DAB4B5A564A454A8A4A7CEAABAB458ADD3A9CABDE82E444F43>"

劳吕
5 years ago
Views:

1 一個魔術請讓我為你變一個魔術首先, 請你在紙上將任意六個阿拉伯數字寫在同一列上 ( 數字可重複 ), 例如 : 在你寫完之後我將很快地在另一張紙上寫下一個數字 ( 不讓你看到是多少 ), 然後我請你將你所寫的六個數字由左而右兩兩相加, 將每兩個相鄰的數字的和除以 9 的餘數寫在兩個數字的下方 ; 以剛才的六個數字為例, 你將在第二列寫下,, 4,, 等五個數字, 因為除以 9 的餘數為, 除以 9 的餘數為, 除以 9 的餘數為 4 等 : 接著我請你依此類推, 用相同的方式由第二列產生第三列, 由第三列產生第四列,, 直到第六列為止 ; 第六列將只剩一個數字 ( 以本例而言為 7): 此時我向你展示我當初寫在紙上的數, 它竟然是 7, 因此我老早就知道最後的數字會是 7 了你知道我是怎麼知道的嗎? 許介彥大葉大學電信工程學系巴斯卡三角形以上所述是一個和數學上有名的巴斯卡三角形 (Pascal s tiagle) 有關的魔術 ; 下圖顯示了巴斯卡三角形的最上面幾列 ( 往下可無限延伸 ): 如果我們將最上面一列稱為第零列, 其下依序為第一列第二列, 那麼巴斯卡三角形的第列含有以下 ( +) 個數 : 其中,,,,! =!(!,. 數學上也常將記作 C (, ) 由於 C (, ) = C(, ) =, 因此每一列的左右兩端一定都是如果我們定義當 < 或 > 時 C (, 的值為 ( 也就是將上圖位於三角形區域外的空白處都視為, 本文以下皆採此定義 ), 那麼巴斯卡三角形除了第零列的 - -

2 之外, 位於其他列上的每個數都滿足下面的遞迴關係 : + =. 巴斯卡三角形自古以來即吸引了眾多數學家的目光, 在它看似平淡無奇的外表下隱含著諸多奇妙的性質, 即便時至今日仍不時有新的性質被挖掘出來 ; 本文接下來將介紹巴斯卡三角形的幾個有趣而又不難理解的性質同一列中的公因數經由觀察巴斯卡三角形的最上面幾列, 您也許注意到對某些特定的而言, 第列除了頭尾兩端的之外的其他 ( ) 個數全部都是的倍數 ; 例如當為 7 時, 第七列的 7,, 35, 35,, 7 等全都是 7 的倍數以下我們証明當為質數時必定如此定理一 : 當為質數且 < <, C (, 必是的倍數証明 : ( )( ) L( + ) = ( )( ) L 上面的分數中, 分子是的倍數, 但分母卻一定不是的倍數 ( 因為分母的每個因數都小於, 都與互質 ), 由此可知 C(, 一定是的倍數我們還可推知第列除了頭尾兩端的之外的其他 ( ) 個數的最大公因數一定是 ( 因為 C (,) = ) 經由觀察巴斯卡三角形中的數, 您也許還注意到對每一列而言, 除了頭尾兩端的之外, 位於同一列上的任意兩數之間似乎都不會互質, 是否真的如此呢? 答案是肯定的, 以下我們加以証明定理二 : 當 3 且 < i < j <, C (, C (, j) 必有大於的公因數証明 : 與下式是一個恆等式 ( 由組合的觀點不難說明此式為何正確 ): i j = i j j i 如果 C (, 與 C (, j) 互質, 等號右邊的 C( j, 一定會是左邊的 C (, 的倍數, 然而實際上 C( j, 根本就比 C (, 還小, 因此 C (, 與 C (, j) 不可能互質上面的論述其實還不完整, 因為並沒有考慮到等號兩邊有可能同時為, 這在 < i + j 時確實會發生 ; 不過既然巴斯卡三角形的每一列都是左右對稱, 只要我們限定 i 與 j 都不大於 / 就可以將等號兩邊都是的情形排除了 ( 為數學上的 floo fuctio 慣用的記號 ; 對任意實數 x,x 的值為所有小於或等於 x 的整數中最大的整數, 例如 4.3= 4, 5 = 5, 4.3= 5 例題 : 等 ) 以下我們看一個相關的例題求出下面的數列的最大公因數 :,, 3,...,

3 科學教育月刊第 75 期中華民國九十三年十二月解 : 由二項式定理知 ( + x) = C + C x + L + C 將 x 以代入得 = C + C + C + L + C 將 x 以代入則為 = C C + C L + C 兩式相減, 得 x = C C C C L. 如果題目所求的最大公因數為 d, 由上式可知 d 一定是的某個整數次方 k q 如果我們將表為, 其中的 q 為奇 k+ 數, 那麼 C(,) = = q, 因此 d 不可能大於 + k + 以下我們將說明 d 其實就等於 k, 也就是說, 當 =, 3, 5, K,( ), k+ 一定能整除 C (,, 這由下式不難得知 : ()! ( )! = =!(! ( )!(! k+ q = = 由於為奇數, k+ 一定與互質, 而 q 與 C (, ) 都是整數, 因此 C (, 的因數巴斯卡三角形中的奇數 k+ 一定是巴斯卡三角形的第零列有一個奇數, 第一列與第二列各有兩個奇數, 第三列則有四個奇數 ; 如果我們由三角形的頂端一列一列往下看, 各列中的奇數個數分別是,,, 4,, 4, 4, 8,, 4, 4,, 它們似乎都是的整數次方 ; 本文接下來將証明的確是如此, 不過我們先証明以下定理 : 定理三 : 當為偶數且為奇數, C (, 必為偶數當為奇數或為偶數, C (, 為偶數若且唯若 C ( 証明 : 組合 : 為偶數依與為奇數或偶數總共有四種可能的 (I) 為偶數且為奇數 (II) 與皆為偶數 (III) 與皆為奇數 (IV) 為奇數且為偶數以下我們針對各種情形分別討論 (I) 為偶數且為奇數此時的一定大於當 < 時, 下式一定成立 :! ( )! = =!(! ( )!(! = 由於 C (, 等於 ( 一個偶數 ) 除以 ( 一個奇數 ) 再乘以 C (, ) ( 一個整數 ), 因此 C (, 必為偶數 (II) 與皆為偶數當 > 時, ( )( ) L( + ) = ( )( ) L 上式分子的 ( ),( 3), K,( + ) 等數及分母的 ( ),( 3), K, 等數都是奇數 ; 由於我們的目標是要判斷 C (, 是否為偶數, 因此所須在意的只是分子與分母中的偶數 ( 更明確地說, 我們須在意的是分子中的因數是否會全部與分母中的抵消 ), 至於式子中 - -

4 的奇數則無關大局, 不妨先將它們剔除, 因此 C (, 為偶數若且唯若 ( )( 4) L( + ) ( )( 4) L 為偶數 ; 此分數的分子與分母各有 / 個偶數相乘, 將分子與分母中的各項都除以得 L + L 這其實就是 C ( /, / ), 也就是 C ( ( 因為 / 與 / 都是整數 ), 因此當與皆為偶數 ( 且 > ) 時, C (, 為偶數若且唯若 C ( 為偶數 ; 此說法在為時其實也成立, 因為當 =, C (, = C( = (III) 與皆為奇數再次利用下式 : = 由於與皆為奇數, 因此 C (, 為偶數若且唯若 C (, ) 為偶數 ; 此時的 ( ) 和 ( ) 都是偶數, 因此這其實回到了我們剛看過的情形 (II), 所以 C (, ) 為偶數若且唯若 C (( ) /,( ) / ) 為偶數 ; 又由於對任意奇數 k 而言, k / 必等於 ( k ) /, 因此當與皆為奇數時, C (, 為偶數若且唯若 C ( 為偶數 (IV) 為奇數且為偶數此時的一定不等於 ; 將 C (, 表為分式並將分子與分母同時乘以 (, 得 ( )! ( )! = = (!! ( )!! = 既然與 ( 都是奇數, C (, 為偶數若且唯若 C(, 為偶數, 而此時的 ( ) 和都是偶數, 因此又回到了情形 (II); 由於此時 ( ) / = /, 因此我們同樣得到 C (, 為偶數若且唯若 C ( 為偶數的結論既然我們已經考慮過與所有四種可能的奇偶組合, 定理三的証明於焉完成判別奇偶的演算法定理三提供了我們一個可以不用實際算出 C (, 就能判斷 C (, 是奇數或偶數的方法 : 如果為偶數且為奇數, C (, 一定是偶數, 否則依 C ( 定 ; 如果 / 為偶數且 / 是奇數或偶數而為奇數, 則 C ( 為偶數 ( 因此 C (, 為偶數 ), 否則依 C ( / /, / / ) 是奇數或偶數而定 ; 如果 / / 為偶數且 / / 為奇數, 則 C (, 為偶數, 否則依 C ( / / /, / / / ) 是奇數或偶數而定 ;, 只要我們在某個步驟能確定 C (, 是偶數, 判斷過程即告終止, 而如果我們一直無法作出 C (, 是偶數的判斷, 由於數字會越來越小, 我們終將面臨須決定 C (, ) 是奇數或偶數的工作, 而這是很簡單的, 因為 C (, ) = 為奇數上述判斷過程可以簡潔地表達成以下的 - 3 -

5 科學教育月刊第 75 期中華民國九十三年十二月遞迴演算法 : OddOEve(, if = = etu 答案為奇數 else if 為偶數且為奇數 etu 答案為偶數 else etu OddOEve( /, 何一個位數分別為和若且唯若 C (, 為偶數舉例來說, 43 =, 8 =, 由於這兩個二進位數的倒數第五位數分別為和 : 43 = 8 = 因此 C (43,8) 一定是偶數與二進制的關係上述演算法雖然可行, 不過判斷過程有可能須歷經好幾個階段才能得出結果 ; 以下我們將說明 : 如果我們在開始判斷之前先將與表為二進位數, 其實一眼就能看出 C (, 是奇數或偶數首先, 我們注意到對任意非負整數 k, 如果 k 被表成了二進位數, 我們可以由 k 的個位數很快地判斷出 k 是偶數或奇數 : 為偶數, 則是奇數 ; 另外, 當 k 被表為二進位數時, 將 k 的個位數刪去 ( 不管是或是 ) 的結果一定就等於 k / 有了上述認識後, 如果我們將與表為二進位數, 那麼前面的遞迴演算法中要判斷是否為偶數且為奇數其實只須觀察與的個位數是否分別為和即可 ; 如果不是, 我們接著要判斷 C ( 時只須觀察 / 與 / 是否為偶數的個位數 ( 也就是與的倒數第二位數 ) 是否分別為和即可 ; 如果不是, 我們接著觀察與的倒數第三位數是否分別為和 ; 如果不是, 我們接著觀察與的倒數第四位數是否分別為和, 因此, 表為二進位數後的與有任某一列中的奇數個數有了以上準備工作, 我們終於可以回到我們先前要探討的問題 : 巴斯卡三角形的第列中有多少個奇數? 如果 C (, 的與都被表成了二進位數, 這個問題相當於 : 第列中, 與沒有任何一個位數分別為和的有幾個? 也就是說, 每當的某位數為, 的同一位數也必是的有幾個? 如果 C (, 是奇數, 每當的某位數為, 的同一位數一定是, 但是當的某位數為時, 的同一位數可以是或, 因此的每一個都對應到兩個可能的值 ; 我們由此推知, 如果 d () 代表被表為二進位數後的所含的個數, 那麼巴斯卡三角形的第列中 ( ) d 的奇數個數必為 ; 正如我們之前所言, 一定是的某個整數次方舉例來說, 巴斯卡三角形的第 8 列一定含有正好 = 4 個奇數, 因為 8 = 含有兩個 ; 我們甚至能很快地指出是哪四個, 它們分別是 =, =, = 6 及 = 8, 對應到第 8 列中的 C (8, ), C (8, ), C (8,6), C (8,8) 等四個數 - 4 -

6 請讀者留意當的某位數為, 的同一位數也必是的另一個說法是當的某位數為, 的同一位數也必是, 因此 C(, 為奇數若且唯若為之處也為, 這通常稱為 Lucas theoem, 因法國數學家 Édouad Lucas(84 89) 而得名 ; 數學上著名的河內塔問題也是由這位數學家提出的 ( 事實上, 河內塔問題與巴斯卡三角形中的奇數間存在著有趣的關連, 本文暫不討論 ) 如果我們將巴斯卡三角形中的每個奇數以一個小黑格表示, 每個偶數以一個小白格表示, 所得的圖形將具有相當美妙的結構 ; 下圖所示為巴斯卡三角形的最上面 64 列 ( 第零列至第 63 列 ) 所對應的圖形 : 此圖與數學上一個稱為 Sieiski tiagle( 或稱 Sieiski gasket) 的碎形相當類似如果我們將一個正三角形的內部塗成黑色, 然後將各邊中點連線所形成的三角形挖掉, 並將類似的動作對剩下的三角形重複無窮多次, 所得即為 Sieiski tiagle; 下圖所示為最初幾個步驟所得的結果 : 當上述動作重複了無窮多次後, 黑色部份的面積將趨近於 ( 不難証明 ); 因此如果我們從巴斯卡三角形中隨機選出一數, 該數為奇數的機率幾乎等於 Lucas 定理上面的討論將巴斯卡三角形中的數分成了奇數與偶數兩大類, 以算術的觀點來看, 這相當於是將巴斯卡三角形中的數依除以的餘數是或分成兩類 ; 由於 = 且 = = = 如果我們將與分別表為二進位數 : = ( a a = ( b b m m m m La a ) Lb b ) ( a, < ), 那麼當與有任何一個位 i bi 數分別為和 ( C (, 為偶數 ) 時, m Π i = ai (mod ) b i 必為, 否則一定為, 因此下式成立 : m Π i = ai (mod ). b i 一般而言, 對任意質數, 如果我們將與分別表為進位數 : = ( a = ( b a m m b m m Lb b ) La a ) ( a, b ), 那麼下式一定成立 : i i < m ai (mod ) Π i b. = i 這可說是一般化的 Lucas theoem; 以下是此定理的一個簡要的証明首先, 我們注意由於 = ( am L a a ) = ( am La ) + a = / + a - 5 -

7 科學教育月刊第 75 期中華民國九十三年十二月且 / b = + 只要我們能夠証明 / / a b (mod ) 剩下的工作由歸納法即可完成 ( 讀者不難看出定理三就是此式在 = 時的特例 ) 我們在前面的定理一看過, 對任意質數, 巴斯卡三角形的第列中除了頭尾兩端的之外的每個數一定都是的倍數, 因此對任意整數 x, ( + x) + x (mod ) 一定成立對模而言, ( + x) / a = ( + x ) ( + x) / a ( + x ) ( + x) / a / i a j = x x i= i j= j 上式左右兩邊的 x 的係數對模而言一定同餘, 其中左邊的 x 的係數為 C (,, 而由於 a 和 b 都小於, 右邊的定是由 / x b 與 x / + b x ( = x ) 一相乘而得 ( 即發生於 i = / 且 j = b 時 ), 因此我們有了的結論 / / a b (mod ) 舉個例子假設我們想知道 C (6,59) 除以 7 的餘數是多少 ; 由於 6 = 467 且 59 = 35 7, 我們可以由上述定理很快算出答案為 6: (mod 7) 由模推廣至模的觀念也可以應用到我們前面利用小黑格和小白格組成的三角形圖案中 ; 下面幾個圖是當分別為時的圖形, 其中的小白格與小黑格分別對應到巴斯卡三角形中與同餘及不與同餘的數的位置 ; 讀者不難看出其中許多圖形同樣隱含著遞迴的概念 mod 3 mod 4 mod 5 mod 6 mod 7 mod 9 如果讀者熟悉程式設計的話不難利用電腦畫出當模為其他數時的圖形, 甚至可以在圖形中使用更多顏色, 例如當模為 3 時可以將除以 3 的餘數為的數分別以三種顏色來顯示 ; 只要搭配得宜, 這類圖形看起來常令人賞心悅目, 您甚至可能從圖形的觀察中推測出巴斯卡三角形的更多不為人知的性質 - 6 -

8 練習題參考以下是幾個與本文相關的問題, 提供讀者. 說明為什麼巴斯卡三角形的第列一定全為奇數, 而第列除了頭尾兩端的之外一定全為偶數. 求証 : 對任意正整數, C (, ), C (,), C(, ), K, C(, 為嚴格遞增數列 3. 利用巴斯卡三角形 :() 說明為什麼 4 = 464 () 將 464 作質因數分解 4. 求証 : 對任意大於的奇數, 數列,,,K, 3 ( 中的奇數個數必為奇數 ) / 5. 求証 : 對任意質數, C (, ) 除以的餘數必為 ( 提示 : 利用 Vademode s idetity 將 C ( +, ) 展開 ) 6. 以下是一個與巴斯卡三角形的構造類似的三角形, 它的兩條腰不是全由組成而是由,, 3, 4, 5, 依序遞增 : 如果我們將此三角形的第列由左邊算起的第個數記作 D (, ( 假設列的編號及同一列中位置的編號都是由算起 ), 那麼 D (,) = D(, ) =, 而且對介於與之間的而言, D (, = D(, + D(, ) 試求出 D (, 的通式 7. 以下的三角形中, 除了最上面一列外, 其他列上的每一個數都是該數的上一列的相鄰兩數之差請問 : 此三角形最底端的數是多少? 以下的三角形中, 除了最頂端的外, 其他列上的每一個數都是該數正上方的數與其左右兩邊的數的和 ( 亦即上一列的連續三數之和, 空白處當作是 ): 試証 : 除了最上面的兩列外, 此三角形的每一列都有偶數結語巴斯卡三角形中的數常被稱為二項式係數 (biomial coefficiets), 因它們出現於二項式定理中而得名將 x = 代入 ( + x) 的展開式可知巴斯卡三角形的第列的 ( +) 個數的和為 ; 當為質數時我們又知道第列除了頭尾兩端的之外的其他數都是的倍數, 因此第列的 ( +) 個數之和必定是的某個倍數加, 也就是對任意質數, 必為的倍數, 這 - 7 -

9 科學教育月刊第 75 期中華民國九十三年十二月其實是費瑪小定理 (Femat s little theoem) 的一個特例在本文結束前讓我們回頭看看本文一開始提及的魔術 ; 這個魔術不見得要從六個數開始, 以下我們先看由四個數開始的情形假設最初的四數為 A, B, C, D ; 如果在各階段先不做除以 9 取餘數的動作, 整個計算過程將如下 : A B A+B B+C C+D A+B+C C B+C+D A+3B+3C+D 因此這個魔術最後一列的數一定會等於 A, B, C, D 分別乘以 (, 3, 3,) 後全部相加再除以 9 的餘數, 而 (, 3, 3,) 正是巴斯卡三角形的第三列 ; 這當然並非偶然, 讀者不難看出如果此魔術是從個數開始, 最後一列的數一定會是一開始的個數分別乘上巴斯卡三角形的第 ( ) 列的個數後全部相加再除以 9 的餘數以本文一開始的 8, 3, 7, 6, 4, 5 六數為例, 最後一列的數將是它們分別乘上, 5,,, 5, 後全部相加再除以 9 的餘數 ; 由於我們在意的只是除以 9 的餘數, 因此計算過程中所有的數都可以用除以 9 之後的餘數 ( 或是對模 9 而言同餘的數 ) 取代 ; 以本例而言, 我們很快就能算出 ( 甚至用心算 ) 最後的數字為 D (mod 9) 讀者不難看出這個魔術中的 9 其實並無特殊之處, 即使是除以 8 除以 3 或是除以任何其他數此魔術都依然可行, 只是數字恰當的話算起來較快而已舉個例子, 如果在一開始我請你將任意八個阿拉伯數字寫在同一列上, 而且在計算過程中對所有的數做除以 7 取餘數的動作, 那麼我不須具備任何特殊的心算技巧就一定能在看到你所寫的八個數之後的半秒鐘內知道最後一列的數字會是多少 ; 既然你已經看完了這篇文章, 你一定知道我是怎麼知道的了參考資料. 許介彥 (), 遞迴演算法簡介, 科學教育月刊, 第 45 期. 許介彥 (3), 同餘的基本概念, 科學教育月刊, 第 6 期 3.R. P. Gimaldi, Discete ad Combiatoial Mathematics, 4th editio, Addiso-Wesley, D. E. Kuth, The At of Comute Pogammig, Volume Oe, Fudametal Algoithms, d editio, Addiso-Wesley,

Microsoft Word - ACL chapter02-5ed.docx

Microsoft Word - ACL chapter02-5ed.docx 第 2 章神奇的質數 2.1.1 什麼是質數 1 1 1 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 1 1 0 10 2 3 5 7 4 6 8 9 10 4 10000 1229 1000 168 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131