Nim博弈

问题描述

有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

问题分析

C. Bouton证明了以下定理

在正常的Nim游戏中，当且仅当堆的大小的nim-sum非零时，进行第一次移动的玩家才具有获胜策略。否则，第二个玩家有一个获胜策略。

nim-sum即每堆的大小的异或和。

证明：

注意，nim-sum（⊕）通常服从加法交换律，还满足一个附加属性，X ⊕ X = 0。
设x 1，...， x n是移动前堆的大小，y 1，...， y n是移动后的相应大小。让$s = x_1 \bigoplus ... \bigoplus x_n​$ 和 $t = y_1 \bigoplus ... \bigoplus y_n​$。假设一次移动在堆k中，则对于所有i ≠ k，我们有$x_i = y_i​$，并且$x_k > y_k​$。根据上面提到的异或的属性，我们有

t = 0 ⊕ t
    = s ⊕ s ⊕ t
    = s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn)
    = s ⊕ (x1 ⊕ y1) ⊕ ... ⊕ (xn ⊕ yn)
    = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xk ⊕ yk) ⊕ 0 ⊕ ... ⊕ 0
    = s ⊕ xk ⊕ yk

(*) t = s ⊕ xk ⊕ yk

通过以下两个引理的归纳。

• lemma 1

如果s = 0，则无论采取何种移动，t ≠ 0。

证明：如果没有可能的移动，则引理是空真(vacuously true)（第一个玩家按照定义无法进行正常的游戏），即由于前件为假导致结果为真。否则，对堆k的任何操作将产生$t = x_k \bigoplus y_k​$。该数字非零，因为$x_k \neq y_k​$。

• Lemma 2

如果s ≠ 0，则可以进行移动以使t = 0。

证明：设d是s的二进制表示中最左边（最高有效）非零位的位置，并选择堆k使得$x_k$的第d位也非零。（这样的k必须存在，否则s的第d位将为0）然后让 $y_k = s \bigoplus x_k$，我们可以知道 $y_k < x_k$：在 $x_k$ 和 $y_k$ 中第d位左边所有位是一样的，位d从1减小为0（将值减小 $2^d$），其余位的任何变化最多为 $2^d$-1。第一个玩家可以从第k堆中拿出$x_k-y_k$个物品，然后

t = s ⊕ xk ⊕ yk
= s ⊕ xk ⊕ (s ⊕ xk)
= 0

由于最后一个人是$s\neq 0$,$t = 0$的情况，那么只要保证最初是 lemma2的$s\neq 0$,$t = 0 ，在lemma2（第一个人）和lemma1（第二个人）交替多次后，必然是第一个人得到最终的胜利。反正若是lemma1为初始状态，则第二人将胜利。

P.S. 此定理仅在有堆的大小为2或大于2时成立

范例问题

problem

HDU1907

John

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 6413 Accepted Submission(s): 3698

Problem Description

Little John is playing very funny game with his younger brother. There is one big box filled with M&Ms of different colors. At first John has to eat several M&Ms of the same color. Then his opponent has to make a turn. And so on. Please note that each player has to eat at least one M&M during his turn. If John (or his brother) will eat the last M&M from the box he will be considered as a looser and he will have to buy a new candy box.

Both of players are using optimal game strategy. John starts first always. You will be given information about M&Ms and your task is to determine a winner of such a beautiful game.

Input

The first line of input will contain a single integer T – the number of test cases. Next T pairs of lines will describe tests in a following format. The first line of each test will contain an integer N – the amount of different M&M colors in a box. Next line will contain N integers Ai, separated by spaces – amount of M&Ms of i-th color.

Constraints:
1 <= T <= 474,
1 <= N <= 47,
1 <= Ai <= 4747

Output

Output T lines each of them containing information about game winner. Print “John” if John will win the game or “Brother” in other case.

Sample Input

2
3
3 5 1
1
1

Sample Output

John
Brother

answer

#include<cstdio>
int main()
{
    int t,n,a,sum,s;
    scanf("%d",&t);
    while(t--)
    {
        sum=0;
        s=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a);
            s^=a;
            sum+=a;
        }
        if(sum==n)//所有堆大小都为1
        {
            if(sum%2==0) printf("John\n");
            else printf("Brother\n");
        }
        else
        {
            if(s==0) printf("Brother\n");
            else printf("John\n");
        }
    }
    return 0;
}

问题扩展

如果Nim游戏中的规则稍微变动一下,每次最多只能取K个,怎么处理?

方法是将每堆石子数mod (k+1).