3

爱丽丝和鲍勃正在玩游戏。他们被赋予了 n (<50) 个介于 1-1000 之间的数字。在一个回合中，他们可以执行以下
任一操作 1.将数字减 1。2.
擦除 2 个数字并写下它们的总和。
数字达到 0 时会自动删除。如果玩家无法完成这 2 个动作中的任何一个，则该玩家输了。给定 Alice 先下棋，如果双方都打得最好，我们怎么知道谁会赢呢？

如果一个人不知道博弈论算法，这个问题可以做吗？

4

1 回答 1

1

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

假设游戏开始时的数字是 x 1 , x 2 , x 3 , ..., x n。n请注意，只有移动 1 会改变所有数字的总和。因此，我们一开始就立即知道 Alice 和 Bob 总共会进行多少次移动 1。

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

由于第 2 步完成的次数不是恒定的，而第 1 步完成的次数是恒定的，谁将获胜的驱动力是谁能控制他们中的任何一个进行第 2 步的次数的平价。在那张纸条上：

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

任何时候其中一个数字是 1，您都可以打赌，是否会减少它（并删除 0），或者选择它作为将被替换为的两个数字之一。和。该决定将与上述各点直接相关。

最后，如果“必须采取行动”，那么“尽快采取行动”和“拖延到最后可能采取行动”之间有什么区别？

于 2013-09-24T17:53:02.567 回答