台阶NIM游戏

内容纲要

file

台阶NIM游戏是NIM游戏的变种,如果不清楚NIM游戏是什么请看上篇文章

确保理解经典NIM游戏之后来分析本例

对于台阶NIM游戏有如下结论

台阶NIM游戏可以看做是对所有奇数级台阶做经典NIM游戏

结论可以证明,如下:

证法一

要证明上述结论只需证明

  1. 对偶数级台阶的操作和游戏结果没有关系
  2. 奇数级台阶的博弈问题等价于经典NIM游戏

先证明第一条:

对于对手对偶数级台阶的某次操作(将2n号台阶上的石子拿下x个到2n-1号上),我们都可以对下一级台阶采取同样操作使其无效(将2n-1号的x个石子拿到2n-2上)

这样便可令偶数级台阶的操作不会影响到奇数级台阶

而根据题意,地面上(0级)台阶是不可操作的,所以对手只能操作2,4,6,···等台阶,而操作这些台阶的结果最终都会收敛到操作第二级台阶,即:对手将第二级台阶的若干石子移至第一级,我们这时将同样数量的石子移至地面,无效化他的操作

这样的情况会收敛于偶数台阶均为0(不可操作)的状态,所以偶数级台阶的状态对游戏结果没有关系

再证明第二条:
对于对手对奇数级台阶的某次操作(将2n+1号台阶上的石子拿下x个到2n号上),可以看做是在经典NIM游戏中将这堆石子取走——因为偶数级台阶相当于“垃圾桶”,进来的石子都对胜负结果没有影响

所以我们可以直接套用经典NIM游戏的结论:

台阶NIM游戏先手必胜,当且仅当所有奇数级台阶石子数异或和不等于0

证法二

因为第k级台阶上的石子需要k次移动才可以到地面(退出游戏),所以第k级台阶上的n个石子可以看做经典NIM游戏中的k个石子堆,每堆石子有n个

当k是偶数时,k个相同的石子堆之间异或和为0
当k是奇数时,k个相同的石子堆之间异或和为n

所以命题得证,即——台阶NIM游戏可以看做是对所有奇数级台阶做经典NIM游戏

上原题代码

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

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