由于最近一直有写道有关 博弈的问题 写个合集 总结下 这一年来一些碰到的博弈论的题目 顺便复习下

• 知识点包括但不限于:
• 简单Nim游戏的推导即证明
• Nim游戏的反向运用及有关孤独堆的整理
• SG函数的深层次理解
• 些非SG函数非NIM的思维博弈论题目

Nim游戏
板子题 没什么可说的 直接上证明

首先 证明 $a_1\bigotimes a_2\bigotimes \cdot\cdot\cdot\bigotimes a_n=0$时 无论如何操作,都一定会使得当前局面下的异或和,变成非0数

**反证法:假定若存在一$a_i$能够通过取走该堆中的一部分石子使得局面的异或和,变成0那么
记$a_i$剩余石子为$\dot{a_i}$ 则操作后的局面的异或和就可以写成

• $a_1\bigotimes a_2\bigotimes \dot{a_i}\bigotimes \cdot\cdot\cdot\bigotimes a_n =0$
• $a_1\bigotimes a_2\bigotimes \cdot\cdot\cdot\bigotimes a_n=0$

那么对上下两个式子同时进行异或运算 则会发现 同一对的数消去以后
剩下 $a_i\bigotimes \dot{a_i}=0$即$a_i=\dot{a_i}$说明没有取石子
那么通过反证的方式
得到重要结论:

• 当局面的异或和为0时 无论如何操作一定会使得局面变成 异或和不为0的

接下来只需要证明第二点 当局面的异或和为0时 一定存在一种操作使得 操作后局面的异或和从非0的变成0

假定$a_1\bigotimes a_2\bigotimes \dot{a_i}\bigotimes \cdot\cdot\cdot\bigotimes a_n =x(x!=0)$
由于 位运算只会使得 数变小或者不变 因此 x的第k位的1 一定存在$a_i$的第k位1在经过异或后保留下来的
因此我们从该$a_i$堆中取走 $a_i-(a_i-x\bigotimes a_i)$这么多的石子使得 $a_i$这堆石子变成$a_i\bigotimes x$
那么剩下的局面的异或和就可以写成： $a_1\bigotimes a_2\bigotimes a_i\bigotimes x \cdot\cdot\cdot\bigotimes a_n $该式子可以写成 $a_1\bigotimes a_2\bigotimes \cdot\cdot\cdot\bigotimes a_n\bigotimes x=0$
即一定存在某种操作使得 异或和不为0的状态变成异或和为0的状态
根据上述的两条结论 我们就可以发现 如果当前局面的异或和不为0 可以通过操作使其变为0 而 面对异或和为0局面的人 只能把异或和不为0的局面交给我们继续操作 因此 只要当前局面的异或和不为0 就可以一直操作
知道 面对异或和为0的人再也无法操作 即胜利