天使和魔鬼问题

mathe

转自: http://tieba.baidu.com/f?kz=342050154
题目不算太难，大家好好想想看，该如何解决。

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

游戏规则如下：

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

请问：天使永远不会被魔鬼抓住所需Ｎ的最小值是多少？

mathe

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

mathe

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

在这个正方形的边界上每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

不容易啊，楼主辛苦了！

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

mathe

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

gxqcn

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

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

zgg___

这题是很难的呀。

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

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

mathe

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

zgg___

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

zgg___

好像不能传附件呀。
给链接吧：http://arxiv.org/PS_cache/arxiv/pdf/0706/0706.2817v1.pdf