1.13 NIM（3）兩堆石頭的游戲

在前面兩個題目中，我們討論了被稱為“NIM（拈）”的這種游戲及其變種的玩法和必勝策略，下面我們將討論這類游戲的另一種有趣的玩法。

假設有兩堆石頭，有兩個玩家會根據如下的規則輪流取石頭：

每人每次可以從兩堆石頭中各取出數量相等的石頭，或者僅從一堆石頭中取出任意數量的石頭；

最后把剩下的石頭一次拿光的人獲勝，如圖1-21所示。

例如，對于數量分別為1和2的兩堆石頭，取石頭的第一個玩家必定將會輸掉游戲。因為他要么只能從任意一堆中取一塊石頭，要么只能從兩堆中各取出一塊石頭。但無論他采用哪種方式取，最后，剩下的石頭總是恰好能被第二個玩家一次取光。

定義一個函數如下：

            bool nim(n, m)  //n, m分別是兩堆石頭的數量

要求返回一個布爾值，表明首先取石頭的玩家是否能贏得這個游戲。

分析與解法

本題中有兩個玩家，有兩種取石頭的方法，每個人還必須按照比較理性的方法取石頭……頭緒的確比較多，不妨從簡單的問題入手，還記得構造質數的“篩子”方法嗎？

怎樣才能找出從2開始的質數呢？我們先把所有數字都排列出來：

既然2是質數，那么2的倍數就不是質數，那我們就把它們都“篩掉”：

那么下一數字3，它沒有被篩掉，意味著它不能被小于它的數整除，所以它就是一個質數！于是我們再把3的倍數篩掉，得到下表：

如法炮制，我們得到了后面的質數：5, 7, …

解法一

回到這個NIM的問題，我們能否也“篩”一回？表1-4顯示了在（10, 10）范圍內兩堆石頭可能的組合，由于它具有對稱性，所以我們不用處理另一半的表格，另外，像（0, 0）、（1, 0）這樣的特殊情況已經處理了。所以我們先把它們篩掉。

首先定義：先取者有必勝策略的局面為“安全局面”，否則為“不安全局面”。

我們把（1, 1）,（2, 2）, …,（10, 10）的安全局面篩掉。如表1-5所示。

這個表里最前面的一個組合就是（1, 2），通過簡單的分析，我們知道這是一個必輸的局面——“不安全局面”，那么根據規則可以一步到達（1, 2）這個局面的數字組合如（1, 3）,（1, 4）,（1, n）等，都是安全局面——我們可以把這些組合全部篩掉，（2, n）也是可以一步轉換成（2, 1）的（它等價于（1, 2）），所以也要被篩掉。（n+1, n+2）也是如此，同樣可以被篩掉。這樣我們的表就簡潔多了（如表1-6所示）。

現在表上的下一組數是什么呢？對，是（3, 5）。和（1, 2）一樣，這個沒有被篩掉的組合就是下一個不安全局面。顯然，（3, 5）組合的任意一個符合規則的變化都是一個“安全局面”。

好了，得到了（3, 5），我們就要把（3, n）,（n, 3）,（5, n）,（n, 5）,（3+n, 5+n）都篩掉。于是我們得到了表1-7。

這時，（4, 7）成為另一個不安全局面，經過篩選之后，（6, 10）又是一個……

一般而言，第n組的不安全局面（an, bn）可以由以下定義得到：

1．a1=1, b1=2；

2．若a1, b1, …, an-1, bn-1已經求得，則定義an為未出現在這2n-2個數中的最小整數。

3．bn=an+n；

做成表就是（如表1-8所示）。

因此，我們可以根據上述定義，從第一個不安全局面（1, 2）出發，依次向上推理，直到推理出足夠的不安全局面來判定一個隨機給定的狀態下，先取者是否能夠獲勝。具體做法就是設兩堆石頭中較小那堆的數量為x，從（1, 2）開始向上推理，直到an大于等于x為止，此時我們就得到了an小于等于x的所有不安全局面。如果x恰好等于某一不安全局面的an值，就看另一堆石頭的數量是否恰好與對應的bn相等，從而判斷出先取者是否有辦法贏得游戲。如果x不等于任意一個不安全局面的an值，則先取者必勝。

根據上述分析，可以寫出代碼清單1-18。

代碼清單1-18:C#自底向上的解法

    static bool nim(int x, int y)
    {
        // speical case
        if(x==y)
        {
            return true;     // I win
        }
        // swap the number
        if(x > y)
        {
            int t=x; x=y; y=t;
        }
        // basic cases
        if(x==1 && y==2)
        {
            return false;        // I lose
        }
        ArrayList al=new ArrayList();
        al.Add(2);
        int n=1;
        int delta=1;
        int addition=0;
        while(x > n)
        {
            // find the next n;
            while(al.IndexOf(++n) !=-1);
            delta++;
            al.Add(n+delta);
            addition++;
            if(al.Count > 2 && addition > 100)
            {
                // 因為數組al中保存著n從1開始的不安全局面，所以在
                // 數組元素個數超過100時刪除無用的不安全局面，使數組
                // 保持在一個較小的規模，以降低后面IndexOf()函數調用
                //的時間復雜度
                ShrinkArray(al, n);
                addition=0;
            }
        }
        if((x !=n) || (al.IndexOf(y)==-1))
        {
            return true;     // I win
        }
        else
        {
            return false;        // I lose
        }
    }
    static void ShrinkArray(ArrayList al, int n)
    {
        for(int i=0; i<al.Count; i++)
        {
            if((int)al[i] > n)
            {
                al.RemoveRange(0, i);
                return;
            }
        }
    }

解法看上去雖然直觀，但是效率并不高，因為它是一種自底向上推理的算法，算法的復雜度為O（N）。

解法二

我們看看能否找出不安全局面的規律，最好有一個通用的公式可以表示。所有不安全局面（{<1, 2>, <3, 5>, <4, 7>, <6, 10>, …}）的兩個數合起來就是所有正整數的集合，且沒有重復的元素，而且所有不安全局面的兩個數之差的絕對值合起來也是相同情況，如：2-1=1,5-3=2,7-4=3,10-6=4, …

看來不安全局面是有規律的。我們可以證明有一個通項公式能計算出所有不安全局面，即

    an=[a * n], bn=[b * n], （[]表示對一個數取下整數，如：[1.2]=1）
    a=(1+sqrt(5)) / 2,
    b=(3+sqrt(5)) / 2

具體證明見文后附1（第82頁）。

有了通項公式，我們就能更加簡明地實現函數bool nim(n, m)，這個函數的時間復雜度為O（1）（如代碼清單1-19所示）。

代碼清單1-19

    bool nim(int x, int y)
    {
        double a, b;
        a=(1+sqrt(5.0)) / 2;
        b=(3+sqrt(5.0)) / 2;
        if(x==y)
            return true;
        if(x > y)
            swap(x, y);      // ensure x ＜=y
        return(n!=(long)floor((y-x)*a));
    }

解法二將算法的復雜度降低到了O（1），由此可見，掌握良好的數學思維能力，往往能在解決問題時起到事半功倍的效果。“拈”游戲還有許多有趣的變形和擴展，感興趣的讀者不妨思考一些新的游戲規則，并嘗試尋找對應的必勝策略。

擴展問題

1．現在我們已經給出了一個判斷先取者是否能夠最終贏得游戲的判斷函數，但是，游戲的樂趣在于過程，大家能不能根據本題的思路給出一個贏得游戲的必勝策略呢？即根據當前石頭個數，給出玩家下一步要怎么取石頭才能必勝。

2．取石頭的游戲已經不少了，但是我們還有一種游戲要請大家思考，我們姑且叫它NIM（4）。

兩個玩家，只有一堆石頭，兩人依次拿石頭，最后拿光者為贏家。取石頭的規則是：

■ 第一個玩家不能拿光所有的石頭。

■ 第一次拿石頭之后，每人每次最多只能拿掉對方前一次所拿石頭的兩倍。

那么，這個游戲有沒有必勝的算法？（提示：好像和Fibonacci數列有關。）

附1：解法二的證明

準備

我們將兩堆石頭的數目記作<a, b>。對任意正整數a，如果<a, b1>和<a, b2>都是不安全局面，則b1=b2（假設b1> b2，則先取者可以通過在<a, b1>中拿b1-b2個石頭來讓對手達到<a, b2>的不安全局面，這與沒有必勝策略矛盾，所以說a和b是一一對應的）。

定義

■ L={<an,bn>|<an,bn>是不安全局面}={<1,2>,<3,5>,<4,7>,<6,10>, …}

■ An={a1, a2, …, an}, Bn={b1, b2, bn}

■ A={a1, a2, …, an, … }

■ B={b1, b2, …, bn, … }

■ N為除0以外的自然數集

因為對稱性和an=bn時為安全局面，我們可以定義an<bn，同時還可以定義an<an+1（n=1, 2, 3, …）。由“準備”中的結論我們知道A∩B=?（否則存在x∈A∩B，使得<a, x>, <x, b>（其中a∈A, b∈B, a<x<b）都是不安全局面，這與“準備”中的結論矛盾）。后面我們還將看到A∪B=N（N是0除外的自然數集）。

證明

從解法一中我們得知，所有的不安全局面<an,bn>都滿足：an+n=bn，且an=min（N–An-1∪Bn-1），接下來我們將采用數學歸納法來證明這個結論。

1．顯然n=1時，結論成立。

n=1時，根據定義得a1=1, b1=2，記作<1, 2>。按照游戲規則，先取者要么取光其中一堆石頭，要么從第二堆中取出一塊石頭，要么從兩堆中各取一塊石頭。無論先取者怎么取，后取者都將取得最后的石頭而獲勝。

2．假設n<k（k>1）時結論成立，我們現在來證明n=k時結論也成立，即ak+k=bk，其中ak=min（N–Ak-1∪Bk-1）。為了證明方便，記a=ak。

（1）顯然<a, x>（x <=a）都是安全局面（根據a定義和歸納假設）。

（2）<a, a+x>（x=1, 2, …, k-1）是安全局面，因為總可以分別從兩堆石頭中拿走a-ax，以到達不安全局面<ax, ax+x>。

（3）<a, a+k> 是不安全局面，可以通過枚舉所有可能情況來證明，如下所示。

■ 從a中取走a–x塊石頭（x=1, 2, …, a-1），剩下<x, a+k>是安全局面。因為即使存在不安全局面<x, x+t>，因為有x<a, t<k，所以x+t<a+k。

■ 從a+k中取，只能到達安全局面。前面（1）和（2）已經證明了<a, x>（x≤a）和<a, a+x>（x=1, 2, …, k-1）都是安全局面。

■ 分別從兩堆中取x塊石頭（x=1, 2, …, a），剩下的<ak-x, ak+k-x>一定是安全局面。因為假設存在<ak-x, ak–x+t>的不安全局面，由于有t<k，所以ak–x+t<ak+k–x，假設不成立。

（4）<a, a+x>（x > k）是安全局面：

■ 由（3）可知，在第二堆中取x-k即可達到不安全局面<a, a+k>。

所以，當n=k時，有bk=ak+k，其中ak=min（N–Ak-1∪Bk-1），結論成立。由數學歸納法知，對任意正整數n原結論成立。

推論：A∪B=N（讀者可以用反證法證明），又因為我們已經得到A∩B=?，所以A/B是N的一個分劃。這個推論會在下面的求解中應用到。

求解不安全局面

我們已經得到不安全局面的一些性質，現在來求解不安全局面。

定理：如果正無理數a, b滿足1/a+1/b=1，則{[a×n] |n∈N}/{[b×n] |n∈N}是N的一個分劃，其中[]為高斯記號，[a×n]表示對a×n向下取整。

我們就根據上述定理來構造一個滿足不安全局面的分劃。

取無理數a, b，其滿足1/a+1/b=1；

令xn=[a×n], yn=[b×n], yn=xn+n（n=1, 2, 3, 4, …）；

則{xn|n∈N}/{yn|n∈N}是N的一個分劃。我們在加上一個限制條件：令yn=xn+n，即[b×n]=[a×n]+n=[(a+1)×n]，因為這個等式對所有的n∈N成立，所以必有b=a+1（否則總能找到足夠大的n使得等式不成立）。

求解二元一次方程組：

可得：

下面我們將看到這個xn, yn就是我們要求的an, bn：

1．顯然x1=a1，且滿足相同的遞推關系，所以我們只需證明xn=min（N–Xn-1∪Yn-1）；

2．其中Xn={x1,x2, …,xn}, Yn={y1,y2,…,yn}，這是顯然的，否則，由于xn、yn具有嚴格的單調性，且yn> xn，那么N–X∪Y將會不為空，與X/Y是N的劃分矛盾。

所以xn, yn就是我們所要求的an, bn。

即an=[a×n], bn=[b×n]，其中：

至此，對于任意給定的一個狀態<x, y>，我們都可以通過判斷x是否等于某個[a×n]，且y是否等于對應的[b×n]，來判斷<x, y>是否為一個不安全局面。或者我們也可以通過判斷x（假設x <=y）是否等于[a]×（y–x）來判斷<x, y>是否為一個不安全局面。同理，若<x, y>是一個安全局面，我們也可以通過這個判定法來取合適數量的石頭，從而令對手達到某一個不安全局面。

附2:Python的程序解法

前面提到的解法一的代碼是由C#寫成的，MSRA里有位工程師給出了一個Python的解法，思路與之類似，大家不妨分析一下哪種解法效率更高？代碼清單1-20是自底向上解法的Python源代碼。

代碼清單1-20

    // Comments: Python code
    false_table=dict()
    true_table=dict()
    def possible_next_moves(m, n):
        for i in range(0, m):
            yield(i, n)
        for i in range(0, n):
            if m<i:
                yield(m, i)
            else:
                yield(i, m)
        for i in range(0, m):
            yield(i, n - m+i)
    def can_reach(m, n, m1, n1):
        if m==m1 and n==n1:
            return False
        if m==m1 or n==n1 or m - m1==n - n1:
            return True
        else:
            return False
    def quick_check(m, n, name):
        for k, v in false_table.items():
            if can_reach(m, n, v[1][0], v[1][1]):
                true_table[name]=(True, v[1])
                return (True, v[1])
        return None
    def nim(m, n):
        if m > n:
            m, n=n, m
        name=str(m)+'+'+str(n)
        if name in false_table:
            return false_table[name]
        if name in true_table:
            return true_table[name]
        check=quick_check(m, n, name)
        if check:
            return check
        for possible in possible_next_moves(m, n):
            r=nim(possible[0], possible[1])
            if r[0]==False:
                true_table[name]=(True, possible)
                return (True, possible)
            elif can_reach(m, n, r[1][0], r[1][1]):
                true_table[name]=(True, r[1])
                return (True, r[1])
        false_table[name]=(False, (m, n))
        return (False, (m, n))

    ###for testing
    def assert_false(m, n):
        size=0
        for possible in possible_next_moves(m, n):
            size=size+1
            r=nim(possible[0], possible[1])
            if r[0] !=True:
                print 'error! ', m, n, 'should be false but it has false sub/
                    move', possible
                return
        print 'all', size, 'possible moves are checked! '

很快，這位工程師又想出了另一種解法，不過這次他不是從n=1的不安全局面自底向上推理的，而是反其道行之，自頂向下查找，代碼如清單1-21，讀者不妨研究一下。

代碼清單1-21

    // Result indicates position(x, y) is whether true or false
    // true means when m=X and n==Y, then the first one will win
    // false vice versa
    public class Result
    {
        public override string ToString()
        {
            string ret=string.Format("{0} ({1}, {2})", State.ToString(),
              X, Y);
            return ret;
        }
        public Result(bool s, uint x, uint y)
        {
            State=s;
            X=x;
            Y=y;
        }
        public bool State;
        public uint X, Y;
    }
    public static Result nim(uint m, uint n)
    {
        if(m==n || m==0 || n==0)
        {
            return new Result(true, m, n);
        }
        if(m<n)
        {
            uint tmp=m;
            m=n;
            n=tmp;
        }
        Result[, ] Matrix=new Result[m, n];
        for(uint i=0; i<n; i++)
        {
            for(uint j=i+1; j<m; j++)
            {
                if(Matrix[j, i]==null)
                {
                    PropagateFalseResult(m, n, j, i, Matrix);
                    if(Matrix[m -1, n -1] !=null)
                    {
                        return Matrix[m -1, n -1];
                    }
                }
            }
        }
        return Matrix[m -1, n -1];
    }
    // when we can decide Position(x, y) is false, then we can decide that
    // all other positions in the row that follows this position is true,
    // since they can get to position(x, y) at one step all other
    // positions in the column that follows this position is true,
    // since they can get to position(x, y) at one step all other
    // positions in the diagonals that follows this position is true,
    // since they can get to position(x, y) at one step
    // thus we propagate the results to these positions.
    static void PropagateFalseResult(uint m, uint n, uint x, uint y,
    Result[, ] Matrix)
    {
        Matrix[x, y]=new Result(false, x+1, y+1);
        Result tResult=new Result(true, x+1, y+1);
        for(uint i=y+1; i<n; i++)
        {
            Matrix[x, i]=tResult;
        }
        for(uint i=x+1; i<m; i++)
        {
            Matrix[i, y]=tResult;
        }
        uint steps=m - x;
        if(steps > n - y)
        {
            steps=n - y;
        }
        for(uint i=1; i<steps; i++)
        {
            Matrix[x+i, y+i]=tResult;
        }
        if(x<n)
        {
            for(uint i=x+1; i<m; i++)
            {
                Matrix[i, x]=tResult;
            }
        }
    }