[C] アリスの宝探し
解答
1003
解説
最大値が $N=1003$ であることを示すには、以下の命題1,2を示せばよい。
命題1: $\mathrm{T}$ の位置にかかわらず、アリスがうまく行動すれば $1003$ ターン目で確実に宝を見つけることができる。
証明: アリスは、$\mathrm{A_{1}}=(1,0)$, $\mathrm{A_{2}}=(1/2,\sqrt{3}/2)$, $\mathrm{{A_3}}=(0,0)$ と動くことにする。まず、偶然 $\mathrm{T}=\mathrm{A_{1}},\mathrm{A_{2}},\mathrm{A_{3}}$ であったときは、それぞれ $1,2,3$ ターン目の終わりに宝を見つけられる。そうでないと仮定し、$\mathrm{T}=(u,v)$ とおく。中心を$\mathrm{A_{1}},\mathrm{A_{2}},\mathrm{A_{3}}$ とする半径 $d_1,d_2,d_3$ の円をそれぞれ $C_1,C_2,C_3$ とおく。いま $d_1,d_2,d_3 > 0$ なのでこれらは確かに円であり、いずれも $\mathrm{T}$ を通る。$v=0$ のとき、$C_1$ と $C_3$ はただ一点 $\mathrm{T}=(u,0)$ を共有するので、$C_1,C_2,C_3$ の共有点は $\mathrm{T}$ だけである。$v\neq 0$ のとき、$C_1$ と $C_3$ の共有点は $2$ 点 $(u,v),(u,-v)$ だが、これらと $\mathrm{A_{2}}=(1/2,\sqrt{3}/2)$ との距離は $v\neq 0$ のとき必ず異なるので、$C_2$ が点 $(u,-v)$ を通ることはない。よってこの場合も $C_1,C_2,C_3$ の共有点は $\mathrm{T}$ だけである。したがって、$3$ ターン目の終わりにアリスは $\mathrm{T}$ を正確に特定できることがわかる。
あとはアリスが原点 $\mathrm{{A_3}}=(0,0)$ にいる状態から、特定した $\mathrm{T}$ まで $1000$ ターン以内に辿り着けることを示せば良い。$\mathrm{{TA_3}}=l$ とおく。いま、$\mathrm{T}\neq \mathrm{A_{3}}$ の場合を考えているので $0<l\leq1000$ である。
・整数 $1\leq m \leq 1000$ を用いて $\mathrm{{TA_3}}=m$ と書けるとき
このとき、アリスは $\mathrm{T}$ まで一直線に進み続けることで、$3+m\ (\leq 1003)$ ターン目で宝を見つける。
・$0<l<1$ のとき
このとき、$4$ターン目にアリスは、$\angle \mathrm{{TA_3A_4}}$ が $\displaystyle \cos\theta=\frac{l}{2}$ を満たすような角度 $\theta$ に等しくなるような方向に距離 $1$ だけ移動する。すると三角形 $\Delta \mathrm{{TA_3A_4}}$ は $\mathrm{{A_3A_4}}=\mathrm{{TA_4}}=1, \mathrm{{TA_3}}=l$ をみたすので、$5$ ターン目に $\mathrm{{T=A_5}}$ に移動することで宝を見つける。
・$1<l<2,2<l<3,\ldots, 999<l<1000$ のとき(つまり、$l$ が整数でなく、$l$ を超えない最大の整数 $m$ が $1 \leq m \leq 999$ であるとき)
このとき、$4$ターン目にアリスは、$\angle \mathrm{{TA_3A_4}}$ が $\displaystyle \cos\theta=\frac{1+l^2-m^2}{2l}$ を満たすような角度 $\theta$ に等しくなるような方向に距離 $1$ だけ移動する。すると三角形 $\Delta \mathrm{{TA_3A_4}}$ は、 $\mathrm{{A_3A_4}}=1, \mathrm{{TA_4}}=m, \mathrm{{TA_3}}=l$ をみたすので、$5$ ターン目以降は $\mathrm{{T}}$ に向かってまっすぐ進み続けることで、$4+m\leq1003$ ターン目に宝を見つける。
以上より、すべての $0<l\leq1000$ に対して $1003$ ターン目までに宝を見つける移動経路が存在するため、主張が示された。(証明終)
命題2: アリスがうまく行動したとしても、運が悪ければ $1002$ ターン目までに宝を見つけることができないような $\mathrm{T}$ の位置が存在する。
証明: $0<\delta\leq 1 $ を定数とする。宝の位置を $\mathrm{T_1}=(-1000+\delta, \sqrt{\delta(2000-\delta)})$ とする。また、偽物の宝が点 $\mathrm{T_2}=(-1000+\delta, -\sqrt{\delta(2000-\delta)})$ にあるとする。まず $1$ ターン目では、アリスは $T$ の位置に関する情報を持たないので、どちらの方向に進む可能性もある。よって運が悪ければ $\mathrm{A_1}=(1,0)$ に進む可能性がある。移動後にアリスが距離を測ると、$d_1=\sqrt{998001+2\delta}$ となり、アリスにとって $\mathrm{T}$ の候補は中心 $(1,0)$, 半径$d_1$ の円弧 $\mathrm{T_1T_2}$ の上になる。この円弧は $x$ 軸に関して対称である。
アリスが次に移動する点を $\mathrm{A_2}=(x,y)$ とおく。
・$y \neq 0$ のとき
$\mathrm{T}$ の候補となる円弧が $x$ 軸に関して対称であるので、アリスは$\mathrm{T}$ の $y$ 座標の符号に関する情報を持たない。よって、運が悪ければ $y<0$ となる可能性がある。$\mathrm{A_1}=(1,0)$ を中心とする半径 $1$ の円の $y<0$ の部分と $\mathrm{T_1}$ との距離を考えると、$\mathrm{A_2T_1}$ が $\mathrm{OT_1}=1000$ 以下となることはない。つまり $\mathrm{A_2T_1}>1000$ であるため、残り $1000$ ターンで宝を見つけることはできない。
・$y=0$ のとき
このとき、アリスにとっての $\mathrm{T}$ の候補は $\mathrm{T_1, T_2}$ の $2$ つである。
まず、$x=2$ のときは $d_2^2=4(1001-\delta)+1000^2>1000^2$ なので、明らかに残り $1000$ ターンで宝にたどり着くことはできない。
次に $x=0$ のときは $d_2=1000$ であり、アリスにとっての $\mathrm{T}$ の候補は $\mathrm{T_1, T_2}$ の $2$ つに絞られる。$1002$ ターン目までに宝を見つけるためにはあと $1000$ 回の移動で $\mathrm{T}$ にたどり着く必要があるため、アリスは $\mathrm{T_1, T_2}$ のいずれかを決め打ちしてまっすぐ進むしかない。よって運が悪ければ、アリスは偽物の宝がある $\mathrm{T_2}$ に向かって進むので、$1002$ ターン目で宝を見つけることはない。
以上より、はじめの $2$ ターンでアリスがどのような戦略をとったとしても、運が悪ければ残り $1000$ ターンで宝にたどり着けない場合があることが示された。(証明終)
おすすめ問題
この問題を解いた人はこんな問題も解いています
