二進位遊戲
_
拈
(Nim)
單堆遊戲是拈的遊戲中較簡單的一種。據說，拈的遊戲源自中國，經由被 販賣到美洲的奴工外傳。所以這個小遊戲先在工人間流行，他們就地取材撿小石 子來玩。後來流傳到上流人士，改以銅板在酒吧櫃檯上玩。最有名的玩法是將十 二枚銅板分三列排成「三、四、五」的遊戲，如下圖：
遊戲的規則很簡單：兩人輪流取銅板，每次需在某一列取一枚或一枚以上 的銅板，但不能同時在兩列取銅板，最後將銅板拿光的人贏得此遊戲。（或是相 反的情形：最後將銅板拿光的人輸。）
讓我們先看二列的例子：
假設甲先取，乙後取，甲如何可取得勝利？
我們先注意到，甲若欲取勝，就得避免將某一列完全取光，否則對方可全 取剩下的一列，而拿到最後一枚銅板。
1.
<
甲勝
>
2.
b.
<
甲勝
>
3.
a. <甲勝>
b. <甲勝>
c. <甲勝>
4.
a. <甲勝>
b. <甲勝>
c. <甲勝>
d. <甲勝>
由 1~ 4，我們可以推得，甲若留下兩列枚數相同的銅板給乙，甲必可獲勝。反 之乙若留下兩列枚數相同的銅板給甲，乙必可獲勝。
抓到兩列的訣竅之後，再來看看三列的情況：
假設甲先取，乙後取，甲如何可取得勝利？
1. <由二列的情形得
知，乙勝>
2. <由二列的情形得
知，乙勝>
3. <由二列的情形得
知，乙勝>
由 1 ~ 3 可推得，若甲欲贏得勝利，就必需避免在留下的三列銅板中，有兩列 的銅板數相同。
此外，甲取完之後三列的銅板數若分別剩下
1, 2, 3
，則甲勝。
4.
b. <甲勝> (一三列相同)
c. <甲勝>
d. <甲勝> (一二列相同)
e. <甲勝>
f. <甲勝>
多玩幾次之後，大家可以發現一開始若甲在第一列取二枚，可取得勝利。
5.
a. <甲勝>
c. <甲勝>
d. <甲勝> (一
二列相同)
e. <甲勝>
f. <甲勝> (二
三列相同)
g. <甲勝>
h. <甲勝>
i. <甲勝> (一
三列相同)
j. <甲勝>
一般法則與二進位
玩久了「三、四、五」的型態，很容易便知道勝利的關鍵是什麼，玩起來也 沒什麼意思。所以可以將銅板的列數或每一列的銅板數改變，這樣要找出所有規 律就不太容易了。
直到本世紀初，哈佛大學數學系副教授查理士．理昂納德．包
頓 (Charles Leonard Bouton) 才利用數的二進位表示法，解出了這個遊戲 的一般法則：
對於任意列數，每列有任意枚數的銅板，致勝之道為何？包頓的
方法很簡單。首先，將各列的銅板數化成二進位數，然後相加，但不進
位。換句話說，就是
1 + 0 = 1 0 + 1 = 1 1 + 1 = 0 0 + 0 = 0
再看一個例子：
1 + 1 + 1 = (1 + 1) + 1 = 0 + 1 = 1
於是我們知道：偶數個1相加會得到0，奇數個1相加會得到1。
如果遊戲規則為：最後將銅板拿光的人贏得遊戲。各列的銅板數化成二進 位數相加之後（不進位）的每一位數都是0的狀況為安全殘局；相反地，只要 其中有任何一位數是1，就是不安全殘局。
一般情形之下，將不安全殘局轉變成安全殘局的方法常常不只一種，如下：
為什麼安全殘局和不安全殘局可以利用上述的方法判定呢？這可以分成幾 個部分來看：
2. 相反的，如果總和的某一位數是1，我們總有辦法在適當的列取走適當 枚數的銅板，使得新總和的每一位數都是0。
a. 首先，找出總和中所有是1的位數 其中 ；
在之前提到的例子{ 14, 15, 18, 22 }中， ={ 1, 3}；也就是說，總和的
第1位與第3位都是1。
b. 找出一列其銅板數之（二進位表示法）第 位數（也就是最左邊
c. 接著改變該列二進位數中的所有 （ ）位數值，亦即將
0變為1，將1變為0。如此，我們會得到一個新數；以14（第一 列）為例，14 = 1110，將其第1位與第3位改變，便得到1011 = 11枚銅板。
利用上面的方法，我們可以在該列中取走適當的銅板，使剩下的銅板數二 進位總和的每一位數都是0；例如，在第一列取走14 – 11 = 3枚銅板。
從以上的例子，你應該可以發現，前面幾步中，甲乙都可以留下自己的安 全殘局，直到後來出現有某一列的銅板數大於1，而其他列都只剩一枚的情況。 這時輪到甲來取，甲如何取就是勝負的關鍵：甲可以選擇將較多枚銅板的那一 列拿光，或拿到只剩一枚。在這個例子中，甲選擇將該列拿到只剩一枚，因為這 樣才能使剩下的列數為“奇數”，當然每一列均只有一枚銅板。顯而易見的是， 以後一人取一列，到最後拿的一定是乙，於是甲必勝。
