42 歐幾里德的算計…輾轉相除法

詳細內容: 分類：戲說數學; 發佈於：15 四月 2014; 點擊數：1380

作者：國立台灣師範大學數學系教授許志農

話說兩千多年前的歐幾里德，寫出第一本數學暢銷書《幾何原本》，不僅遠在東方的康熙皇帝讚譽有加，就連西方的林肯總統也經常熬夜苦讀。在《簡短的自傳》裡，有過如下對林肯讀幾何原本的描述：「自從他當了議會議員之後，他學習並掌握了歐幾里德的六卷書。他開始專心致志地進行嚴格的腦力訓練，以提高他的才能，特別是他的邏輯和語文能力。由此他喜歡歐幾里德的書，他在巡行時總帶著它們，經常在枕邊放一小蠟燭，學習到深夜，直到他能容易地證明六卷書中的所有命題。而與此同時，一間屋子裡有半打他的律師伙伴們，沒完沒了的鼾聲充斥房間。」

據說，歐幾里德會善用《幾何原本》裡的知識娛樂他的學生。他又叫兩位學生上台，輪流在黑板上寫出新的正整數的數字比賽：歐幾里德先在黑板上寫出52及78兩個數字，之後叫台上的男女學生，依下列規則，輪流在黑板上寫上正整數：

(1) 所寫的數字必須是正整數，而且是黑板上某兩個數字的差。

(2) 寫過的數字不能再寫。

(3) 無法依規則寫出數字的一方輸。

這遊戲肯定不會平手，而且在有限回合後，就可以分出勝負。歐幾里德為了招收女弟子，讓更多的女生學會數學，經常巧妙的安排數字，讓女學生可以贏過男學生，就讓我們來玩這道遊戲在電腦上的 Flash 動畫版：

下圖是1到100的百數圖，甲﹑乙兩人輪流在百數圖上點選數字，規則如下：

(1) 起先甲﹑乙兩人各選一個數字，選到的數字會呈灰色狀。

(2) 接下來甲﹑乙兩人輪流點數字，點過的數字變成灰色，且每次新點的數字必須是前面點過某兩數的差。

(3) 無法依規則點數字的一方輸。

以上圖為例，當甲﹑乙選的數字為52與78時，接下來是甲點數字，因為甲必須點這兩個灰色數字之差，即甲只能點數字78-52=26，此時灰色數字變成三個，如下圖所示：

然後輪到乙點數字，這時灰色數字有52, 78及26三個，所以乙可以點的數字有52-26=26,78-26=52及78-52=26三個，但這三個數都是灰色數字（已被點過），所以乙無法依規則點新數字，甲贏得比賽。

關於這道點選數字的遊戲，如何判別何者可以贏？贏的策略為何？

在進入遊戲解答之前，讓我們瞭解一個物理學上很有名的實驗‥密立根油滴實驗，這實驗是透過測量不同微小油滴的帶電量來求得基本電荷量（一個電子所帶的電量）。實驗發現，將不同小油滴所量得的電荷除以0.8×10^-19，得到

2,6,14,18,46,‧‧‧

等的整數。從這樣的數據可以推出基本電荷量是多少嗎？當然可以，因為每滴油滴是基本電荷量的倍數，所以這些小油滴所帶電荷量的最大公因數可以視為基本電荷量。從上述數據可以知道基本電荷量為2×0.8×10^-19=1.6×10^-19。雖然只是最大公因數概念的簡單應用，但是卻讓密立根大大出名。同樣的情境，如果有五位美國學生到台灣觀光，他們在機場拿美金換台幣，分別換得

4725, 5670, 6930, 8064, 7087.5

元新台幣，那麼可以得知美金換台幣的匯率嗎？將這五個數除以0.5，得

9450, 11340, 13860, 16128, 14175.

又這五個數的最大公因數為63，所以可以推敲美金換台幣的匯率為

0.5×63=31.5,

即一塊美金應該換31.5塊台幣。

這個推敲的前提當然是：五位學生都拿整數的美金換台幣。最大公因數並不只是數學的名詞，他是日常生活中經常可用到，而且存在的一道觀念與現象。現在就讓我們回到遊戲本身。

在點選百數圖的遊戲中，如果甲﹑乙兩人所點選的數字為m與n ，其中m>n，那麼在點選比賽過程中，會有如下的疑問：

(1) 百數圖上被點選的最大數字為何？

(2) 百數圖上被點選的最小數字為何？

(3) 哪些數字會被點選？

(4) 誰會贏得比賽，需要策略才會贏嗎？