看完之后,能懂自然懂。
不懂我就在补充一下吧。
对于第二个游戏的定义:
一个位置上有任意堆硬币(初始只有一堆或者没有),一堆对应着第一个游戏的该位置为正面朝上,反之即为负面朝上。
若位置$i$连带着前$k$个相邻的位置翻面,相对应的就是$i$这里要拿走一堆硬币,前$k$个相邻的位置都要放入一堆硬币。
那么对于第二个游戏而言x,每个堆无关。那么根据SG定理,
游戏和的SG函数等于各个游戏SG函数的Nim和。
那么该位置多或少偶数堆硬币,整个局面的SG值不会发生改变。
正如截图所说的,第一个游戏是DAG(有向无环图),考虑归纳证明:对于任意一个第一个游戏的局面,它的SG值与第二个游戏的对应局面相同。
边界情况指硬币在$1$这个位置,显然成立。
那么考虑对于某个第一个游戏的局面,它的前驱局面都已被归纳证明,那么它的SG值就是所有前驱局面的$\text{mex}$值。
对于某个前驱局面,已被归纳证明,与第二个游戏的对应前驱局面SG值相等,那么考虑如果当前需要翻转操作某一个位置,使得$1\rightarrow 0$,那么在$0$的基础上加上两堆硬币,这恰好就是对应了第二个游戏的操作,于是两个集合的$\text{mex}$集合相同,也就是SG值相同。
因此原命题得证。
最后一次更新于2020-05-16
0 条评论