k倍动态减法游戏

superacid

k倍动态减法游戏：
两个人玩游戏，有一个整数S(S>=2)，第一人在S上减掉一个数x，至少是1，但小于S。之后双方轮流把S减掉一个正整数，但都不能超过先前一回合对方减掉的数的k倍(k是正整数)，减到0的一方获胜。问：谁有必胜策略。

tm__xk

k=3,我推的怎么是4,6,8,11,15,21,28,38?

15->21那步有点奇怪..是不是我弄错了..

lulijie

k=3:
必败局面
s=2,3,4,6，8,11,15,20......
从s=6开始，后面的每项都等于前面的项+1+{前面的项/3}      {X}表示比X小的最大整数。
--------------------------------
对于任意的k，
s=2,3，......，k，k+1，k+3，......
从s=k+3开始，都有后面的每项都等于前面的项+1+{前面的项/k}

tm__xk

可计算?你是指通项公式?

superacid

谁能提供一个k=3的可计算的解答？

tm__xk

或者说异或.
那题本区出现过了..

superacid

你说的那道题简单多了，经典的NIM游戏，写成二进制按位相加考虑就可以了

tm__xk

递推公式不难,问题是要通项公式..

lulijie

我来谈谈自己的思路：
对于s和k，若先行方必胜，记做g(s,k)=1，反之记做g(s,k)=0
对于前一次对手取x，剩下还有s，若此次选手必胜记做f(s,x,k)=1，反之记做f(s,x,k)=0.
所以有以下递推公式：
f(0,n)=0
g(s,k)=Not (∏f(s-x,x,k))   ,   x=1 to s-1           Not(x) 表示x为1，等于0；x为0,等于1
f(s,y,k)=Not( ∏f(s-x,x,k))  ,   x=1 to yk
－－－－－－－－－－－－－－－－－－－－－－－－
当k确定时，可以把函数f、g括号里的k省略掉
从以上递推公式，可以推出
k=2时：   
f(1,n)=1             g(2)=Not(f(1,1))=0
f(2,n)=1            g(3)=Not(f(2,1)*f(1,2))=0
f(3,1)=0            g(4)=Not(f(3,1)*f(2,2)*f(1,3))=Not(0)=1
f(3,n)=1    n>1
f(4,n)=1            g(5)=Not(f(4,1)*f(3,2)*f(2,3)*f(1,4))=0
f(5,1)=0            g(6)=Not(f(5,1)*......)=Not(0)=1
f(5,2)=0            g(7)=Not(f(5,2)*......)=Not(0)=1
f(5,n)=1  n>2
......................
对于其他的k值，利用电脑的高速计算力，结合上述递推公式，应该能很快计算出来。

tm__xk

两题差得远了....