经典NIM游戏/取石子游戏

内容纲要

作为博弈论第一课来看一个非常经典有趣的问题——NIM游戏

file

NIM游戏属于博弈论中的ICG问题(公平组合游戏)

ICG问题需要满足下面三点

  1. 由两名玩家交替移动
  2. 在游戏进程的任意时刻可以执行的操作和轮到哪名玩家无关
  3. 不能行动的玩家判负

需要注意的是,我们熟知的棋类游戏不属于ICG游戏,比如围棋双方下的棋子颜色不同

NIM游戏属于ICG游戏的典例

对于NIM游戏,有如下优美简洁的结论:

NIM游戏先手必胜,当且仅当

a_1 \oplus a_2 \oplus ...\oplus a_n \ne 0

下面给出简要的证明

要证上述结论,我们需要证明以下几点

  1. 当所有石子异或和不为0时,我们可以通过一次合法操作令其异或和为0
  2. 当所有石子异或和为0时,先手无论如何取,都不能令其异或和保持0
  3. 当所有石子被取完时,先手必败(显然成立)

对第一点的证明:

当所有石子异或和不为0时,我们可以通过一次合法操作令其异或和为0

假设

x = a_1 \oplus a_2 \oplus ...\oplus a_n \ne 0

我们关注x二进制位最高的1,设为第k位,有如下结论:对于所有的ai,至少有一个二进制下第k位是1

因为由异或的性质可知如果 a xor b = 1,则ab必有一个1

我们可以做出一次合法操作令上述二进制第k位为1的a_i转变为a_i xor x

此时前后状态改变为

x = a_1 \oplus a_2 \oplus ...\oplus a_k \oplus ...\oplus a_n \ne 0 \\
x' = a_1 \oplus a_2 \oplus ...\oplus a_k \oplus x \oplus ...\oplus a_n = x \oplus x=0

而为什么这一次操作是合法的呢?
观察二进制下ai xor x 的过程可以发现
file
因为x在第k位前都是0,所以a_i’在第k位前保留了ai对应位置的部分

而第k位已经证明二者都是1,xor结果是0,所以后面的数字不用再关心(图中写问号的位置是0或者1都与结果无关),因为a_i’一定比a_i要小
也就是我们一定可以取走ai的一部分石子,令a_i变为a_i'(ai xor x),此时所有石子的异或和(x)为0

现在证明第二点:

当所有石子异或和为0时,先手无论如何取,都不能令其异或和保持0

我们可以用反证法:
假设现在有a1~an其异或和为0,我们可以通过一次对ai的操作,令操作后的石子异或和仍未0

x = a_1 \oplus a_2 \oplus ...\oplus a_i \oplus ...\oplus a_n = 0 \\
x' = a_1 \oplus a_2 \oplus ...\oplus a_i' \oplus ...\oplus a_n = 0

将等式两边分别异或,成对的数值消去,可得

a_i \oplus a_i' = 0 \oplus 0 = 0

a_i = a_i'

与假设矛盾,故假设不成立



至此我们已经证明了该结论的正确性

现在来正向过一遍NIM游戏的思路吧

  1. NIM游戏当且仅当所有石子异或和不为0时先手必胜
  2. 这是因为我们先手要做出一次操作令其异或和为0,而对手无论如何操作都不能使异或和保持为0
  3. 这会使得游戏像所有石子堆都为0的方向收束并最终胜利
  4. 我们做出的操作是取出当且不为零的异或和x的二进制最高位1,记为第k位,然后找出一个二进制第k位同为1的a_i,令他变为a_i xor x
  5. a_i xor x 一定会比a_i小,所以这次操作是合法的

上代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int res = 0;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        res ^= x;
    }
    if(res)
        puts("Yes");
    else
        puts("No");
    return 0;
}
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论