amoshyc/nim_game_classic.md

## nim_game_classic.md

      
    Raw
  

              nim_game_classic.md
            
          
    Nim Game

文章節錄、翻譯、改寫自 這
玩法


共有三堆石頭，分別有 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 滿足交換律與結合律


引理 1


當前一個玩家拿完石頭後，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

至此得證。

引理 2


當前一個玩家拿完石頭後，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）
於是，我們可以假設 y[k] = x[k] xor s，因為 x[k], s 有著相同的最高有效位，所以 y[k] 必定小於 x[k] ，因為在最高有效位上，1 xor 1 = 0。
(Wrong statement pointed out by alan23273850)
而 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 的那個玩家會拿走最後的石頭，也就是說，他贏了。
第一堆	第二堆	第三堆	說明
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 贏了