首页 > 试题广场 >

设有k≥1堆硬币,各堆分别含有n1,n2...nk枚硬币。

[问答题]

设有k1堆硬币,各堆分别含有n1,n2...nk枚硬币。

游戏中两个人交替拿取硬币,每次只能从剩余硬币数大于0的其中一堆取走任意数量硬币(至少1枚,至多取完),取走最后一枚硬币的人取胜。在游戏双方均足够理智的情况下,给出先手必胜的条件。

该问题属于尼姆博弈问题的推广,若要先手必胜只需要n1,n2,...,nk中硬币的个数按位异或,即n1xor n2 xor n3 ... xor nk 不为零就行了。
发表于 2019-04-23 15:57:21 回复(0)
n,m问题,总体堆的异或运算不为0,就好了
发表于 2019-04-19 23:12:08 回复(0)
k=1时必胜
k=2且n1不等于n2时,必胜策略是每次拿多的让两堆相等
k=3且存在两堆相等时,必胜策略是把另外一堆全拿走,收敛为k=2的情况。
k=3且每堆都不等时,推不出来了……太复杂了
发表于 2019-04-12 16:29:00 回复(0)