灯下 登录
番外 · 题谱 · 2017 · P13

2017 IMO Shortlist C5

组合 · P3/P6 · 压轴题

题面据 IMO Shortlist 可核档案整理;中文题意为本站自译,公式请以原始来源为准。

IMO Shortlist 2017 C5 combinatorics

A hunter and an invisible rabbit play a game in the Euclidean plane. The hunter's starting point H0H_{0} coincides with the rabbit's starting point R0R_{0}. In the nth n^{\text {th }} round of the game (n1)(n \geq 1), the following happens. (1) First the invisible rabbit moves secretly and unobserved from its current point Rn1R_{n-1} to some new point RnR_{n} with Rn1Rn=1R_{n-1} R_{n}=1. (2) The hunter has a tracking device (e.g. dog) that returns an approximate position RnR_{n}^{\prime} of the rabbit, so that RnRn1R_{n} R_{n}^{\prime} \leq 1. (3) The hunter then visibly moves from point Hn1H_{n-1} to a new point HnH_{n} with Hn1Hn=1H_{n-1} H_{n}=1. Is there a strategy for the hunter that guarantees that after 10910^{9} such rounds the distance between the hunter and the rabbit is below 100 ?

猎人和隐形兔子在欧几里得平面上玩游戏。猎人的起点H0H_{0}与兔子的起点R0R_{0}重合。在游戏 (n1)(n \geq 1) 的第 nth n^{\text {th }} 轮中,会发生以下情况。 (1) 首先,隐形兔子从当前点 Rn1R_{n-1} 秘密且不被观察地移动到某个新点 RnR_{n},其中 Rn1Rn=1R_{n-1} R_{n}=1。 (2) 猎人有一个跟踪设备(例如狗),它返回兔子的大概位置 RnR_{n}^{\prime},使得 RnRn1R_{n} R_{n}^{\prime} \leq 1。 (3) 然后猎人明显地从点 Hn1H_{n-1} 移动到新点 HnH_{n},其中 Hn1Hn=1H_{n-1} H_{n}=1。猎人是否有一种策略可以保证在 10910^{9} 这样的回合之后猎人和兔子之间的距离低于 100 ?

提示 1

先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。

提示 2

找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。

提示 3

把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。

完整解答

这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2017 年 IMO Shortlist C5 可先归入组合:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。

这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?