1.12 NIM（2）“拈”游戲分析

我們再來看一個類似的游戲。

有N塊石頭和兩個玩家A和B，玩家A先將石頭分成若干堆，然后按照BABA……的順序不斷輪流取石頭，能將剩下的石頭一次取光的玩家獲勝（如圖1-20所示）。每次取石頭時，每個玩家只能從若干堆石頭中任選一堆，取這一堆石頭中任意數(shù)目（大于0）個石頭。

請問：玩家A要怎樣分配和取石頭才能保證自己有把握取勝？

分析與解法

據(jù)說，該游戲起源于中國，經(jīng)由當(dāng)年到美洲打工的華人流傳出去。它的英文名字“NIM”是由廣東話“拈”（取物之意）音譯而來。這個游戲一個常見的變種是將12枚硬幣分三列排成[3, 4, 5]再開始玩。我們這里討論的是一般意義上的“拈”游戲。

言歸正傳，在面試者咄咄逼人的目光下，你要如何著手解決這個問題？

在面試中，面試者考察的重點不是“what”——能否記住某道題目的解法，某件歷史事件發(fā)生的確切年代，C++語言中關(guān)于類的繼承的某個規(guī)則的分支等。面試者很想知道的是“how”——應(yīng)聘者是如何思考和學(xué)習(xí)的。

所以，應(yīng)聘者得展現(xiàn)自己的思路。記得在上一節(jié)“NIM（1）一排石頭的游戲”中，我們提到了解答這類問題應(yīng)從最基本的特例開始分析。我們不妨再試一下，我們用N表示石頭的堆數(shù)，M表示總的石頭數(shù)目。

當(dāng)N=1時，即只有一堆石頭——顯然無論你放多少石頭，你的對手都能一次全拿光，你不能這樣擺。

當(dāng)N=2時，即有兩堆石頭，最簡單的情況是每堆石頭中各有一個石子（1, 1）——先讓對手拿，無論怎樣你都可以獲勝。我們把這種在雙方理性走法下，你一定能夠贏的局面叫作安全局面。

當(dāng)N=2, M > 2時，既然（1, 1）是安全局面，那么（1, X）都不是安全局面，因為對手只要經(jīng)過一次轉(zhuǎn)換，就能把（1, X）變成（1, 1），然后該你走，你就輸了。既然（1, X）不安全，那么（2, 2）如何？經(jīng)過分析，（2, 2）是安全的，因為它不能一步變成（1, 1）這樣的安全局面。這樣我們似乎可以推理（3, 3）、（4, 4），一直到（X, X）都是安全局面。

于是我們初步總結(jié)，如果石頭的數(shù)目是偶數(shù)，就把它們分為兩堆，每堆有同樣多的數(shù)目。這樣無論對手如何取，你只要保證你取之后是安全局面（X, X），你就能贏。

如果石頭數(shù)目是奇數(shù)個呢？

當(dāng)M=3的時候，有兩種情況，（2, 1）、（1, 1, 1），這兩種情況都會是先拿者贏。

當(dāng)M=5的時候，和M=3類似。無論你怎么擺，都會是先拿者贏。

若M=7呢？情況多起來了，頭有些暈了，好像也是先拿者贏。

我們在這里得到一個很重要的階段性結(jié)論：

當(dāng)擺放方法為（1, 1, …, 1）的時候，如果1的個數(shù)是奇數(shù)個，則先拿者贏；如果1的個數(shù)是偶數(shù)個，則先拿者必輸。

當(dāng)擺放方法為（1, 1, …, 1, X）（多個1，加上一個大于1的X）的時候，先拿者必贏。因為：

如果有奇數(shù)個1，先拿者可以從（X）這一堆中一次拿走X-1個，剩下偶數(shù)個1——接下來動手的人必輸。

如果有偶數(shù)個1，加上一個X，先拿者可以一次把X都拿光，剩下偶數(shù)個1——接下來動手的人也必輸。

還有其他的各種擺法，例如當(dāng)M=9的時候，我們可以擺為（2, 3, 4）、（1, 4, 4）、（1, 2, 6），等等。這么多堆石頭，它們既互相獨立，又互相牽制，那如何分析得出致勝策略呢？關(guān)鍵是找到在這一系列變化過程中有沒有一個特性始終決定著輸贏。這個時候，就得考驗一下真功夫了，我們要想想大學(xué)一年級數(shù)理邏輯課上學(xué)的異或（XOR）運算。異或運算規(guī)則如下：

XOR（0, 0）=0

XOR（1, 0）=1

XOR（1, 1）=0

首先我們看整個游戲過程，從N堆石頭（M1, M2, …, Mn）開始，雙方斗智斗勇，石頭一直遞減到全部為零（0, 0, …, 0）。

當(dāng)M為偶數(shù)的時候，我們的取勝策略是把M分成相同的兩份，這樣就能取勝。

類似的，若M為奇數(shù)，把石頭分成（1, 1, …,1）奇數(shù)堆時，XOR（1, 1, …,1）[奇數(shù)個] !=0。而這時候，對方可以取走一整堆，XOR（1, 1, …, 1）[偶數(shù)個]=0，如此下去，我方必輸。

我們推廣到M為奇數(shù)，但是每堆石頭的數(shù)目不限于1的情況，看看XOR值的規(guī)律：

不幸的是，可以看出，當(dāng)有奇數(shù)個石頭時，無論你如何分堆，XOR（M1,M2,…, Mn）總是不等于0！因為必然會有奇數(shù)堆有奇數(shù)個石頭（二進制表示最低位為1），異或的結(jié)果最低位肯定為1。[結(jié)論1]

再不幸的是，還可以證明，當(dāng)XOR（M1,M2, …, Mn）!=0時，我們總是只需要改變一個Mi的值，就可以讓XOR（M1,M2,…, Mi', …,Mn）=0。[結(jié)論2]

更不幸的是，又可以證明，當(dāng)XOR（M1,M2,…,Mn）=0時，對任何一個M值的改變（取走石頭），都會讓XOR（M1,M2,…Mi', …,Mn）!=0。[結(jié)論3]

有了這3個“不幸”的結(jié)論，我們不得不承認，當(dāng)M為奇數(shù)時，無論怎樣分堆，總是先動手的人贏。

還不信？那我們試試看：當(dāng)M=9，隨機分堆為（1,2,6）：

B先動手：（1, 2, 3），即從第三堆取走三個，得到（1,2,3）

好了，通過以上的分析，我們不但知道了這類問題的答案，還知道了游戲的規(guī)律，以及如何才能贏。XOR，這個我們很早就學(xué)過的運算，在這里幫了大忙。我們應(yīng)該對XOR說Orz才對！

有興趣的讀者可以寫一個程序，返回當(dāng)輸入為（M1, M2, …, Mn）的時候，到底如何取石頭，才能有贏的可能。比如，當(dāng)輸入為（3, 4, 5）的時候，程序返回（1, 4, 5）——這樣就轉(zhuǎn)敗為勝了！

擴展問題

1．如果規(guī)定相反，取光所有石頭的人輸，又該如何控制局面？

2．如果每次可以挑選任意K堆，并從中任意取石頭，又該如何找到必勝策略呢？