取球问题的博弈分析

问题描述

    这是一个今天和别人讨论的时候碰到的一个问题，其实很早以前在初中读书的时候，发现一些数学竞赛也出过类似的问题。这里问题提到的是假设我们有两个人A和B，他们要轮流从100个球里面来取球出来。一个人每次只能取1到5个球，不能不取。假定A先取，我们设定取走最后几个球的人获胜，那么这其中有什么策略吗？

 

分析

    对于这个问题，我们可以从最小的范围来往大的范围扩展。这两个人他们每次只能取1到5个球，所以他们两个一轮最多能取的球是10个，最少能取的球是2个。我们可以来画一个如下的表：

 

	1	2	3	4	5	6	7	8	9	10
A
B

    这里数字1到10表示假设总共的球的个数。所以当最开始球的数量为1到5的时候，我们最先取的A肯定会胜利，因为他可以一次将所有的球都取走。所以我们可以得到从1到5, A必然胜的结果。如下表：

	1	2	3	4	5	6	7	8	9	10
A	*	*	*	*	*
B

    我们这里用星号表示胜利的一方。再往后面看的话，当我们有6个球的时候，我们知道，A必须要至少取一个球，如果他取了的话，则剩下的球则最多为5最少为1, 这样B则必然胜利。所以对于6个球的场景，先取的必然输。然后我们再来看7个球的。既然6个球使得先取的人必然输，而A想要赢的话，必然会尽量构造出剩下的球为6的场景。所以对于后面的6 + 1到6+5的范围，A先取的必然会获胜，只要他构造出这个6来就赢了。于是按照这个思路，剩下的从7到10, 甚至到11, 先取的A也必然获胜。

    这样，得到的一个结果如下表：

	1	2	3	4	5	6	7	8	9	10
A	*	*	*	*	*		*	*	*	*
B						*

    因为这里的场景比较简单，我们再进一步的扩展。这里是针对10个的范围。假设有两个6, 也就是说12个球呢？实际上一样，在这12个球的场景下，我们只要保证后面取球的人和前面取球的人一轮中取的球的个数为6,则必然后面取球的人获胜。

    有了这一步的分析，后面的问题就更加简单了。这就好比是一个坑。谁要是碰到这个6的倍数的数字，他就掉坑里没戏了。而针对总共的球数，有没有办法来判断谁会胜利呢？我们可以用100来对6取模。如果这个数字能被6整除，说明先取的人正好是从6的整数倍开始取的，他最后就必然会输。而如果这个数不能被6整除，则先取的人可以把那些零头去掉，使得剩下的数字刚好构成6的倍数，于是后面取的那个人就输了。

    所以所以，说了这么多的所以，这个问题其实再简单不过了。就是将球的总数对6去求模，如果为0则先取的输，否则后取的数。

    好了，这么简单的破问题，总不要我来写代码了吧？

 

总结

    其实对于这一类的问题分析也是有它的套路的。这里虽然牵涉到了博弈论的一些思路。当然，因为我们这里分析的问题场景还是比较简单，可以一个整除判断就解决问题。在一些真正具体实现的问题里，我们可能还需要用到一些动态规划的思想，将前面一些推导的结果保存起来，以方便后面的论证。当然，这些问题也就是只要掌握了套路之后就没什么了，虽然有一种让人觉得怒刷存在感的格调。