以下のようなメガネ型をした遊歩道がある。端から三叉路まで10分,三叉路から三叉路まで10分掛かる。Aさんは左端にいる。Bさんは遊歩道上のどこにいるか判らない。Bさんは歩き続け,端に来ると戻り,三叉路ではどちらかに進む。AさんがBさんを確実に探し出すにはどのように探せば良いか?
歩く速度はAさんもBさんも同じ速度とする。
難易度「やや難」であるが,私には難しい問題だった。プログラムを組んで解こうとしたのが最初の躓き。
さらに,Bさんは三叉路をどちらに進んでも良いということに気づいたのは翌日曜日朝風呂に入っている時。ずっと左右を単純に行き来するのかと思っていた。
新聞の問題文を読み直すために一旦風呂から出てしまった。
最初,以下のような単純な形で問題を考えた。右の突き出たところは1分と考えた。
この図でBさんがAさんの3分前を歩いていると一生出会えない。
ということは「途中で引き返さなければならない」と思った。
そこで以下のような経路を思いつく。
70分。これでOKと思った。しかしこれではダメ。次に考えたのが以下の図。
この時点まではBさんは端に向かってしか進めないと思っていた。
しかしBさんは三叉路でどちらに進んでも良いので,これではダメ。要するにすれ違った場合,放っておくとダメ。すれ違ったBさんを確実に捕らえなければならない。
途中ですれ違ったBさんを確実に捕らえるには,そこで待つことが大事。AさんがP地点に到達したとき,入れ違いに左に向かってBさんが進んだとすると,20分後か40分後には確実にP地点に帰ってくる。
よってAさんはA地点を出発しP地点に到達後は40分そこにとどまる。これで行き違いになったBさんと確実に会うことが出来る。
40分経過後は右へ進み,三叉路でBさんに出会うのを待つ。
単純だけどこれが一番かな。