logo 首頁 > 文匯報 > 教育 > 正文

奧數揭秘:二進位數定遊戲勝負

2016-07-06

看完上兩周的文章後,相信大家對拿取遊戲(Take-away Game或Nim)都提起了一定的興趣。這類遊戲相信是源於中國,發展至今在世界各地已有很多版本。

起初大家對這類遊戲的致勝之道都不大清楚,但隨蚍ずヴa們的研究,很多版本已可以透過數學方法獲得勝利。

下面的遊戲跟我們上兩周介紹過的「拿石子遊戲」很相似,讓我們一起看看:

將一堆石子排成三行,第一行、第二行及第三行分別有石子2顆、3顆及6顆。兩人輪流拿取石子,每人每次只可以在其中一行拿取石子,拿取石子的數目沒有限制,但每次必須至少拿取1顆。拿到最後一顆石子的為勝利者。

Nim-sum易計算

要解答上述問題,我們須做下列步驟。

第一步:將 2、3 及6化成二進位數,即是10、11及110。

第二步:將這三個二進位數對齊寫好,如下表所示。

第三步:要計算「Nim-sum」。Nim-sum的計算方法很簡單,在已對齊數位的二進位數直看,如果在同一直行上有單數個1,則在該直行寫上1;如果在同一直行上有雙數個1,則在該直行寫上 0,所以上述遊戲的Nim-sum為111。

保持0就贏

保證獲勝的方法很簡單,誰能夠將Nim-sum上所有的1,在拿取石子後全部消失或變成0 ,即是誰「將Nim-sum保持0」,誰就獲勝;而更重要的是,如果Nim-sum上已有1的出現,這種保證必勝的拿取方法就一定存在。換句話說,除非先拿者不懂方法,否則在這個設置下,這個遊戲一定是先拿者必勝。

讓我們看看二進位數的數位,由右至左計起,第三個直行只有一個1,這個1必須消失,而由此亦帶出了玩家必定要在第三行拿石子;第二個直行有三個1,這是單數個1,只要令這直行變成雙數個1,目的便可達到;第一個直行有一個1,但這個1卻在第二行出現,玩家無法在第三行拿取石子又能夠影響第二行石子的數目。

第一直行有兩個1便可

因此,玩家只好從第三行茪漶A在第三行最右的數位留一個1,使第一個直行有兩個1便可。綜合分析後,只要將第三行的110變成1,這就可以保證獲勝。

二進位數110代表十進位數的6,而二進位數1代表十進位數的1,即是要將第三行的石子數目由6變成1,先拿者只需在第三行拿取5顆石子便可,他只要繼續按「將Nim-sum保持 0」這個策略去拿取石子,必定獲勝。

那麼另一位玩家又如何呢?若他能夠「將Nim-sum保持0」,他豈不是也能獲勝嗎?不幸的是,當輪到這位玩家拿取石子時,若Nim-sum已經是0,那麼無論他怎樣拿取石子,之後的Nim-sum都必定有1出現,換句話說,他無法「將Nim-sum保持0」,基本上,他輸定了。

結 語

Nim-sum可以廣泛應用,亦包括上兩周的遊戲,不過上兩周的遊戲設置畢竟與本文所介紹的不同,Nim-sum的特性也稍有不同,尤其是應用在矩形上時,Nim-sum 只能作一個參考指標,而不是判斷勝負的唯一標準。

二進位數是高深的電腦數字系統,而一個普通的「拿石子的遊戲」的必勝策略竟然可以用二進位數來描述,這真令人驚訝!數學其中一個令人荌g的地方就是:表面上看似不相關的事情,卻往往隱藏玄妙關係!■蔡欣榆

簡介:香港首間提供奧數培訓之教育機構,每年舉辦奧數比賽,並積極開辦不同類型的奧數培訓課程。學員有機會獲選拔成為香港代表隊,參加海內外重要大賽。詳情可瀏覽:www.hkmos.org。

讀文匯報PDF版面

新聞排行
新聞圖片