捉马

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

类似困兽斗游戏

账号		自动登录	找回密码
密码			欢迎注册

[提问] 捉马

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。