Roland. P Sprague 和 Patrick M. Grundy 都是组合游戏的狂热爱好者,但他们素未谋面。
一天,Sprague 在写给 Grundy 的信中向他介绍了一个据称是来自东方的古老游戏一一取石子。
取石子是一个双人博弈游戏。在游戏的一开始,桌面上有几堆石子堆。接下来,游戏双方轮流进行操作:从桌面上选取一堆石子堆,然后从这一堆里面取走任意多个石子(但不能不取)。当某个人无法操作时则失败,另一方获得胜利。由于条件所限,Sprague 建议在纸上写一排自然数来代表各个石子堆的石子数目,然后两人轮流划数与数;Grundy 欣然应允。
一个月过去了,在 Grundy 连续输了五盘游戏之后,他怀疑 Sprague 要诈。经过几天的研究,Grundy 在某天下午发现假设游戏双方都足够聪明,那么给定一个初始状态(一排自然数),可以有很简单的方法来判定先手必胜还是后手必胜,并且可以给出必胜策略!于是 Grundy 决定要进行反击。
翌日,Grundy 在写给 Sprague 的信中建议把游戏的规则改得更复杂一点:首先确定一个常数 KKK。然后,游戏双方的操作改为:每次选择一个数划掉。假设该数为 xxx,操作者可以任选一个正整数 aaa,在划掉之后需要再写上 x−a,x−2a,…,x−Kax-a,x- 2a,\ldots,x-Kax−a,x−2a,…,x−Ka 共 KKK个数,且 aaa 需满足 x−Ka≥0x-Ka \geq 0x−Ka≥0。若这样的 aaa 不存在,那么操作者就不能划掉这个 xxx。某一方失败的条件依然是他无法操作。
碍于面子,Sprague 当然无法拒绝。不过他也不会坐以待毙,现在他已经得到了这个 KKK 和写在纸上的 nnn 个数。他把这些数据和这个游戏的规则都告诉了你一一John von Neumann——正在研究如何使用一个尚不存在的机械(你将其命名为计算机)来解决实际问题的数学、物理、经济学(、计算机科学)家。