[翻譯]尼姆(複數堆棋子取子遊戲)的必勝法
翻譯
尼姆，又稱取子遊戲、移山遊戲。這個遊戲存在一種利用二進位計算的必勝方法。
尼姆的規則與例子
尼姆遊戲有許多不同的版本，而在這次解說會使用以下規則。
・兩人進行遊戲
・有複數個以數顆棋子組成的XXX
・玩家輪流從堆中取子。注意取子時一次只能從同一堆中拿取。每次至少要拿一顆，並沒有數量上限。
・拿取最後一顆子的玩家獲勝
接下來將會以(a, b, c)的形式表示各堆中的棋子數量。例如(3, 5, 7)就表示總共有三堆棋子，每堆各有3, 5及7顆子。並且以A, B代表兩名玩家。
例
起始狀態為(3, 5, 7)。
A從第一堆裡取出2顆子:剩(1, 5, 7)
B從第三堆裡取出全部7顆子:剩(1, 5)
A從第二堆裡取出4顆子:剩(1, 1)
B從第二堆裡取出1顆子:剩(1)
A 拿走最後一顆棋子並取得勝利
關於必勝狀態
為了說明尼姆遊戲的必勝法，必須要先定義這個遊戲的「必勝狀態」。
我們將以下的狀況稱為必勝狀態:
每堆棋子數量以二進位表示時，每位數的和全部都是偶數時
(也就是每位數異或計算後得到0時)
例1
將(2, 5, 7)以二進位表示時會是
10, 101, 111。將每位數加總會得到222(異或運算為000)，全部都是偶數，所以是必勝狀態。
例2
將(2, 3, 3)以二進位表示時會是
10, 11, 11，將每位數加總會得到32(異或運算為10)，結果存在奇數，所以不是必勝狀態。
我們又將這個異或運算結果10稱為(2, 3, 3)的尼姆和。
順帶一提，棋子只有兩堆的狀況下，
(a,
b)是必勝形時 ⟺ a = b。
各位可以自行確認看看。
尼姆必勝法的概略
尼姆遊戲存在必勝法。只要在自己回合結束時，讓場面維持在必勝狀態就一定能夠贏。
※說「必勝狀態」好像是在這個狀態下進行遊戲的一方有利，或許說是「必敗狀態」比較好，但為了說明方便還請見諒m(__)m
如果起始為「非必勝狀態」的話，只要按照以下方法，先手的玩家即可獲得勝利。
如果起始為「必勝狀態」時則相反，後手的玩家會獲勝。
從「非必勝狀態」開始的先手必勝法
1.
在「非必勝狀態」下只要調整拿取棋子的數量，就能讓場面成為「必勝狀態」，因此在自己回合結束時總是會讓場面成為「必勝狀態」。
2.
從「必勝狀態」下不論如何取子，都一定會讓場面成為「非必勝狀態」，因此對手的回合結束時場面都會是「非必勝狀態」。
3. 場面上沒有棋子的狀態(結束狀態)是「必勝狀態」，因此結束狀態理論上會在自己的回合後出現。
3很明顯是正確的，而1,
2必須要經過證明才能確認是否會順利運作。
但其實證明這兩點也十分容易。
證明必勝法
關於1:
我們想要藉由取子，讓在「所有棋子的尼姆和」中為1的位數反轉成0。而這件事可以通過選擇尼姆和最高位的同位數上，其數值為1的棋堆X來達成。
例
(2,
4, 5)時
(2, 4, 5)的二進位表示為(10, 100, 101)，尼姆和為011。因此只要取子的結果讓第1位和第2位反轉即可。
那麼要從哪堆棋子取走幾顆呢?
尼姆和的最高位數為第2位，所以要選擇第2位值為1的棋堆。也就是選擇「10」(棋子數量為2)那堆。
而讓想要反轉的位數(第1位和第2位)反轉後會變成01。也就是只要讓這堆棋子的數量n = 1就OK了。
總而言之，只要讓2顆子的棋堆數量n = 1的話就可以做出必勝狀態。
(我們選擇尼姆和最高位為1的棋堆，因此反轉後的數字n一定比原本棋子的數量還要小。也就是說，我們一定可以藉由取子讓棋堆X的數量變成n。)
關於2:
(因為不改動其他位數只變更一個位數時，所有位數的異或運算結果一定會變化，所以)不管如何取子尼姆和都會變化。因此只要從必勝狀態(=尼姆和為0的狀態)下取子，最後都會變成「非必勝狀態」。
※在頭腦王節目中登場的遊戲規則是取走最後一顆棋子的人敗北。但依然可以用相同的法則作為必勝法。
留言
張貼留言