拿球必胜策略

Buffalo

有N个球，两人轮流拿，第一次可以拿1~N-1个，之后后一个可以拿1~k*对方上次拿的个数，拿到最后一个球的获胜。
问什么情况下存在先手必胜、后手必胜或无必胜策略。
已有结果：k=2时对属于菲波那契数列的N先手必败，其余的先手必胜。

mathe

好像结果是除掉前面若干项以后，所以先手负的情况构成的数列可以写成
$f(n+h_k+1)=f(n+h_k)+f(n)$,其中$h_k$是一个适当的只同k有关的数

056254628

引用2楼的数列递推公式，那么$h_k=2*k-3$
k＝2时，刚好 f(n+2)=f(n+1)+f(n)   就是菲波那契数列

056254628

k=2    N=2,3,5,8,13,21,34,55,89,144,233,377,610,987,
k=3    N=2,3,4,6,8,11,15,21,29,40,55,76,105,145,200,276,381,526,726,
k=4    N=2,3,4,5,7,9,12,15,19,24,31,40,52,67,86,110,141,181,233,300,386,496,637,818,
k=5    N=2,3,4,5,6,8,10,12,15,18,22,27,33,41,51,63,78,96,118,145,178,219,270,333,411,507,625,770,948,
k=6    N=2,3,4,5,6,7,9,11,13,16,19,23,27,32,38,45,54,63,74,87,103,122,145,172,204,242,287,341,404,478,565,668,790,935,
k=7    N=2,3,4,5,6,7,8,10,12,14,16,19,22,26,30,35,40,46,53,61,71,83,95,109,125,144,166,192,222,257,297,343,396,457,528,611,706,815,940,
k=8    N=2,3,4,5,6,7,8,9,11,13,15,17,20,23,26,30,34,39,44,50,57,65,74,85,96,109,124,141,161,184,207,233,263,297,336,380,430,487,552,626,711,807,916,
k=9    N=2,3,4,5,6,7,8,9,10,12,14,16,18,20,23,26,29,33,37,42,47,53,59,66,74,83,93,105,117,131,147,165,185,208,234,260,289,322,359,401,448,501,560,626,700,783,876,981,
k=10    N=2,3,4,5,6,7,8,9,10,11,13,15,17,19,21,24,27,30,33,37,41,46,51,57,63,70,77,85,94,104,115,128,141,156,173,192,213,237,261,288,318,351,388,429,475,526,583,646,716,793,878,972,

经检验：当k<=5时，3楼的式子才成立。

Buffalo

按照上面的数据总结，2楼的猜想是不对的，但是除了2~k+1这些数(原则上1也应该算成必败数)显然地必败之外，后面的两个相邻必败数之差必定也是个必败数，这点还是对的。

Buffalo

请检验一下数据，因为新数列$c_i=b_{i+k+1}-b_{i+k}$的元素虽然都在数列$b$中，但是除了开头一部分外后面仍然不断地有重复的数出现。

4# 056254628

mathe

检验到10^8以内:
K=3, n>=5,a[n]=a[n-1]+a[n-4], 共检查55个元素
K=4, n>=8,a[n]=a[n-1]+a[n-6],共检查70个元素
K=5, n>=10,a[n]=a[n-1]+a[n-8],共检查84个元素
K=6, n>=18,a[n]=a[n-1]+a[n-11], 共检查102个元素
K=7, n>=23,a[n]=a[n-1]+a[n-14],共检查119个元素
K=8, n>=31,a[n]=a[n-1]+a[n-17],共检查135个元素
K=9, n>=36,a[n]=a[n-1]+a[n-20],共检查150个元素
K=10, n>=39,a[n]=a[n-1]+a[n-23],共检查165个元素

mathe

再给个数据，
K=20时，从第108个元素开始，满足a[n]=a[n-1]+a[n-60]检查了前319项
K=21时，从第117个元素开始，满足a[n]=a[n-1]+a[n-64]检查了前334项

mathe

有N个球，两人轮流拿，第一次可以拿1~H个，之后后一个可以拿不超过K*对方上次拿的个数，拿到最后一个球的获胜。
问什么情况下存在先手必胜、后手必胜或无必胜策略。
我们知道对于充分大的H(比如$H>=N$),先手必胜。而且如果对于参数<N,H,K>先手必胜，那么对于任意$H'>=H$,<N,H',K>也是先手必胜。
于是对于每个N,K组，存在最小的H使得<N,H,K>.我们把这个H称为N,K的H函数，记为$H_K(N)$
于是我们知道，对于原题，如果$H_K(N)=N(N>=2)$,那么先手败，不然先手胜。
所以我们的任务转化为计算函数$H_K(N)$

mathe

显然$H_K(N)$在$1<=N<=K+1$时有$H_K(N)=N$,同时我们定义$N_K(0)=+infty$
而且对于任意N>K,我们有性质
$H_K(N)=min{t|1<=t<=N,H_K(N-t)>tK}$