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会超过边界，矛盾。
综上所述，命题成立。
(貌似是加拿大某年数学国家集训队的题)