数30游戏的一些思考

大家好，欢迎来到IT知识分享网。

数30

昨天看了向往的生活第四季小岳岳那期玩了个游戏，叫数30。游戏有两个人玩，一个人最多可以数两个数，数到30的人算输。当时觉得这个游戏应该有必胜的方法，后来想了想，确实有些规律。

数30

为了好推导，我将游戏用数学化公式表达。数到n能赢表示1，会输表示0。例如f(30)=0，f(29)=1。

1. f(30)=0好理解，那么f(29)=1呢，因为当你数到29，对方一定会数30，对方就输了，所以当你数到29时是一定会赢的。
2. 那么f(28)等于多少呢？当你数28时，对面可以数29，而f(29)=1，因此对面赢了，可知f(28)=0。
3. 注意，f(n)=1指的是存在特定的方法使你一定获胜，而并非无论怎样你都能获胜；同样值为0表示对面有特定的方法让你一定输，而并非无论如何你都会输。比如当你数28时，对面可以数29，也可以数29、30。但是对面一定有一种方法让你输，那就是数29。
4. 现在我们知道f(30)=0, f(29)=1, f(28)=0。那么当你数27时，对方可以数28或者28、29，我们知道f(29)=1，因此只要对方数到29，你一定会输，f(27)=0。
5. 由此我们可以得出一些规律了，要考虑f(n)的值为1还是0，只要考虑是否能在下两步是否能达到1，即f(n+1)=1或者f(n)=1。若两者存在一个成立，那么对面就能赢，f(n)=0，否则f(n)=1。
6. 至此可以推出，值为1的步数为：29，26，23，20，17，14，11，8，5，2。只要你抢到其中某一个节点，你都能数这些数字获胜。当然如果双方都知道这个规律，那么谁先数，谁获胜（先数的人可以数1、2，抢到2之后再按照5、8、11…这个规律数下去就一定能赢）。

数$N$

考虑一般情况，每个人最多数$m$个数，数到$N$的人算输，是不是先数的人一定会赢呢？

1. 由上面的推论易知，$f(N)=0$， $f(N-1)$=1
2. 考虑数$n$时，如果在$m$步以内可以达到$f(n+i)=1,i\in [1,m]$，那么对方赢，$f(n)=0$。由此可见，在$N-1$之前的$m$步，都为$0$，之前的第$m+1$步，即$f((N-1)-(m+1))$为1。同理，第$(N-1)-(m+1)$步之前的第$m+1$步为1。这样就形成了周期为$m+1$的循环。
3. 至此我们有了两个结论，1. $f(N-1)=1$，2. $f$是一个周期为$m+1$的函数。
4. 根据第3点的结论，我们就可以找到必胜的方法了。只要知道第一个值为1的$n$，下面只要以$m+1$的周期数下去就好了（为什么一定能数到，大家可以自己想一下）。
5. 如何找到第一个值为1的$n$呢？也很简单，直接给出结论吧
   $$n=(N-1)\%(m+1)$$其中$\%$表示取余。如果$n=0$，那么取第一个数为$m+1$就好了。
6. 回到最初的问题，是不是所有情况先手就能赢呢？答案是否定的。回到上面的式子，如果$n=0$，那么第一个值为1的数是$m+1$，你无论如何都抢不到这个数(因为最多只能数到$m$)，而会被对面抢到，这样你就输了。

代码

goal = 30 step = 2 value = [0] * (step - 1) + [0, 1] for i in range(goal - 2, 0, -1): if 1 in value[-1:-(step + 1):-1]: value.append(0) else: value.append(1) value = value[:(step-2):-1] for i, v in enumerate(value): print("{}: {}".format(i + 1, v)) 

结果

1: 0 2: 1 3: 0 4: 0 5: 1 6: 0 7: 0 8: 1 9: 0 10: 0 11: 1 12: 0 13: 0 14: 1 15: 0 16: 0 17: 1 18: 0 19: 0 20: 1 21: 0 22: 0 23: 1 24: 0 25: 0 26: 1 27: 0 28: 0 29: 1 30: 0