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