需要竞争性编程手册中的 Grundy 数字的解释

Question

我正在尝试理解 https://cses.fi/book/book.pdf 一书中第 239 页的示例。 示例描述如下：

我不明白的是，右下角旁边的数字 3 的意思是，我们可以向上移动 4 步，向左移动 3 步，为什么是 3？与它上面的 4 相同，它不对应于我能想到的任何一组动作。总的来说，这本书做了很多他们认为显而易见的逻辑跳跃，但通常我可以在一段时间后推断出它们的意思，在这里我只是迷路了。

Answer 1

计算这些数字的规则是递归的。

你考虑所有你能达到的值，然后选择最小的（non-negative）不可达到的整数。

例如，top-left 角的值为 0，因为无法移动。

例如，右下角旁边的值是 3，因为可达值是 0,4,1,0,2,1,4，所以 3 是不在此列表中的最小整数。

这解释了如何计算数字，但要理解它们最好从理解 Nim 的游戏开始。在 Nim 游戏中，一堆的 Sprague Grundy 数等于一堆的大小。