A Midsummer Knot’s Dream 簡直可以說是去年學術界的一篇奇文,大家點進去看看就知道了。論文里講了一個基于紐結理論的雙人對弈游戲,名字也非常有藝術感: To Knot or Not to Knot 。這個游戲可能是最難的組合游戲了,它的數學性極強,思考難度非常大,甚至比 ERGO 更不容易上手。一場游戲下來,究竟誰贏誰輸可能都不好判斷。
To Knot or Not to Knot 的游戲規則非常簡單。用鉛筆在紙上畫一個封閉的、可以自相交的回路,然后 A 、 B 兩人輪流在圖形中選取一個尚未被處理過的交叉點,并用橡皮擦對圖形進行“細化”,明確兩根線條的位置關系(可以拋擲硬幣決定誰先行動)。A 的目的是要讓最終的圖形變成一個結,而 B 的目的則是避免圖形打結。下面是其中一種可能的游戲過程,雙方約定 B 先走。兩人輪流對交叉點進行細化,七步之后,整個圖形并未打結(你能看出來嗎), B 獲得勝利。
注意,這是一個決策透明、信息公開的游戲,并且游戲不可能有平局產生。因此,即使雙方都使出最佳策略,也必然有一個人會贏有一個人會輸。也就是說,任意給定一個初始狀態,總有一方有必勝的策略。不過,難就難在,究竟誰有必勝策略,必勝策略是什么,這并不容易判斷。讓我們來做一個練習題吧:下面的圖形中,如果 A 先走,B 后走,誰有必勝策略?如果 B 先走,A 后走呢?記住,A 的任務是要讓最終的圖形打成結,而 B 的任務則是避免圖形打結。
答案是,兩種情況下,后走的人都是必勝的。為了便于敘述,我們用 a 、 b 、 c 、 d 、 e 、 f 來標記圖中的六個交叉點。對于兩根線條連續兩次相交的地方,最終只可能是右圖所示的 I 、 II 、 III 、 IV 四種情形之一。我們把前兩種情形叫做“假交叉”,把后兩種情形叫做“真交叉”。
注意到,如果 B 能把 (e, f) 變成假交叉,那么不管下面四個交叉點是什么樣,整個圖形必然不打結。因此,如果 B 是后走的,那么 B 一定可以獲勝:一旦 A 動了 e 、 f 中的一個交叉點,那么 B 立即細化另一個交叉點,讓它成為假交叉;否則, B 就陪著 A 在下面四個交叉點中玩。但是,下面只有四個交叉點,是一個偶數,因而最終 A 將被迫對 e 或者 f 進行細化,從而宣告 B 的勝利。
如果 A 是后走的人呢? A 也將必勝。 A 可以把六個交叉點分成 (a, b) 、 (c, d) 、 (e, f) 三組,然后 B 細化了哪一個交叉點, A 也就跟著修改同組的另一個交叉點,從而決定每組交叉點的交叉類型。 A 可以把 (e, f) 變成真交叉,把 (a, b) 和 (c, d) 當中的一個也變成真交叉,另一個變成假交叉,這便能保證讓整個圖形打結(如圖 1)。需要注意的是,把下面兩組交叉變成一真一假,這是必需的。如果下面兩組都是假交叉,得到的圖形仍然沒有打結(如圖 2);而如果下面兩組都是真交叉的話,最終的圖形也不見得就一定是一個結(如圖 3)。