staircase nim-楼梯游戏

定义

有一个n阶楼梯,从下到上编号为0~n,游戏开始时有若干硬币任意分布在楼梯上。Alice和Bob轮流操作。
每次操作可以选择一阶楼梯上的若干硬币(至少一个),然后移到下一阶楼梯上。最后不能移动的人输。

结论

奇数阶楼梯上的石子异或和为零,则先手必胜。

证明

首先明确 最后的状态是奇数阶梯上的石子异或和为零。

那么对于奇数阶楼梯上的石子异或和不为零的情况:

先手可以移动若干石子,使得奇数阶梯上的石子异或和为零。

不管后手怎么移动,一定会使得奇数阶梯上的石子异或和不为零。

因此最后一定是先手必胜。


对于奇数阶梯上的石子异或和为零的情况:

不管先手如何移动,都会使得奇数阶梯上的石子异或和不为零。

而后手可以修正,使得奇数阶梯上的石子异或和为零。

因此后手必胜。

Thank you for your support!