Nim取子游戲是由兩個人面對若干堆硬幣（或石子）進行的游戲。設有k>=1堆硬幣，各堆分別含有N1，N2，……NK枚硬幣。游戲的目的就是選擇最后剩下的硬幣。游戲法則如下：
1．兩個游戲人交替進行游戲（游戲人I和游戲人II）；
2．當輪到每個游戲人取子時，選擇這些堆中的一堆，并從所選的堆中取走至少一枚硬幣（游戲人可以取走他所選堆中的全部硬幣）；
3．當所有的堆都變成空堆時，最后取子的游戲人即為勝者。
這個游戲中的變量是堆數k和各堆的硬幣數N1，N2，……Nk。對應的組合問題是，確定游戲人I獲勝還是游戲人II獲勝以及兩個游戲人應該如何取子才能保證自己獲勝（獲勝策略）。
為了進一步理解Nim取子游戲，我們考查某些特殊情況。如果游戲開始時只有一堆硬幣，游戲人I則通過取走所有的硬幣而獲勝。現在設有2堆硬幣，且硬幣數量分別為N1和N2。游戲人取得勝利并不在于N1和N2的值具體是多少，而是取決于它們是否相等。設N1！=N2，游戲人I從大堆中取走的硬幣使得兩堆硬幣數量相等，于是，游戲人I以后每次取子的數量與游戲人II相等而最終獲勝。但是如果N1= N2，則：游戲人II只要按著游戲人I取子的數量在另一堆中取相等數量的硬幣，最終獲勝者將會是游戲人II。這樣，兩堆的取子獲勝策略就已經找到了。
現在我們如何從兩堆的取子策略擴展到任意堆數中呢？
首先來回憶一下，每個正整數都有對應的一個二進制數，例如：57(10) à 111001(2) ，即：57(10)=25+24+23+20。于是，我們可以認為每一堆硬幣數由2的冪數的子堆組成。這樣，含有57枚硬幣大堆就能看成是分別由數量為25、24、23、20的各個子堆組成。
現在考慮各大堆大小分別為N1，N2，……Nk的一般的Nim取子游戲。將每一個數Ni表示為其二進制數（數的位數相等，不等時在前面補0）：
N1 = as…a1a0
N2 = bs…b1b0
……
Nk = ms…m1m0
如果每一種大小的子堆的個數都是偶數，我們就稱Nim取子游戲是平衡的，而對應位相加是偶數的稱為平衡位，否則稱為非平衡位。因此，Nim取子游戲是平衡的，當且僅當：
as + bs + … + ms 是偶數
……
a1 + b1 + … + m1 是偶數
a0 + b0 + … + m0是偶數
于是，我們就能得出獲勝策略：
游戲人I能夠在非平衡取子游戲中取勝，而游戲人II能夠在平衡的取子游戲中取勝。
我們以一個兩堆硬幣的Nim取子游戲作為試驗。設游戲開始時游戲處于非平衡狀態。這樣，游戲人I就能通過一種取子方式使得他取子后留給游戲人II的是一個平衡狀態下的游戲，接著無論游戲人II如何取子，再留給游戲人I的一定是一個非平衡狀態游戲，如此反復進行，當游戲人II在最后一次平衡狀態下取子后，游戲人I便能一次性取走所有的硬幣而獲勝。而如果游戲開始時游戲牌平衡狀態，那根據上述方式取子，最終游戲人II能獲勝。
下面應用此獲勝策略來考慮4-堆的Nim取子游戲。其中各堆的大小分別為7，9，12，15枚硬幣。用二進制表示各數分別為：0111，1001，1100和1111。于是可得到如下一表：
|
|
23 = 8
|
22 = 4
|
21 = 2
|
20 = 1
|
|
大小為7的堆
|
0
|
1
|
1
|
1
|
|
大小為9的堆
|
1
|
0
|
0
|
1
|
|
大小為12的堆
|
1
|
1
|
0
|
0
|
|
大小為15的堆
|
1
|
1
|
1
|
1
|
由Nim取子游戲的平衡條件可知，此游戲是一個非平衡狀態的取子游戲，因此，游戲人I在按獲勝策略進行取子游戲下將一定能夠取得最終的勝利。具體做法有多種，游戲人I可以從大小為12的堆中取走11枚硬幣，使得游戲達到平衡（如下表），
|
|
23 = 8
|
22 = 4
|
21 = 2
|
20 = 1
|
|
大小為7的堆
|
0
|
1
|
1
|
1
|
|
大小為9的堆
|
1
|
0
|
0
|
1
|
|
大小為12的堆
|
0
|
0
|
0
|
1
|
|
大小為15的堆
|
1
|
1
|
1
|
1
|
之后，無論游戲人II如何取子，游戲人I在取子后仍使得游戲達到平衡。
同樣的道理，游戲人I也可以選擇大小為9的堆并取走5枚硬幣而剩下4枚，或者，游戲人I從大小為15的堆中取走13枚而留下2枚。
歸根結底，Nim取子游戲的關鍵在于游戲開始時游戲處于何種狀態（平衡或非平衡）和第一個游戲人是否能夠按照取子游戲的獲勝策略來進行游戲。
posted on 2007-12-15 21:26
R2 閱讀(870)
評論(0) 編輯 收藏 引用 所屬分類:
Pure Theory