KeyTo9_Fans 发表于 2010-11-9 00:59:57

捉马

在无限大的正方形网格中心有一只马。

这只马的走法与中国象棋的马的走法相同。

这只马每走一步，我们就在某个格子上放一个障碍。

这只马不能走到障碍上，而且当这只马与障碍相邻的时候，障碍会憋马腿。

这只马是绝顶聪明的。

问我们能否困住这只马？

如果能，需要多大的场地和步数？

如果不能，如何证明？

gxqcn 发表于 2010-11-9 07:49:22

怎么才叫“困住”？
是指无法再走下一步，且有空白区域吗？
（最后那句是我想象补充的）

mathe 发表于 2010-11-9 08:41:18

可以定义为无法再走下一步。
实际上，只要有厚度为2的边界将它围住，肯定困住了

mathe 发表于 2010-11-9 08:49:56

由于有蹩马腿，厚度为1的正方形围住就可以了

gxqcn 发表于 2010-11-9 09:23:26

2# gxqcn

早上我将“这只马每走一步，我们就在某个格子上放一个障碍”
误读成了“这只马每走一步，我们就在这个格子上放一个障碍”。

风云剑 发表于 2010-11-9 09:28:18

做成个游戏不错:)

zgg___ 发表于 2010-11-9 10:37:54

这个问题貌似是Angel problem的一个变种，可以参见"http://en.wikipedia.org/wiki/Angel_problem"。
在提出这个问题的文章（参见http://library.msri.org/books/Book29/files/conway.pdf）里说：“如果天使是按照国际象棋里的王走，那么Berlekamp证明了在32乘33的范围内，天使就会被抓住。如果天使按照国际象棋里的马走，那么好像是困不住的。”在文献"András Máthé, The angel of power 2 wins, Combin. Probab. Comput. 16(3):363-374, 2007"（请注意作者的名字，呵呵。）中说，天使按照国际象棋里的王1次走2步，就不会被困住了。而楼主的问题恰好在这些结论之间。

mjs1wh 发表于 2010-11-13 14:30:37

类似困兽斗游戏
页: [1]
查看完整版本: 捉马