1  2  3  4  5   Contents

豆芽遊戲 (Sprouts)

Brussels Sprouts

        在豆芽遊戲(Sprouts)之後,康威又發明了一個類似的遊戲,取名為Brussels Sprouts,不過這個遊戲很奸詐,不知內情的人會被耍得團團轉。

        Brussels Sprouts的玩法與豆芽遊戲類似,只是把點改成了小十字符號。一開始紙上有n個小十字符號,然後兩個人輪流在圖中加上一條線(線的兩端可以連接兩個小十字符號,也可以連在同一個十字符號上),並在新增的線上加上一個小十字符號。加上的這條線不能穿過自己,或其他之前畫好的線與小十字符號。當然,每個小十字符號最多只能連出4條線(稱為4條自由手臂)。當這個圖再也無法加線的時候,遊戲結束。一般的玩法,畫到最後一條線的人獲勝,當然,也可以做相反規定:畫到最後一條線的人落敗。

        這個遊戲似乎比豆芽遊戲還複雜,而且有可能出現一直可以加線的情形,因為每加一條線,雖然會用掉2條自由手臂,但是在線上加的十字又帶來了兩條新自由手臂,所以這個遊戲的自由手臂永遠不會減少,那麼遊戲還會有結束的一天嗎?但實際上,這個遊戲一定會在加上第5n – 2條線時結束,也就是說,當n是奇數,一定是先玩的人畫到最後一條線;若n是偶數,一定是後玩的人贏。

 

以下是一個開始時為兩個小十字符號的例子:

 

 

開始

 

第一步

 

第二步

 

 

 

 

 

 

 

第三步

 

第四步

 

第五步

 

 

 

 

 

 

 

第六步

 

第七步

 

第八步

 

        多玩幾次Brussels Sprouts之後,你有沒有發現:n個十字開始的遊戲,結束時會是一個有4n個面的平面圖。一開始給n個十字的話,就有4n條自由手臂,而且前面提過在遊戲過程中,自由手臂的數目不會增加也不會減少。當遊戲結束時,在同一個面中當然不會有2條自由手臂同時存在,否則這個遊戲還是可以繼續下去。另一方面,在每一個面裡一定會有一條自由手臂,因為你每拉一條邊切出一個新的面時,都會在那條邊上加一個十字,於是與這條邊相鄰的兩個面都多出了一條自由手臂。所以,在遊戲結束時,面的數目會與自由手臂的數目相同(每個面裡要有一條手臂),也就是4n

        我們假設遊戲是在加上第x條線時結束,並將一開始的每個十字視為5個點與4條邊的組合,以後每加一條線與一個小十字符號則看成是增加3個點與4條邊。如下圖是一個開始時是2個小十字符號的情況:

 

開始

V = 10

E = 08

 

第一步

V = 13

E = 12

        一開始如果有n個十字符號,在加上第x條線之後,就得到5n + 3x個點,4n + 4x條邊,以及4n個面。如果這個遊戲結束時是一個連通圖,將V = 5n + 3x,  E = 4n + 4x,  F = 4n代入尤拉公式:

(5n + 3x) + (4n) = (4n + 4x) + 2
9n + 3x = 4n + 4x + 2
x = 5n – 2

我們得出Brussels Sprouts的確會在加上第5n – 2條線時結束。

        現在我們回過頭來想想,有沒有可能這個遊戲結束時並不是一個連通圖呢?如果這種情況發生的話,以上的證明就不適用了。但是我們可以證明這個遊戲結束時的確是一個連通圖。假設最後的結果不是連通圖,就去看它的每一個連通部分(connected component),每個連通部分所包含的每個面都有一條手臂,但是再把這些連通部分合起來看,會發現這些連通部分最外面的面其實是同一個面,所以這個面中就有不只一條手臂,則遊戲可以繼續,與假設說它是一個遊戲結果矛盾。

 

Previous   Contents