2009年12月13日

天使與魔鬼

作者/游森棚(任教高雄大學應用數學系)

繼《達文西密碼》橫掃全球後,原作者丹布朗的另一本《天使與魔鬼》也跟著大暢銷。不過讀者可能不知道,其實天使與魔鬼在棋盤上的纏鬥,是數學上一個有名的問題。這個月我們就來聊聊棋盤上的天使與魔鬼。他們纏鬥的方式是這樣的:

在無限大的西洋棋盤上,一開始天使站在某一格上。然後魔鬼敲掉另一格的地板。天使接著往上下左右或對角線方向任意移動一格,但是不能走到地板已經被敲掉的格子裡(否則就會墜入無底的深淵)。魔鬼接著再敲掉一格,天使再移動一格,以此類推。

要問的問題是:是邪不勝正(天使總有辦法一直跑來跑去,不會被困住),還是正不勝邪(天使終會被魔鬼困住,無法再移動)?我建議讀者現在停下來,找個朋友,甚至跟家裡的小朋友,兩個人一起來玩這個遊戲。很刺激的!讀者的答案是哪一邊?是天使能不受拘束自由自在,或者魔鬼讓天使無容身之地?

這個問題在1982年最初由英國大數學家康威(Conway)提出,他也提到數學家伯利坎普(Berlekamp)已經解決了這個問題,答案是正不勝邪——天使總有一天會動彈不得。這表示天使的能力不夠強,於是康威接著問:如果天使可以每次走兩步呢(魔鬼仍然一次只能敲掉一格地板)?答案是邪不勝正,還是正不勝邪?

我們把原來一次走一格的天使稱為「單倍力天使」,每次可以走兩格的天使稱為「雙倍力天使」。所以康威問的是,雙倍力天使和魔鬼對決,誰勝誰負?(起初第一個問題的結果就是,單倍力天使和魔鬼對決必敗)

康威百思不得其解,沒想出答案。怎麼辦呢?數學家考慮一個問題時,如果卡住了,常用的手法是將其一般化。一般化的後果當然是變得更難更抽象,但好處是或許反而可以顯露出本質所在,而不會受限於起初的特例。

於是康威問,是否存在一個k,使得「k倍力天使」和魔鬼對決必勝?或是不管k是多少,魔鬼永遠可以讓「k倍力天使」動彈不得?康威公開徵求解答,如果能證明前者,賞金100美元(是不多,但讀者知道,這不是賞金多寡的問題,而是一種榮耀);而如果能證明後者,賞金1000美元。【更詳細的內容,請參閱第480期科學月刊】

回本期目錄

沒有留言: