MathLabs

第3题

一名猎人和一只隐形兔子在欧几里得平面上进行游戏。兔子的起点 A0A_0 与猎人的起点 B0B_0 相同。游戏进行 n−1n-1 轮后,兔子在点 An−1A_{n-1},猎人在点 Bn−1B_{n-1}。在第 nn 轮中,依次发生三件事:(i) 兔子隐蔽地移动到点 AnA_n,使 An−1A_{n-1} 与 AnA_n 的距离恰为 11;(ii) 跟踪装置向猎人报告一个点 PnP_n,唯一保证是 PnP_n 与 AnA_n 的距离至多为 11;(iii) 猎人公开移动到点 BnB_n,使 Bn−1B_{n-1} 与 BnB_n 的距离恰为 11。无论兔子怎样移动、跟踪装置报告哪些点,猎人是否总能选择自己的移动,使得经过 10910^9 轮后可以保证自己与兔子的距离至多为 100100?
第 7/9 步:每个区块都增加距离平方
y2=d2+ε(400−2d)>d2+12y^2=d^2+\varepsilon(400-2d)>d^2+\frac12
详细分析

将 ε2+1=400ε\varepsilon^2+1=400\varepsilon 代入 y2=1+(d−ε)2y^2=1+(d-\varepsilon)^2,得到 y2=d2+ε(400−2d)y^2=d^2+\varepsilon(400-2d)。因为 d≤100d\le100,有 400−2d≥200400-2d\ge200;又因为 ε>1/400\varepsilon>1/400,所以 y2>d2+1/2y^2>d^2+1/2。因此无论猎人怎样移动,兔子都能选择两条不可区分路线中的一条,使 200200 轮后的新距离平方比原来至少增加 1/21/2。