魔方吧·中文魔方俱乐部

标题: k倍动态减法游戏 [打印本页]

作者: superacid 时间: 2010-4-2 12:45:48 标题: k倍动态减法游戏

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

作者: 裸兰 时间: 2010-4-2 12:59:15

k一定的话，第一个人必胜？还是必胜方与s有关？

作者: superacid 时间: 2010-4-2 13:04:14

就是对一定的k，求哪些S使得第一个人胜，哪些使得第二个人胜

作者: dangerxxxx 时间: 2010-4-2 14:28:03

有点难度不知道

作者: chuchudengren 时间: 2010-4-2 15:08:31

似乎只有k=1好分析，其余的情况就不知怎么入手了

作者: superacid 时间: 2010-4-2 16:05:10

据说k=2就很有难度

作者: 裸兰 时间: 2010-4-2 17:13:41

小时的的取火柴棍游戏的拓展，k要是随x变动就更有难度了

作者: superacid 时间: 2010-4-2 18:05:29 标题: 回复 7# 的帖子

这样过于不确定，就没有研究价值了

作者: tm__xk 时间: 2010-4-2 18:08:26

k=1简单..
k=2只看到一个Fibonacci..
k=3暂时找不到有价值的规律了..= =

作者: limite034 时间: 2010-4-2 23:35:30

我好想见过这道题。其大概意思是：有若干堆火柴。可以拿一堆，也可以在一堆里面拿一些。最后拿完的为输。
只要策略正确，胜负关系在比赛以前其实已经定了。在若干年前，我曾经用BASIC编过一个程序。
最后把火柴集合（堆数和每堆的数量）打印出一个对照表。只能“背”一些表（集合太大了，谁也记不住）
还有一种情况，太多数情况下，是不便于“数”数的。
我的结论：谁也没有胜负的把握！否者，就不存在这道题了！只有用计算机玩才比人脑有必胜的把握

[ 本帖最后由 limite034 于 2010-4-2 23:39 编辑 ]

作者: tm__xk 时间: 2010-4-3 00:06:11 标题: 回复 10# 的帖子

两题差得远了....

作者: lulijie 时间: 2010-4-3 00:43:54

我来谈谈自己的思路：
对于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 时间: 2010-4-3 01:21:00 标题: 回复 12# 的帖子

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

作者: superacid 时间: 2010-4-3 02:04:29 标题: 回复 10# 的帖子

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

作者: tm__xk 时间: 2010-4-3 03:55:30 标题: 回复 14# 的帖子

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

作者: superacid 时间: 2010-4-4 00:22:04

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

作者: tm__xk 时间: 2010-4-4 02:34:15 标题: 回复 16# 的帖子

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

作者: lulijie 时间: 2010-4-5 18:53:08

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 时间: 2010-4-5 19:56:48 标题: 回复 18# 的帖子

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

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)