mathe 发表于 2008-3-20 14:25:58

天使和魔鬼问题

有趣的数学游戏转自: http://tieba.baidu.com/f?kz=342050154
题目不算太难,大家好好想想看,该如何解决。

在一个无限大的国际象棋棋盘里,天使和魔鬼玩猫捉老鼠的游戏.

游戏规则如下:

1,初始时天使在棋盘上,每回合可以向上、下、左、右四个方向中任一方向走任意不超过N格的步数,但天使不可以不走
2,魔鬼每回合可以在棋盘中除天使当前所在位置的任何一格步下陷阱。陷阱是永远存在且可见的,天使不能越过陷阱
3,天使与魔鬼都是完全理性的

请问:天使永远不会被魔鬼抓住所需N的最小值是多少?

mathe 发表于 2008-3-21 12:18:49

原先想错了,现在基本证明了对于N=2的情况,恶魔总可以构造一个边长不小于820*sqrt(2)的正方形将天使给框住。午饭后在给出我的策略。所以可以知道N>=3,不过估计N=3时天使可以逃跑了。

mathe 发表于 2008-3-21 13:21:40

考虑天使每步可以走两格的情况
如下图(黑点代表陷阱)开始恶魔可以不管天使的行走路线,先选择了一个充分大的斜向的正方形,

在这个正方形的边界上每10个格子下一个陷阱,也就是两个陷阱之间有9格是空的。然后对于四个角上附近
的18个格子(不包含已经下过陷阱的角)也都事先填上格子。
对于这个正方形(4个顶点坐标为(-L,0), (L,0), (0,-L),(0,L) ), 4条边上共有4L个格点,
上面过程共需要布置4L/10+72个格点。
假设开始天使在原点(坐标(0,0)),那么天使需要L/2步才能够走到上面正方形的边界
所以只要取L充分大,可以使得上面过程布置好以后,天使至少还需要10步才能够到达边界(取L>=820就可以)
在接下来的过程中,每次恶魔看天使离正方形哪条边最近,在天使在这条边的投影位置最近的一个空闲的格点上下陷阱。
假设在所有格子都布置好以后,天使向着某条边走去,总共花了K($>=$9)步达到离边界只有一步的位置(可以不是第一次到达)。
我们查看整个天使走过的位置在这条边上的投影,可以看出投影的长度不超过$K*sqrt(2)$。而天使占用这头尾K+1个位置的
时候,恶魔可以依次在投影位置(没地方下时会下到外面)布下K+1格陷阱。由于边上每两个格点之间距离为$sqrt(2)$,两边各延长
0.5或1的长度后最多还是只有K+2个格点,延长以后的这不超过K+2个格点上如果都有陷阱显然已经可以挡住天使的脚步了。
由于$K>=9$所以这条投影上本身已经至少包含一个预先布置的陷阱,所以只要这K+1步覆盖了这个延长的投影上,显然就可以挡住天使了。
而上面过程是否可以覆盖这个延长的投影线我没有证明,不过如图看上去是比较明显可行的(红色为天使行走路线,蓝色为投影)。

gxqcn 发表于 2008-3-21 13:28:42

不容易啊,楼主辛苦了!

友情提醒:第一幅图点击后可放大浏览(这样才有比较好的效果)。

mathe 发表于 2008-3-21 13:49:21

奇怪,我怎么不需要点击放大

gxqcn 发表于 2008-3-21 14:20:45

那是因为楼主的屏幕分辨率已足够大,可以不必缩放即可显示全图片。:)

可做如下实验体验之:
1、打开本帖;
2、将浏览器窗口缩小,小到无法显示第二幅图;
3、按 Ctrl+F5 刷新
再浏览帖子,就会发现图片被自动缩小了,由于抽点算法缘故,有些竖线就没有了,点击一下即可放大浏览(支持鼠标滚轮缩放)。

zgg___ 发表于 2008-3-21 16:26:26

这题是很难的呀。

记得原问题和这里的问题的提法有两个区别:
1、天使可以不走,魔鬼可以在任意的位置挖坑,当然也包括天使所在的格子了,每次天使行动之后检验天使是否落入了陷阱。
2、天使是会飞的。要么怎么叫天使呢?但是他飞了N格后就累了,要休息一下,就要落地了,而地面由魔鬼管的。呵呵。
我想按照原题的问法或许就比现在的问法更加简单明确了。

我们可以看到,每进行一个回合,情况就向对魔鬼有利的方向发展了一步。因为天使没有得到什么,而魔鬼却在棋盘上多留下了一个陷阱。我们可以看到,如果棋盘是宽度有限而长度无穷的带子,天使就死定了。
正是因为这个游戏中的天使不是那么好跑掉,所以问题挺难的。

mathe 发表于 2008-3-21 16:35:00

不过如果可以飞过坑的位置那就更加难了,估计N=2魔鬼都很难抓住

zgg___ 发表于 2008-3-21 16:55:56

看来有了一些结果了
http://arxiv.org/abs/0706.2817v1

zgg___ 发表于 2008-3-21 17:02:24

好像不能传附件呀。
给链接吧:http://arxiv.org/PS_cache/arxiv/pdf/0706/0706.2817v1.pdf
页: [1] 2
查看完整版本: 天使和魔鬼问题