王姿婷 李建華

(1 海南省文昌中學(xué) 571300；2北京師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院 數(shù)學(xué)與復(fù)雜系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室 100875)

1 前言

與眾多經(jīng)典的數(shù)學(xué)游戲一樣，NIM型游戲的趣味性與挑戰(zhàn)性如此濃厚，以至于得到各領(lǐng)域數(shù)學(xué)研究者及愛好者的關(guān)注，首先它作為博弈游戲的一員，在博弈論、圖論中常被提及，它在集合論、組合數(shù)學(xué)中也占據(jù)較重要的位置.眾多相關(guān)文獻(xiàn)或聲勢浩大的占據(jù)整章的篇幅(如法國數(shù)學(xué)家C.Berge所著的《The Theory of Graphs and Its Applications》專門在第六章對(duì)NIM型游戲?qū)Σ叩难芯?，或?qū)⒂螒螂[匿在浩繁的文字中，對(duì)游戲與相關(guān)理論了解不夠深入者，多會(huì)因其近乎純數(shù)學(xué)的嚴(yán)肅外表看不真切NIM型游戲的輪廓.下面，我們對(duì)現(xiàn)代數(shù)學(xué)視角下NIM型游戲做一個(gè)導(dǎo)引式的介紹與分析.

2 NIM型游戲

2.1 NIM型游戲與圖論

Sprange-Grundy值介紹

包括經(jīng)典NIM游戲在內(nèi)的許多的NIM型游戲，通常可以用一種稱之為“Sprange-Grundy值”予以分析，所謂的“Sprange-Grundy值”實(shí)際上是一種狀態(tài)函數(shù)：

SG(p,q,…,r)=f(p,q,…,r)

例如經(jīng)典NIM游戲中石子全部被取完的狀態(tài)的“Sprange-Grundy值”為SG(0,0,…,0)=0.我們規(guī)定：凡使“Sprange-Grundy值”為0的狀態(tài)為平衡狀態(tài).

假定甲將局勢拿取成了(p,q,…,r)，而SG(p,q,…,r)>0，接下來輪到乙拿取，如乙拿取成了(p′,q′,…,r′)，如果乙有辦法讓SG(p′,q′,…,r′)=0，那么乙就占據(jù)了平衡狀態(tài)這一有利局勢，接下去乙步步為營，每次都占據(jù)平衡狀態(tài)，直至狀態(tài)變?yōu)?0,0,…,0).

當(dāng)然，f(p,q,…,r)函數(shù)不特指哪個(gè)函數(shù)，不同的游戲有不同的SG(p,q,…,r)求法，而函數(shù)f(p,q,…,r)的選取有相當(dāng)?shù)募记?例如：

在堆數(shù)為1的經(jīng)典NIM游戲中(有一堆石子，數(shù)量為n，甲乙兩人輪流從這堆石子中取走一些石子 ，每人每次最多取走m個(gè)(m

在堆數(shù)大于1的經(jīng)典NIM游戲中，也可知此時(shí)函數(shù)f(p,q,…,r)應(yīng)選取為f(p,q,…,r)=(p,q,…,r)Nim，此處的(p,q,…,r)Nim即為先前定義過的“NIM和”.

“穆爾”游戲中(與NIM游戲的規(guī)則基本相同，唯一有區(qū)別的地方是：玩家的每一步，可以從任意不超過k堆中取石子)，類似于NIM游戲，函數(shù)f(p,q,…,r)應(yīng)選取為f(p,q,…,r)=(p,q,…,r)Nim k,而這里的(p,q,…,r)Nim k就是先前定義過的“NIMk和”.

與圖論的聯(lián)系分析

首先，在圖論中，我們可以將經(jīng)典NIM游戲中的每一局勢看做一個(gè)頂點(diǎn)，而每一個(gè)頂點(diǎn)與其后繼局面的頂點(diǎn)以邊相互連接，這樣一來，從初始局勢開始，所有的局面就構(gòu)成了一個(gè)由若干個(gè)頂點(diǎn)以及連接這些頂點(diǎn)的有向邊所組成的圖，并且，每兩個(gè)頂點(diǎn)之間至多可以有一條有向邊將它們連接起來.將所有的頂點(diǎn)集合記為P，所有的有向邊集合記為E，則整個(gè)游戲的所有狀態(tài)組合起來便可對(duì)應(yīng)一個(gè)有向圖G(P,E).若有一條有向邊e0，從p0出發(fā)，指向p1，則p0與p1是鄰接的，且稱p1為p0的后繼頂點(diǎn)，對(duì)于某個(gè)頂點(diǎn)pi∈P，記其所有后繼頂點(diǎn)的集合為H(pi).

事實(shí)上，這些頂點(diǎn)與之前的局勢數(shù)組是一一對(duì)應(yīng)的，例如(a1,a2,…,ai,…,an)是某一個(gè)局勢，而且后繼頂點(diǎn)即為(a1,a2,…,bi,…,an)便為它的一個(gè)可以指向的局勢，其中bi

回到圖中討論游戲，若當(dāng)前的局面為頂點(diǎn)p0，下一位游戲者只能在H(p0)中選擇一個(gè)頂點(diǎn)，而H(pj)=?即為游戲結(jié)束的標(biāo)志，在經(jīng)典NIM游戲以及其他不允許不進(jìn)行任何操作的NIM型游戲中，這個(gè)圖的任意一條邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)不可能重合，即不會(huì)出現(xiàn)環(huán).

顯然，尋找游戲的平衡狀態(tài)，就轉(zhuǎn)變成了尋找圖中這樣一個(gè)頂點(diǎn)集W?P，它滿足：

(1)若pi∈W，則H(pi)∩W=?;

(2)若pi?W，則H(pi)∩W≠?.

第一條性質(zhì)對(duì)應(yīng)著“必破性”，第二條性質(zhì)對(duì)應(yīng)著“還原性”.此時(shí)的“Sprange-Grundy值”可按以下方式計(jì)算：首先定義一個(gè)函數(shù)SG(x)，它是圖的頂點(diǎn)集P到非負(fù)整數(shù)集N的一個(gè)映射，此時(shí)的SG(pi)=mex{SG(pj)|pj∈H(pi)}，其中mex(K)=min{d|d∈N∧d?K}，若H(pj)=?則SG(pj)=0.可以看到，這個(gè)函數(shù)SG(x)是一個(gè)遞歸函數(shù).

由之前的分析我們知道，經(jīng)典NIM游戲的圖中一定會(huì)有頂點(diǎn)集W的存在，而且W={pi|SG(pi)=0}，這是因?yàn)?，從SG(pi)定義中所用的函數(shù)mex(K)，我們可以知道，若SG(pi)=0，則任意一個(gè)后繼頂點(diǎn)pj∈H(pi)，都有SG(pj)≠0，即H(pi)∩W=?成立，且若SG(pj)≠0，定是由于存在pj的一個(gè)后繼頂點(diǎn)pk∈H(pj)，使得SG(pk)=0，即H(pj)∩W≠?成立.這樣一來，只需依次占據(jù)頂點(diǎn)pi和pj，并在之后如法炮制即可在步數(shù)有限時(shí)取得勝利.

此處例舉局勢(1,2,3)的“Sprange-Grundy值”的計(jì)算過程，以便于讀者對(duì)上述函數(shù)SG(x)的理解.首先我們按照自然順序，逐一建立如下的圖的頂點(diǎn)與局勢數(shù)組之間的對(duì)應(yīng)：

p1→(0,0,0)，p2→(0,0,1)，p3→(0,1,1)，p4→(0,0,2)，p5→(0,1,2)，p6→(1,1,1)，p7→(1,1,2)，p8→(0,2,2)，p9→(1,2,2)，p10→(0,0,3)，p11→(0,1,3)，p12→(0,2,3)，p13→(1,1,3)，p14→(1,2,3).

可以推知各頂點(diǎn)的后繼頂點(diǎn)集合為：

H(p1)=?；H(p2)={p1}；H(p3)={p2}；

H(p4)={p1,p2}；H(p5)={p2,p3,p4}；H(p6)={p3}；H(p7)={p3,p5,p6}；H(p8)={p4,p5}；H(p9)={p5,p7,p8}；H(p10)={p1,p2,p4}；H(p11)={p2,p3,p5,p10}；H(p12)={p4,p5,p8,p11}；H(p13)={p3,p6,p7,p10,p11}；H(p14)={p5,p7,p9,p11,p12,p13}；

這些頂點(diǎn)所構(gòu)成的有向圖，局部如圖1所示，完整圖見圖2，可見這樣對(duì)應(yīng)出來的圖是沒有有向回路的，可以看出，這是一個(gè)連通的有向圖，但不是強(qiáng)連通的.

圖 1

圖 2

因?yàn)镾G(p1)=0，故

SG(p2)=mex{SG(p1)}=mex{0}=1,

SG(p3)=mex{SG(p2)}=mex{1}=0,

SG(p4)=mex{SG(p1),SG(p2)}

=mex{0,1}=2,

SG(p5)=mex{SG(p2),SG(p3),SG(p4)}

=mex{1,0,2}=3,

SG(p6)=mex{SG(p3)}=mex{0}=1,

SG(p7)=mex{SG(p3),SG(p5),SG(p6)}

=mex{0,3,1}=2,

SG(p8)=mex{SG(p4),SG(p5)}

=mex{2,3}=0,

SG(p9)=mex{SG(p5),SG(p7),SG(p8)}

=mex{3,2,0}=1,

SG(p10)=mex{SG(p1),SG(p2),SG(p4)}

=mex{0,1,2}=3,

SG(p11)=mex{SG(p2),SG(p3),SG(p5),SG(p10)}=mex{1,0,3,3}=2,

SG(p12)=mex{SG(p4),SG(p5),SG(p8),SG(p10),SG(p11)}=mex{2,3,0,3,2}=1,

SG(p13)=mex{SG(p3),SG(p6),SG(p7),SG(p11)}=mex{0,1,2,2}=3,

SG(p14)=mex{SG(p5),SG(p7),SG(p9),SG(p11),SG(p12),SG(p13)}=mex{3,2,1,2,1,3}=0.

觀察各頂點(diǎn)的“Sprange-Grundy值”，為0的頂點(diǎn)所對(duì)應(yīng)的局勢，正好是之前所分析過的有利局勢，而剩余的都是不利局勢，其“Sprange-Grundy值”都不為0！

值得一提的是，Sprange-Grundy函數(shù)是為了研究NIM而引入的，但之后的發(fā)展，遠(yuǎn)不止NIM本身的內(nèi)涵性詮釋.其中SG-組合游戲[注]賈志豪.組合游戲略數(shù)—淺談SG游戲的若干拓展及變形[J]國家集訓(xùn)隊(duì)2009論文就是其一.

SG-組合游戲的介紹

這類游戲若有如下特征便可稱為SG-組合游戲：

?游戲有兩個(gè)參與者，記為A和B，二者在游戲過程中輪流作出決策；

?游戲的所有位置構(gòu)成集合P，游戲的規(guī)則為由P→P的多值映射H；

?同一個(gè)游戲位置，不可能多次到達(dá)；

?當(dāng)一方無法作出決策時(shí)游戲結(jié)束，且判決輸贏，游戲不會(huì)出現(xiàn)平局.

這類游戲都可以用Sprange-Grundy函數(shù)進(jìn)行解決.若同時(shí)進(jìn)行多個(gè)SG-組合游戲，它們的總和也構(gòu)成了一個(gè)SG-組合游戲，它包含多個(gè)單一的游戲，游戲者可以任意挑選其一進(jìn)行決策，換個(gè)意義說，這些單一的游戲成了總游戲的子游戲.

對(duì)應(yīng)到圖論中，我們就可以將總的SG-組合游戲?qū)?yīng)為總圖G(P,E)，各個(gè)子游戲的圖Gi(Pi,Ei)便為總圖G(P,E)的分支，總圖G(P,E)的分支數(shù)就為它所包含的單一游戲的數(shù)目.

總游戲的Sprange-Grundy函數(shù)值就是各個(gè)子游戲的Sprange-Grundy函數(shù)值的異或和：SG=SG1⊕SG2⊕…⊕SGn.

Sprange-Grundy函數(shù)值在以最終誰拿完算贏的游戲中的使用方式之前已討論，現(xiàn)在借此函數(shù)再研究以最終取完為輸?shù)腟G-組合游戲，之前研究過以取完為輸?shù)慕?jīng)典NIM游戲，此處推而廣之到所有符合定義的SG-組合游戲，當(dāng)然，此時(shí)游戲規(guī)定，決策集合為空的游戲者勝利.

我們直接介紹由賈志豪給出的結(jié)論SJ定理：

在決策集合為空的游戲者算勝利的SG-組合游戲中，先手必勝當(dāng)且僅當(dāng)：

(1)總游戲的Sprange-Grundy函數(shù)值不為0且游戲中某個(gè)單一游戲的Sprange-Grundy函數(shù)值大于1；

(2)總游戲的Sprange-Grundy函數(shù)值等于0且游戲中沒有一個(gè)單一游戲的Sprange-Grundy函數(shù)值大于1.

該定理的論證過程不在本文討論范圍，感興趣的讀者可自行查閱.

回頭看看這些游戲描述及策略分析，經(jīng)典NIM游戲原有的面貌已全然看不出來，這儼然只是圖論中一些決策游戲！但是其實(shí)我們?nèi)绻紤]到，經(jīng)典NIM游戲中允許的操作是從一堆中拿走一定量的石子，那么，k堆的經(jīng)典NIM游戲共同構(gòu)成的總游戲所對(duì)應(yīng)的圖就可以看成每一堆自成的圖的累加了，也就是說，總圖可以劃分為k個(gè)子圖的合成，即分別擁有頂點(diǎn)集P1,P2,…,Pk的圖G1,G2,…,Gk做直和組成了k堆NIM游戲的總圖，其中，總圖的頂點(diǎn)集

P={(p1,p2,…,pk)|pi∈Pi,1≤i≤k}；

邊由其后繼H(P)={(p1,p2,…,pi,…,pk)|pi∈H(Pi),1≤i≤k}可以給出；符號(hào)記作是G=G1⊕G2⊕…⊕Gk，由之前的定義，我們可以知道，這也是一個(gè)NIM型游戲.另外，許多基于圖上的操作游戲如刪邊游戲，也能與NIM型游戲產(chǎn)生聯(lián)系.

2.2 NIM型游戲與組合數(shù)學(xué)三元系

觀察到，在堆數(shù)為3的經(jīng)典NIM游戲中，每三個(gè)數(shù)構(gòu)成一個(gè)的數(shù)組，更特殊的是，在所找出的制勝策略里頭，任意一對(duì)數(shù)字都能出現(xiàn)且只出現(xiàn)在一個(gè)三元數(shù)組里頭！這不禁讓我們想起設(shè)計(jì)指標(biāo)λ=1的區(qū)組設(shè)計(jì)，又因?yàn)槊恳唤M的元素個(gè)數(shù)k=3，這儼然就是一個(gè)Steiner三元系統(tǒng)(STS)！而制勝策略中的三元系統(tǒng)的構(gòu)造，就是之前所循的“NIM和”為0的方法！

可以指出的是，指標(biāo)λ=1的STS(v)中，由于任意兩個(gè)數(shù)該STS(v)的一個(gè)數(shù)組中總能出現(xiàn)且只出現(xiàn)一次，故某一三元組已存在在該STS(v)中，若在該區(qū)組中改變?nèi)我庖粋€(gè)數(shù)，則必跳出此STS(v)；若某一三元組不屬于該STS(v)，我們也總能通過適當(dāng)減小當(dāng)中某一個(gè)數(shù)使其又回到該STS(v)中！從這個(gè)意義上說，我們總能通過一定的方法，找到最大石子數(shù)不超過v=2n-1(n≥2)的“抓三堆”與STS(v)之間的對(duì)應(yīng)！從而將3堆情形下的經(jīng)典NIM游戲的制勝策略問題轉(zhuǎn)化成了組合數(shù)學(xué)中STS(v)的區(qū)組設(shè)計(jì)問題！當(dāng)然，并不是所有的STS(v)都能夠?qū)?yīng)上NIM的制勝策略，例如包含區(qū)組(1,2,4)的STS(v)就不是制勝策略了，因?yàn)檫@個(gè)STS(v)不可能再包含(1,2,3).

Kirkman女生問題的介紹

Kirkman在1850年提出了著名的女生問題：十五個(gè)女生站成每排三人的五排，每排的三人互為伙伴，問能否安排一種排隊(duì)方法，使得連續(xù)七天內(nèi)，每個(gè)人的兩個(gè)伙伴都不會(huì)重復(fù).這就是后來被不少數(shù)學(xué)家關(guān)注且研究的Kirkman女生問題，后來，數(shù)學(xué)家們還將人數(shù)進(jìn)行了一般化的處理，使人數(shù)為v=6n+3的形式，一般化后的問題又稱為Kirkman三元系問題，它是這樣的Steiner三元系統(tǒng)(STS)：它的區(qū)組可以分解為若干個(gè)可解類，使得每一個(gè)元素恰好出現(xiàn)在每個(gè)可解類的一個(gè)區(qū)組中，稱這樣的(STS)是可解的.

這里，需要令v=6n+3，而不能是v=6n+1，是因?yàn)?，在每個(gè)可解類中，必須包含所有元素，因此，v必須是3的倍數(shù)，故只能是v=6n+3.我們看Kirkman給出的一個(gè)解：

星期一：{1,2,3}，{4,8,12}，{5,10,15}，{6,11,13}，{7,9,14}；

星期二：{1,4,5}，{2,8,10}，{3,13,14}，{6,9,15}，{7,11,12}，

星期三：{1,6,7}，{2,9,11}，{3,12,15}，{4,10,14}，{5,8,13}；

星期四：{1,8,9}，{2,12,14}，{3,5,6}，{4,11,15}，{7,10,13}；

星期五：{1,10,11}，{2,13,15}，{3,4,7}，{5,9,12}，{6,8,14}；

星期六：{1,12,13}，{2,4,6}，{3,9,10}，{5,11,14}，{7,8,15}；

星期天：{1,14,15}，{2,5,7}，{3,8,11}，{4,9,13}，{6,10,12}.

我們看到，這個(gè)解恰好是我們經(jīng)典NIM游戲中k=3且每一堆石子數(shù)都不超過15的情況下的平衡狀態(tài)！

這里，我們可以證明：v=2n-1(n≥2)且3|v時(shí)(即n為偶數(shù)時(shí))的Steiner三元系統(tǒng)的區(qū)組可以如下構(gòu)造：

羅見今老師的一本冊子中較為細(xì)致地做了這部分的一些整理工作[注]羅見今.科克曼女生問題(世界數(shù)學(xué)名題欣賞叢書)[M].沈陽：遼寧教育出版社，1995.，故若想在這一方面做進(jìn)一步的研究，可以自行參閱.

2.3 NIM型游戲與集合論

兩個(gè)集合做對(duì)稱差，求的是屬于且只屬于其中的一個(gè)集合的元素，所構(gòu)成的集合，相當(dāng)于兩個(gè)相對(duì)補(bǔ)集的并集，或者是兩個(gè)集合的交集在它們并集中的補(bǔ)集，即：

A△B=(AB)∪(BA)=(A∪B)(A∩B).

對(duì)稱差運(yùn)算滿足交換律和結(jié)合律：

A△B=B△A,

(A△B)△C=A△(B△C)=A△B△C.

交換律的證明顯然，結(jié)合律的證明就顯得稍微復(fù)雜一些.

證明(結(jié)合律)

A△(B△C)=(A(B△C))∪((B△C)A)

同理可證：

故有，結(jié)合律成立，證畢.

那么，這與“NIM和”之間的具體關(guān)系是什么？

1.若(a′,b,c)、(a,b′,c)和(a,b,c′)都是有利局勢，則有：

(a′>a)∧(b′>b)?c′

這其實(shí)可以通過下面的維恩圖觀察出來：

圖3 圖4 圖5

其中，圖3中，A′為四邊形CDEF，B為四邊形HIJK,由于A′△B△C=?，故C即為圖中的四邊形CHKF與四邊形DIJE的并；又因?yàn)锳△B′△C=?且A′>A,B′>B,C=C,故A′比A大的部分應(yīng)該恰好與B′比B大的部分重合，且落在C中，如見圖4中的圓⊙C1；如此一來，當(dāng)C′想要滿足A△B△C′=?，就必將比C少掉圓⊙C1的部分，見圖5.

2. (a,b,c)中任意一元不大于另兩元之和，且不小于另兩元之差.

證明這一結(jié)論可由A△B△C=?得到，若其中一元含有另外兩元所不含的元素，它們的對(duì)稱差不可能為空集，前半句得證；同理，可知兩元之差也必含與第三元中，后半句得證.

3.若(a,b,c)是有利局勢，且有2t-1≤a<2t，那么(a,b+k·2t,c+k·2t)也是有利局勢，其中k是自然數(shù).

證明b和c這兩元同時(shí)加上同一個(gè)k·2t之后，轉(zhuǎn)為2的方冪的集合B′與集合C′就同時(shí)多了相同的元素，多的這些都存在兩個(gè)集合的交集之中，恰好能夠在對(duì)稱差B′△C′運(yùn)算中消掉，又因?yàn)?t-1≤a<2t，故加上的這個(gè)數(shù)又在與A做對(duì)稱差運(yùn)算時(shí)不帶來實(shí)質(zhì)性的消減影響.故A△B′△C′=?也同樣成立.

“必破性”：利用性質(zhì)1我們可以知道，若在有利局勢(a′,b,c)中，從某一堆中拿走一些石子，不妨假設(shè)從第一堆中取走若干石子，使其變成了(a,b,c)，那么此時(shí)它就不是有利局勢了，否則由于(a,b′,c)也是有利局勢，由性質(zhì)1可推出c

“還原性”：從有利局勢取至不利局勢如(a,b,c)后，在余下的某一堆中恰可以取走適當(dāng)?shù)氖?，使之變?yōu)橛欣謩荩藭r(shí)可取為(a,b,c′).

另外，利用性質(zhì)3，我們便可以從一個(gè)已知的簡單平衡狀態(tài)出發(fā)，構(gòu)造出更多的平衡狀態(tài)，如已知(1,2,3)是平衡狀態(tài)，那么(1,2k,2k+1)，(1,4k+2,4k+3)，(4k+1,2,4k+3)，(16k+1,2,16k+3)，(32k+1,32k+2,3)等等也都是.并且，有理由相信，每一個(gè)平衡狀態(tài)都可以看成是一些簡單初始狀態(tài)經(jīng)過若干次的雙元同加一個(gè)數(shù)這樣的變化所得到的，這些簡單的初始狀態(tài)構(gòu)成一個(gè)集合S，它們在性質(zhì)3的運(yùn)算下將能夠生成整個(gè)平衡狀態(tài)集.而這個(gè)初始集合S就是{(0,0,0)}，它只有一個(gè)元素.

例如：

事實(shí)上，由于所有的平衡狀態(tài)都滿足三個(gè)集合的對(duì)稱差能夠?yàn)?，意味著某一個(gè)2的方冪若出現(xiàn)，必只在其中兩個(gè)集合中出現(xiàn)，這樣一來，在遞推過程中，我們就總能倒著兩兩刪除這個(gè)數(shù)，最后一步一步倒推回最初的生成元(0,0,0)，這使我們不禁想起經(jīng)典NIM游戲里面的情景，它幾乎是游戲情形的再現(xiàn).

3 結(jié)束語

上述的幾種數(shù)學(xué)理論中，NIM型游戲的輪廓有時(shí)尚可依稀分辨，但有些已全然看不出其原貌，已升華為純數(shù)學(xué)的抽象語言了.而NIM型游戲在數(shù)學(xué)中的研究，遠(yuǎn)不止前面所提及的這些，例如利用“NIM和”研究得到的新成果，可以與高斯函數(shù)、莫比烏斯函數(shù)、伽羅華域、歐幾里得環(huán)等相聯(lián)系④，也是令人感到驚奇的.數(shù)學(xué)中總是有著一些意料之外卻又在情理之中的聯(lián)系，讓你不得不嘆服那些發(fā)現(xiàn)這些聯(lián)系的數(shù)學(xué)家們，在布滿荊棘的叢林中，天才的探險(xiǎn)家與常人不同的是，他們總能披荊斬棘，發(fā)現(xiàn)暗藏其中的巨大寶藏，為世人帶來傳奇與快樂！

④ 羅見今.Nim—從古代的游戲到現(xiàn)代的數(shù)學(xué)[J].自然雜志，1986,01.