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;
            }
        }
    }