文章節錄、翻譯、改寫自 這
- 共有三堆石頭，分別有
3, 4, 5顆。 - 只有兩個玩家。兩個玩家輪流拿石頭，每次拿石頭可以從三堆中任意一堆拿走不限數量的石頭，但不可以一顆石頭都不拿。
- 贏家為拿走最後一個石頭的人。
A 先拿；B 後拿。
| 第一堆 | 第二堆 | 第三堆 | 說明 |
|---|---|---|---|
| 3 | 4 | 5 | A 從第一堆拿走 2 顆石頭 |
| 1 | 4 | 5 | B 從第三堆拿走 3 顆石頭 |
| 1 | 4 | 2 | A 從第二堆拿走 1 顆石頭 |
| 1 | 3 | 2 | B 從第一堆拿走 3 顆石頭 |
| 1 | 0 | 2 | A 從第三堆拿走 1 顆石頭 |
| 1 | 0 | 1 | B 從第一堆拿走 1 顆石頭 |
| 0 | 0 | 1 | A 從第三堆拿走 1 顆石頭 |
| 0 | 0 | 0 | A 贏了 |
有時為了增加複雜度與可玩性，石頭可能不只三堆，石頭數也可能不是 3, 4, 5。但不管石頭有幾堆，事實上，存在著必勝策略：
每次拿石頭時，拿走能讓
Nim-sum變為0的石頭數。
Nim-sum為「第一堆石頭數 xor 第二堆石頭數 xor ... xor 第 n 堆石頭數」
首先，xor 有三個性質需注意：
1. N xor N = 0
2. N xor 0 = N
3. xor 滿足交換律與結合律
當前一個玩家拿完石頭後，
Nim-sum=0，那麼下一個玩家拿完石頭後，Nim-sum必不為0。
x[1], x[2], ..., x[n] 代表下一個玩家拿石頭前，各堆的石頭數。
此時 Nim-sum s = x[1] xor x[2] xor x[3] xor … xor x[n] = 0。
y[1], y[2], ..., y[n] 代表下一個玩家拿石頭後，各堆的石頭數。
其中，x 與 y 只差在第 k 項：y[k] ≠ x[k] ，其它項都一樣。
此時的 Nim-sum 假設為 t。
Nim sum t
= 0 xor t
= s xor s xor t
= s xor (x[1] xor x[2] xor … xor x[n]) xor (y[1] xor y[x] xor … y[n])
= s xor (x[1] xor y[1]) xor (x[2] xor y[2]) xor ... xor (x[n] xor y[n])
= s xor x[k] xor y[k]
= 0 xor x[k] xor y[k]
= x[k] xor y[k]
≠ 0
至此得證。
當前一個玩家拿完石頭後，
Nim-sum≠0，那麼下一個玩家拿石頭時，一定存在著某種拿法，使Nim-sum變為0。
x[1], x[2], ..., x[n] 代表下一個玩家拿石頭前，各堆的石頭數。Nim-sum s ≠ 0。
y[1], y[2], ..., y[n] 代表下一個玩家拿石頭後，各堆的石頭數。Nim-sum 假設為 t。
因為 s ≠ 0，所以存在 最高有效位（Most Significant Bit） （也就是 s 在 二進位 中，最左邊的 1，這裡使用的是 2's complement 表示法，s, t 都是非負整數），假設這個位置是 d。
而 x 陣列中必存在至少一個 x[k]，x[k] 有著與 s 相同的最高有效位，也就是說，x[k] 在二進位中，最左邊的 1 的位置也是 d。
（如果 x[k] 不存在，那麼在計算 s 時，s 怎麼可能在位置 d 上產生 1 呢？注意只有 1 xor 0 或 0 xor 1 才會是 1。0 xor 0, 1 xor 1 都 = 0）
於是，我們可以假設
(Wrong statement pointed out by alan23273850)y[k] = x[k] xor s，因為 x[k], s 有著相同的最高有效位，所以 y[k] 必定小於 x[k] ，因為在最高有效位上，1 xor 1 = 0。
而 x 陣列中必存在一個 x[k]，x[k] 的 d 位是 1。因為如果 x[k] 不存在，那麼在計算 s 時，s 怎麼可能在位置 d 上產生 1 呢？注意只有 1 xor 0 或 0 xor 1 才會是 1。0 xor 0, 1 xor 1 都 = 0
此時我們可以拿走第 k 堆中 x[k] - x[k] xor s 個石頭，也就是說讓第 k 堆石頭剩下 y[k] = x[k] xor s 個，新的 Nim-sum：
Nim-sum t
= s xor x[k] xor y[k] （引理1中的式子，即讓第 k 堆的石頭從 x[k] 變成 y[k]）
= s xor x[k] xor (x[k] xor s)
= 0
得證。
※ 我們可以保證 x[k] xor s 一定比 x[k] 小，因為 x[k] xor s 相當於將 x[k] 的 d 位改成 0，且 d 位以左值都不變（因為 d 位已是 s 的最高位），d 位以右怎麼變化是看 s 的值而定，但這不影響結論： xor 後的結果結果一定比 x[k] 小。
(1) 在遊戲中的任何階段，Nim-sum 要嘛 = 0 ，要嘛 ≠ 0。
(2) 當 Nim-sum = 0 時，根據引理1，下一個玩家拿完後，Nim-sum 必 ≠ 0。
(3) 之後換另一個玩家拿石頭時，根據引理2，總可以在拿完石頭後，使 Nim-sum = 0。
(4) 這就回到 (2) 了。之後遊戲會在 (2), (3) 之間不斷重覆。一個玩家不斷地使 Nim-sum ≠
0；一個玩家不斷地使 Nim-sum = 0。直到…
(5) 遊戲終止時，即每堆的石頭數都是 0 時，這是屬於 Nim-sum = 0的狀態。所以不斷地使 Nim-sum = 0 的那個玩家會拿走最後的石頭，也就是說，他贏了。
路人順手回覆，其實引理二之中的 >> 而 x 陣列中必存在至少一個 x[k]，x[k] 有著與 s 相同的最高有效位 << 這句話有點瑕疵，這樣子的 x[k] 並不一定存在，例如：
110001
100000
--------
010001
但是在這樣的情況之下我們仍能找到一個 y[k] = x[k] ^ s 而且 y[k] < x[k] 是因為只要 s 的最高位對到 x[k] 的 bit 也是 1 即可，那個 bit 不一定要是 x[k] 的最高位，但是我們一定能找到這樣的 x[k] 的原因其實就跟內文說的一樣，該位置必須至少有一個 1-bit 這樣全部 XOR 起來才會是 1，否則全 0 的 XOR 還是 0。
不過還是謝謝大大的文章，這篇寫得很棒，才讓我迅速理解～