1、淺析Nim游戲武鋼三中吳豪一、引言Nim游戲是一個非常經典的組合游戲，它具有很強的趣味性與數學性，而且其 解法也蘊含了一些比較具冇啟發性的思維方式在本文中，我們將探討Nim游 戲屮滲透的些數學思想。席望讀者通過本文，能對Nim游戲仃更加深入的認 識.并能對其中的數學思想有進一步的體會。二、Nim游戲Nim游戲是一個由兩個玩家輪流進行的游戲：一開始，有n堆便幣，毎堆分別 有pl.72"枚硬幣。每個冋介，玩家都可以選擇一堆硬幣，并從中取走k枚 礎幣（KAfCnJ,取完最*枚碾幣的玩家獲得勝利。試問，對先玩家是 否有必勝策略？三、初步分析一開始拿到這個問題似乎毫無頭緒，我們就何IL先把問題

2、簡化，石慮“=2的悄 況經過兒番實驗之后.我們不難發現n=2時的規律：能否必勝，并不是看這 兩堆有多少個石子，而圧看這兩堆的石子數楚否相等。當兩堆的石子數不等 時.第一個玩家取出一定量的右使得這胸堆的右了數相等.接右冃要第 個 玩家從一堆中取出了k個石子.第一個玩家就模仿他住另一堆取出k個石子。如 此往父.第一個玩家-定可以獲得勝利。同樣.如果-開始兩堆的石子數相 第個玩家就可以完全模仿第一個玩家的操作以獲得勝利四、結論的抽彖與泛化在前一部分,我們分析了Nim游戲在n=2時的觀律與策略。但僅憑這個特例的 結論.還不足以解決一般的Nim游戲。因此.在這里我們需要對原結論進行 進-步抽象與泛化，來

3、給-般Nim游戲的解決提供切入點。我們不難注意到， 必勝判定的關鍵在于“狀態”，例如在n=2時,這個狀態就是“相等”與“不相等” > 而且這兩種狀態Z間在某種依賴關系，從而能給某個玩家的必勝制適 了契機。我們不妨設這兩個狀態分別為“V狀態衲和“L狀態” 那么這兩個狀態必然滿 足以下關系：條條條（目標狀態p Gy,無論如何操作V狀態都會變成L狀態、 一罡存在某種操作使得狀態L能變成狀態匕雪如在n=2的時候V狀態就是兩堆相等，L狀態就是兩堆不相等。日標狀態是兩 堆均為6是V狀態中的一種（條件1）。如果兩堆相等，從一堆中取出一些石 子，兩堆必然不等（條件2）如果兩堆的石子不等可以從多的一堆中取

4、出兩 堆的是值，使兩堆相等（條件3）。這兩種狀態Z間的邏輯關系如卜圖所示：這個圖很淸晰的反映rwifn提到的3個條件。圖中的三條邊表示了三種狀態轉移 的方式顯然，如果一個玩家不幸地要從v狀態出發.那么下一玩家會不斷 從L進向V,并獲得勝利。換句話說,如果一個玩家從L出發,只要每次從L走 向V即可獲得勝利。因而，沒有人會愿意從L走到L,因為這樣就把主動權讓給 了對手五、構造模型經過詢-部分的分析，我們（2經得到了必勝策略的邏輯模型。那么接著，我們 就需要為一般Nim游戲就身怎做一個符合以卜模糧的V狀態和L狀態。這里.我們不妨考慮把備堆分解為石子數為2.4,& 1G.21的子堆。顯然，最后

5、取完時， 每種子堆都是0個，即毎種子堆都仃偶數個。因此，我們猜想，是否可以令所仃 子堆數都為偶數時為V狀態？這里我們就來考察這種猜想是否滿足以上模醴的 其余兩個族本條件.為了方便起見，我們將所冇堆的石子數轉為2進制，令所冇 右子數在二進制時第i位上的數字Z利為 那么V狀態就是如為偶數，L狀態 就是日偽為奇數.先來看條件2：設玩家選擇第i堆令這堆石子數用:進制表示是久矢幾該:進制數與務位剩余T的數目如下:b、b2、63,、bi、bm9 q °2,如、,bm從P沖取出一些石子，則其對應進制數屮必然存在位®的值發工變化（否則 沒取）.那么該位上的數字和由（®-bj） +

6、 bj = aj變為口-心）+（1-如=（仃+1-2小 因為取之前是V狀態，冇©足偶數，故取定 Z后該位數字和© + 1-2®是奇數，轉變成了L狀態。因此無論玩家如何操 作.V狀態都只能轉移到L狀態。接著來看條件3:對于上述二進制數，由于當詢是L狀態，我們町以選擇一個最高的和為奇數的 數位J.然后任意選擇-堆該位為1的石子堆i.把這一位上的1改為山接著對于 低位，無論怎么改，都比原數小，因此我們一定叮以通過訓整低位便得毎-位上 的數字和均為偶數，所以我們一定可以通過取出一些石子，從L狀態轉移到V狀 態至此,我們已經說明了這種猜想的完備性。因此我們可以認為對于 般Nim問 題其必勝的判定，可以以石子數在二進制中每一位上1的個數的奇偶性為依 據。我們可以把Nim游戲的結論表述如卜：對于II堆石子PXP2Pn1.若pi xor p2 xor . pn = 0 （二進制每-位上的數字和足