先取者有没有必胜策略

abababa

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

色k

用 $(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$ 那堆取两个，就赢了。


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

abababa

回复 2# 色k

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

色k

这么多记不清……不过没所谓了，反正我没研究过，平时很少玩这类题，昨晚也是闲着无聊才想了出来，多堆的估计我也搞不定……

abababa

回复 4# 色k

就是这种游戏。黑色的竖是局面，红蓝分别表示两个人，一次只能划同一行里的竖线，并且要连续着划，比如红的把第三行中间那个划下去了，蓝的就不能一次性划掉第三行剩下的两个。当时听别人说只有四行时先划的必胜，但不知道是不是证明过的。

色k

回复 5# abababa

这样的话不是一两行都是先手胜吗？三行确实是先手败，所以四行先手胜，五行以上就很难判断了……

abababa

回复 6# 色k

确实，四行时把四的一行全划掉就胜了。所有这些胜负的局面，存在性很好理解，但构造出来就不容易了。

realnumber

感觉2楼解答好神奇