2015年2月3日

必勝撿石頭

作者/游森棚(任教臺灣師範大學數學系及空軍官校)

這學期末,「離散數學」課進行的主題是「組合對局論(combinatorial game theory)」。課堂上我設計了許多兩人對弈遊戲,要同學找出必勝的方法。兩人對弈遊戲的基本設定是,甲、乙兩人輪流下,甲先開始。比如:

1. 一開始有16 顆石頭,每次可以拿走1、2、3或4顆石頭,拿光石頭的贏。請問誰有必勝策略?要怎麼玩?

2. 從「0」開始,每次可以加上2或3,先達到4、9或 12的獲勝。請問誰有必勝策略? 要怎麼玩?

講理論之前,我挑了幾個問題,讓全班同學捉對廝殺,看能不能從嘗試中發現必勝規則。競爭求勝是生物的本能,尤其「必勝法」是密技,實在太誘人了。於是課堂陷入一片混亂,全班興致高昂,討論非常熱烈。讀者可以先停下來,找個朋友玩個幾盤,看能不能找到必勝法。

聰明的同學就發現第一個問題的必勝法了,但是第二個問題的必勝法就需要一些思考。我們來從最簡單的情形開始慢慢摸索:一開始有3 顆石頭,每次可以拿走1、2顆石頭,拿光石頭的贏。誰必勝?

顯然乙必勝。因為甲拿1,乙就拿2; 甲拿2, 乙就拿1。而如果一開始有4顆石頭,則甲必勝(甲需先拿1);一開始有5顆石頭,甲也必勝(甲需先拿2)。從這裡可以看出來,留下3顆石頭是一個關鍵。

那麼一開始是6顆石頭呢?這時甲拿1、拿2都不對,所以乙必勝。依此模式思考下去,可以知道,能走到
K = {0, 3, 6, 9, ⋯}
的人就是必勝者。因為對手的下一步不管怎麼走,結果一定不是3的倍數。輪到我時, 又可以讓局面變成3的倍數。所以,如果一開始有7顆石頭,就要搶先手,先拿1顆。

同理,問題1的關鍵就是K= {0, 5, 10, 15},也就是這幾個點是必勝點:對手下完一定離開K,而我又一定可以回到K。既然一開始有16顆石頭,所以先手必勝,拿走1顆石頭即可。

把這個想法概念化,找必勝點就是要找一些棋局狀態,形成一個集合K,使得輪到我下時一定可以走進K,而對手時他只能走出K。......【更多內容請閱讀科學月刊第542期-購買

沒有留言: