题面据 IMO Shortlist 可核档案整理;中文题意为本站自译,公式请以原始来源为准。
A hunter and an invisible rabbit play a game in the Euclidean plane. The hunter's starting point coincides with the rabbit's starting point . In the round of the game , the following happens. (1) First the invisible rabbit moves secretly and unobserved from its current point to some new point with . (2) The hunter has a tracking device (e.g. dog) that returns an approximate position of the rabbit, so that . (3) The hunter then visibly moves from point to a new point with . Is there a strategy for the hunter that guarantees that after such rounds the distance between the hunter and the rabbit is below 100 ?
猎人和隐形兔子在欧几里得平面上玩游戏。猎人的起点与兔子的起点重合。在游戏 的第 轮中,会发生以下情况。 (1) 首先,隐形兔子从当前点 秘密且不被观察地移动到某个新点 ,其中 。 (2) 猎人有一个跟踪设备(例如狗),它返回兔子的大概位置 ,使得 。 (3) 然后猎人明显地从点 移动到新点 ,其中 。猎人是否有一种策略可以保证在 这样的回合之后猎人和兔子之间的距离低于 100 ?
提示 1
先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。
提示 2
找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。
提示 3
把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。
完整解答
这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2017 年 IMO Shortlist C5 可先归入组合:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。
这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?