由AMC10題目延伸出組合博弈論的經典問題

在本年的AMC10 B卷中，出現了一道背景較深刻的問題：

來看看機構的老師怎樣帶領我們(men) 破題：

 Kayles Game

事實上，此問題是組合博弈論當中的一個(ge) 經典問題：Kayles Game。它是Henry Dudeney在1908年發明的，最初是說擊打保齡球，而Kayles的發音與(yu) 法語“quilles”很接近，故後稱為(wei) Kayles Game。Kayles Game與(yu) Nim很類似，Nim指的是兩(liang) 個(ge) 玩家輪流從(cong) 不同的堆 ( piles ) 取走或移除物體(ti) 。

每一回合 ( round ) 每個(ge) 玩家必須移走至少一個(ge) 物體(ti) ，並且可以移除任意數量的物體(ti) ，隻要它們(men) 來自一堆。

事實上，組合博弈論有一個(ge) 非常重要的定理刻畫了這種相似性，也即著名的Sprague-Grundy定理。它陳述:“Every impartial game under the normal play convention is equivalent to a one-heap game of Nim, or to an infinite generalization of Nim.”（其中impartial指player 1與(yu) player 2之間唯一區別是輪次，而normal play convention指拿走最後一個(ge) 者判勝，one-heap指Nim中的一堆，在有限博弈中，大可以忽略infinite generation）。

使用Nim-value和Nim-sum的計算方法，我們(men) 可以遞歸地找到Kayles問題的Nim序列：

有了Nim-value，就可以知道所有Nim-sum非0的初始條件都是先手必勝，原因在於(yu) Kayles Game中若隻有一堆磚頭，先手可以造出鏡像局麵給後手從(cong) 而不敗。

而 ( B ) 中 ( 6 , 2 , 1 ) 的Nim-sum = 3 ⊕ 2 ⊕1 = 0

學會(hui) 了Nim方法和Sprague-Grundy定理後，老師為(wei) 大家留下了一道課後作業(ye) ，來試試看求如下遊戲的Nim值：

On a rectangular board, 2 players take turns placing dominoes either horizontally or vertically until no more dominoes (1×2) can be placed. The first player unable to make a move loses.

(Hint: 2×n board has a nimber of 0 for 2/n and nimber of 1 for 2+n)