algorithm - 给定游戏的获胜者

Question

爱丽丝和鲍勃正在玩游戏。他们被赋予了 n (<50) 个介于 1-1000 之间的数字。在一个回合中，他们可以执行以下任一操作
1.将数字减1。
2.删除2个数字并写下它们的和。
达到 0 的数字将自动删除。如果玩家不能完成 2 步中的任何一步，他就输了。假设爱丽丝先玩，如果双方都玩得最好，我们怎么知道谁会赢得比赛？

不懂博弈论算法能做这道题吗？

Answer 1

我还没有充实完整的解决方案，但我很确定您可以在没有任何博弈论算法的情况下获得解决方案，只需推理。以下是我希望对您有所帮助的有用信息:

假设游戏开始时的数字是 x₁, x₂, x₃, ..., x_n。请注意，只有移动 1 会改变所有 n 数字的总和。因此，我们一开始就知道 Alice 和 Bob 总共会走多少次第 1 步。

但是，他们走第 2 步的次数并不是恒定的。要分析它会发生多少次，请注意移动 2 和删除 0 项是唯一会减少当前写入数字数量的因素。因此，它们之间总共会出现 n 次，并且必须至少删除一个 0(当最后一次递减完成时)。

由于第 2 步完成的次数不是恒定的，而第 1 步的完成次数是恒定的，因此谁能获胜的驱动力就是谁能控制奇偶性他们中的任何一个采取行动 2 的次数。注意:

• 假设您已经知道数字总和的奇偶性，谁完全可以继续只走第 1 步，谁需要走第 2 步才能获胜？
• n 的奇偶性与上面有什么关系？ (注意当有人走 2 时动态如何变化)

任何时候其中一个数字是 1，您可以打赌，很多人都会考虑是否将它递减(并删除 0)，或者选择它作为将要计算的两个数字之一替换为总和。该决定将与上述几点直接相关。

最后，如果一个 Action “必须发生”，那么“尽快做出那个 Action ”和“拖延到最后一刻才做出那个 Action ”之间有什么区别？