讨论 / 连通区域中的机器人必能重合的证明
FinalSix 2013-02-23 20:05:00
点我顶贴 收藏 删除
证:

记机器人A,B间的最短路径长度为n,对n归纳。

n=1时,B一直追着A跑,由于图有界,所以一定会重合。

若n<=k-1时命题成立,对n=k:

B行走最短路一直到A,如果在过程中A被阻挡过,那么当B到了原来A的地点后,A与B的最短路径小于k,由归纳假设,命题成立。

如果A没被阻挡,那么相当于A沿着射线BA平移了BA的长度,经过有限次重复,A会超过边界,矛盾。

综上所述,命题成立。

(貌似是加拿大某年数学国家集训队的题)

查看更多回复
提交回复