来源:武汉英中 周粟
编辑：Gemini
大家有看过《美丽心灵》的电影吗？男主角原型是约翰·纳什，生于1928年6月13日。著名经济学家、博弈论创始人。前麻省理工学院助教，后任普林斯顿大学数学系教授，主要研究博弈论、微分几何学和偏微分方程。由于他与另外两位数学家在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博弈论和经济学产生了重大影响，而获得1994年诺贝尔经济学奖。
记得在初中时读过一篇关于博弈论的精典文章一一囚徒困境
假设警察局抓住了两个合伙犯罪的嫌疑犯，但获得的证据并不十分确切，对于两者的量刑就可能取决于两者对于犯罪事实的供认。警察局将这两名嫌疑犯分别关押以防他们串供。两名囚徒明白，如果他们都交代犯罪事实，则可能将各被判刑5年；如果他们都不交代，则有可能只会被以较轻的妨碍公务罪各判1年；如果一人交代，另一人不交代，交代者有可能会被立即释放，不交代者则将可能被重判8年。
对于两个囚徒总体而言，他们设想的最好的策略可能是都不交代。但任何一个囚徒在选择不交代的策略时，都要冒很大的风险，一旦自己不交代而另一囚徒交代了，自己就将可能处于非常不利的境地。对于囚徒A而言，不管囚徒B采取何种策略，他的最佳策略都是交代。对于囚徒B而言也是如此。最后两人都会选择交代。因此，囚徒困境反映了个体理性行为与集体理性行为之间的矛盾、冲突。
ok,今天的数学社让我们一起来玩个游戏吧！
首先，看看一个耳熟能详的例子：
1.如果有50个小球，A和B两个人轮流从中取出1到6个小球，但不能不取，规定A先取，且如果一个人没有球可以取就输了。他们都很聪明，且想赢，那么谁会赢呢？
2.其他条件不变，但是如果有49个小球呢？
好的，那么因为A和B都非常聪明，所以如果某个人要赢的话，必须制定一个可实施且不给对手留任何机会的对策。具体什么意思呢？我们先看看A的对策吧。A是这样想的，我和B都可以取1到6之间任意的数量，不管他取什么，我都得有一个对应的取法，而且保证我始终占优势。B是这么想的，如果我最后要赢，那么剩下的球必须是1到6个，所以我得保证A把球取的只剩1到6个，如果有8个球，那A可以只取1个，然后我不论取什么数，剩下的都是1-6个，如果只有6个，A又可以直接取完，所以我必须让最后只剩7个球的时候让A来取。不巧的是，A也想到了。A现在想，在最后7个球的时候让B来取，相当于是在剩8到13个球时我来取，也相当于在最后14个球的时候让B来取，以此类推，每次剩7的倍数个球的时候，我都必须让B来取，现在50个球，我只要取一个不就赢了吗？B也琢磨着，如果A开始只取一个，然后每次我取x个球，他就取7-x个，最后一定是他获胜，看来我是没有一点获胜的希望了啊。
1.所以说在第一问里，获胜的人是A。每次A取的时候都将球数取成7的倍数，而每次B取的时候不得不把球数取成非7的倍数。这样一来最后取完所有球的A就赢了。
2.如果只有49个球的话，那么A不得不将球取成非7的倍数，这样B就用前一问中A的套路便可以赢了。
这种问题有一个更专业的名字，叫ICG（ImpartialCombinatorial Games），是什么意思呢？ICG游戏满足以下几个条件：1.两个无失误且想获胜的人轮流进行操作；2.他们可进行的合法操作的集合不随当前状况或者以前的操作的改变而改变；3.最后无法进行合法操作的人判断为输。
上面举的取球例子。就是ICG。
在ICG游戏里，有一个递推关系：
1.在任何必胜状态，都存在至少一种操作，使其变为必输状态；
2.在任何必输状态，所有合法操作，都使其变为必胜状态。
满足这种递推关系，就必有一方输掉游戏，一方赢得游戏。在取球游戏中，必输状态是“球的个数是7的倍数”，必胜状态是“球的个数非7的倍数”。其中如果“球的个数是7的倍数”，那么任何合法操作，也就是取1到6 个，都会进入一个“球的个数非7的倍数”的状态；然后至少有一种合法操作，使得状态由“球的个数非7的倍数”变成“球的个数是7的倍数”，也就是取“球数模7的余数”。因此必有一方获胜，A或B，取决于开场的球数。
下面我们来看看另一种特殊的ICG：如果黑板上有1到n这n个数，每次操作的时候都从黑板上选择一个数，然后擦去这个数所有的约数。例如选择6，就该擦去1,2,3,6这四个数。那么A和B谁会赢呢？（操作顺序和获胜条件不变）
为什么说这是个特殊的ICG？因为在这种游戏里，只有先手才能获胜。（这种游戏还包括五子棋。在五子棋里，如果先手完美操作，是不可能输的。为了避免先手的压倒性优势，禁手这个规则就被发明出来了。）你可能会想，凭什么呀？难道无论n是多少，一开始都是必胜状态？答案是肯定的。
下面我们来证明：
如果一开始是必胜状态，那么A获胜；
如果一开始是必输状态，意味着不管A选择什么数，接下来都是一个必胜状态。那么考虑A一开始选择1的情况，那么B根据假设处于必胜状态，假如B选择数x，则接下来，A处于必输状态；再考虑A一开始选择x的情况，此时的状态与先选择1后再选择x的效果是一样的，根据上次考虑的结论接下来的B处于必输状态，也就是说A处于必胜状态，这与假设不符。所以假设不成立。
所以，A始终处于必胜状态且会赢得游戏。
上面是个巧妙的证明，避免了复杂的对策分析。
作者简介：周粟，男，武汉外国语学校高二年级学生。爱好数学、计算机编程、足球等，初中时以满分成绩获得全国中学生数学联赛一等奖，高一年级参加AMC12获得109.5分，成功晋级AIME；2016年参加全国青少年信息学奥林匹克竞赛NOIP获全国一等奖。自创“COOL数学”数学公众号，旨在交流学习心得，传播数学文化。
