如何赢得这场比赛？

Question

支持我们有一个n*m表,两个玩家玩这个游戏.他们依次排除细胞.玩家可以选择一个单元格(i,j)并排除从(i,j)到(n,m)的所有单元格,以及排除最后一个单元格丢失游戏的人.

例如,在3*5板上,播放器1排除小区(3,3)到(3,5),播放器2排除(2,5)到(3,5),当前板是这样的: (O表示不排除单元格,x表示排除单元格)

3 O O x x x
2 O O O O x
1 O O O O O
  1 2 3 4 5

在玩家1排除从(2,1)到(3,5)的单元格后,棋盘变为

3 x x x x x
2 x x x x x
1 O O O O O
  1 2 3 4 5

现在,玩家2排除了从(1,2)到(3,5)的单元格,只留下了(1,1)清洁:

3 x x x x x
2 x x x x x
1 O x x x x
  1 2 3 4 5

因此,玩家1必须排除唯一的(1,1)单元格,因为一个玩家必须在一个回合中排除至少一个单元格,并且他输掉游戏.

很明显,在n*n,1*n和2*n(n> = 2)的情况下,第一个获胜的人获胜.

我的问题是,在所有情况下,是否有任何策略让玩家赢得比赛？他应该先打比赛吗？

PS

我认为它与动态编程或分而治之等策略有关,但尚未形成一个想法.所以我在这里发布.

答案

感谢sdcwc的链接.对于大于1*1的表,第一个玩家将获胜.证据如下:(借用维基页面)

事实证明,对于任何大于1×1的矩形起始位置,第一位玩家都可以获胜.这可以通过策略窃取论证来显示:假设第二个玩家对任何最初的第一个玩家移动都有一个获胜策略.那么假设第一个玩家只占用右下方.根据我们的假设,第二名球员对此有回应,这将迫使胜利.但如果存在这样一个获胜的回应,那么第一名球员可能已经将其作为他的第一步,并因此被迫获胜.因此,第二位玩家无法获胜.

而Zermelo的定理确保了这种获胜策略的存在.

Answer 1

这个游戏被称为Chomp.第一个玩家获胜,看到他的战略链接(非建设性的).