1

我遇到了一个问题。

有 N 堆石头，其中第 i 堆有 xi 块石头。爱丽丝和鲍勃玩以下游戏：

a. Alice starts, and they alternate turns.

b. In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the piles you create should have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5). 

c. The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

给定起始的牌堆，假设两个玩家都打得最好，谁会赢得比赛？

最重要的陈述——“如果爱丽丝获胜，答案应该是爱丽丝，否则答案是鲍勃。”

现在我的问题是，如果我们最初只有一堆 8 块石头，那么实际答案是 Bob。但就我而言，如果 Alice 将最初的 8 块石头分成两堆 7 和 1，即 8->7+1，那么如果 Alice 采用最佳策略（最优），Bob 就不可能获胜。然而答案是鲍勃。有人可以帮我找出答案是 Bob 的原因吗？我认为我在上面标记为最重要的陈述在这个答案中很重要，但我还无法弄清楚。任何人都可以帮忙吗？您可以参考此链接，该链接在“Grundy's Game”的 Wikipedia 上显示完全相同的插图

任何基本的想法也值得赞赏。

伙计们，这正是我面临的问题。任何小想法也值得赞赏。

格兰迪的比赛扩大到两个以上

4

2 回答 2

2

如果爱丽丝先走，她可用的任何动作都不会让她获胜。用尽证明：

如果 Alice 将棋子分成5,2,1，则 Bob 以下列方式获胜：

  1. 轮到鲍勃了。5,2,1->4,2,1,1
  2. 轮到爱丽丝了。她唯一合法的举动是将四人分开。4,2,1,1->3,2,1,1,1
  3. 轮到鲍勃了。3,2,1,1,1->2,2,1,1,1,1
  4. 轮到爱丽丝了。没有可用的动作。爱丽丝输了。

如果 Alice 将棋子分成4,3,1，则 Bob 以下列方式获胜：

  1. 轮到鲍勃了。4,3,1->3,3,1,1
  2. 轮到爱丽丝了。她唯一合法的举动是三分。3,3,1,1->3,2,1,1,1
  3. 轮到鲍勃了。3,2,1,1,1->2,2,1,1,1,1
  4. 轮到爱丽丝了。没有可用的动作。爱丽丝输了。

如果 Alice 将棋子分成7,1，则 Bob 以下列方式获胜：

  1. 轮到鲍勃了。7,1-> 4,2,1,1（请注意，根据维基百科的“仅分成两堆”规则，这一举动是不可能的，但在 OP 的“分成任意数量的堆”规则下是不可能的。）
  2. 轮到爱丽丝了。她唯一合法的举动是将四人分开。4,2,1,1->3,2,1,1,1
  3. 轮到鲍勃了。3,2,1,1,1->2,2,1,1,1,1
  4. 轮到爱丽丝了。没有可用的动作。爱丽丝输了。

如果 Alice 将棋子分成6,2，则 Bob 以下列方式获胜：

  1. 轮到鲍勃了。6,2->4,2,2
  2. 轮到爱丽丝了。她唯一合法的举动是将四人分开。4,2,2->3,2,2,1
  3. 轮到鲍勃了。3,2,2,1->2,2,2,1,1
  4. 轮到爱丽丝了。没有可用的动作。爱丽丝输了。

如果 Alice 将棋子分成5,3，则 Bob 以下列方式获胜：

  1. 轮到鲍勃了。5,3->3,3,2
  2. 轮到爱丽丝了。她唯一合法的举动是三分。3,3,2->3,2,2,1
  3. 轮到鲍勃了。3,2,2,1->2,2,2,1,1
  4. 轮到爱丽丝了。没有可用的动作。爱丽丝输了。
于 2012-03-20T17:38:30.537 回答
0

如果爱丽丝发挥最佳，我看不出鲍勃能以任何方式赢得这场比赛。维基百科正确地解释了它。如果两个玩家都玩得最好，并且如果 8 是初始棋子数，那么 Alice 应该会赢。因为在 1 个完整回合之后（都需要 1 轮），Alice 总是可以使用配置 4+2+1+1 强制执行 Bob。从这个配置中，Bob 所能做的就是 3+1+2+1+1 因此 Alice 获胜

于 2012-03-20T17:21:19.237 回答