現代數學視角下的NIM型游戲

王姿婷 李建華

(1 海南省文昌中學 571300；2北京師范大學數學科學學院 數學與復雜系統教育部重點實驗室 100875)

1 前言

與眾多經典的數學游戲一樣，NIM型游戲的趣味性與挑戰性如此濃厚，以至于得到各領域數學研究者及愛好者的關注，首先它作為博弈游戲的一員，在博弈論、圖論中常被提及，它在集合論、組合數學中也占據較重要的位置.眾多相關文獻或聲勢浩大的占據整章的篇幅(如法國數學家C.Berge所著的《The Theory of Graphs and Its Applications》專門在第六章對NIM型游戲對策的研究)，或將游戲隱匿在浩繁的文字中，對游戲與相關理論了解不夠深入者，多會因其近乎純數學的嚴肅外表看不真切NIM型游戲的輪廓.下面，我們對現代數學視角下NIM型游戲做一個導引式的介紹與分析.

2 NIM型游戲

2.1 NIM型游戲與圖論

Sprange-Grundy值介紹

包括經典NIM游戲在內的許多的NIM型游戲，通?？梢杂靡环N稱之為“Sprange-Grundy值”予以分析，所謂的“Sprange-Grundy值”實際上是一種狀態函數：

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

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

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

當然，f(p,q,…,r)函數不特指哪個函數，不同的游戲有不同的SG(p,q,…,r)求法，而函數f(p,q,…,r)的選取有相當的技巧.例如：

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

在堆數……