[组合] 先取者有没有必胜策略

有$X=10,Y=15$两堆苹果，$A,B$两人轮流取，规定只从一堆里取时，可以取任意大于等于$1$个，从两堆里同时取时，两边取的数量要相等，也可以取任意大于等于$1$个。取走最后的苹果就算胜。问先取的人有没有必胜策略。

分享到: QQ空间 腾讯微博 腾讯朋友

色k

2^#

发表于 2017-4-14 01:02 | 只看该作者

本帖最后由色k 于 2017-4-14 01:12 编辑

用 $(m,n)$ 表示 $X=m$, $Y=n$，
用 $(m,\ge n)$ 表示 $X=m$, $Y\ge n$，
用 $S$ 表示先手胜，$B$ 表示先手败。

显然 $(0,n)=S$, $(m,m)=S$，所以
$(1,2)=B$
则
$(1,\ge3)=S$
$(2,\ge2)=S$
$(m,m+1)=S, m\ge3$
因为这几个都能一步变成 $(1,2)$，
由此推出
$(3,5)=B$
因为无论怎么取，都会变成前面的 $S$，
所以
$(3,\ge6)=S$
$(m,m+2)=S, m\ge4$
由此推出
$(4,7)=B$
理由也是一样，怎么取都会变成 $S$，
所以
$(4,\ge8)=S$
$(m,m+3)=S, m\ge5$
推出
$(5,9)=B$
所以
$(5,\ge10)=S$
$(m,m+4)=S, m\ge6$
推出
$(6,11)=B$
……
……
如此类推，当 $m\ge3$ 时都有
$(m,2m-1)=B$
因此
$(8,15)=B$
所以对原题来说，先手从 $X$ 那堆取两个，就赢了。

其实感觉还可以写成数学归纳法的形式，有空再想想怎么表达……

这名字我喜欢

TOP

abababa

3^#

发表于 2017-4-14 17:16 | 只看该作者

回复 2# 色k

谢谢，这个题可能是从一堆里取那种变化过来的，约束条件也增加了，对于更多的，比如三堆，甚至更多堆，约束条件也不同，不知道有没有一般的方法。我记得有一个游戏，不知道叫什么名字，玩法里的约束条件现在也忘了。大概就是像杨辉三角那样画出来，第一行一竖，第二行两竖，一般的第n行n竖，然后去划掉每一行里的竖，规则之一是每次只能画同一行里的，还有，比如别人把第三行里中间的竖划掉了，自己就不能再一次性划掉第三行左右两边的竖，就是必须连续着划。其它的规则记不清了。可能是划掉最后一竖的算胜。像这类的不知道有没有一般解法。

TOP

色k