吊り橋を最も早く渡るには
問題
暗闇の中、吊り橋を渡ります。吊り橋は古く、同時に2人までしか渡れません。また、懐中電灯がなければ渡れませんが、懐中電灯は1つしかありません。Aさん、Bさん、Cさん、Dさんが吊り橋を渡るのに、それぞれ2分、4分、8分、10分かかるとすると、全員が渡り切るのに最短何分かかりますか。
答え
24分
過去にGoogleの入社試験でも出されたとも聞く有名な問題です。
よくありがちな答えが26分です。私も、「こんな問題を出してくるということは、一筋縄ではないな」と構えていなければ間違っていました。
以下が、具体的な渡り方です。
1. Aさん、Bさんが渡る（4分）
2. Aさんが戻る（2分）
3. Cさん、Dさんが渡る（10分）
4. Bさんが戻る（4分）
5. Aさん、Bさんが渡る（4分）
あ～すごいね。で終わるとよくないです。
算数・数学的に考えてみましょう。
4人が吊り橋を渡るのにかかる時間をそれぞれa,b,c,d（a<b<c<d）分とします。
渡り方は多くありますが、検討すべき吊り橋の渡り方は次の2パターンです。
①一番渡るのが早い人が往復を繰り返す
1. Aさん、Bさんが渡る（b分）
2. Aさんが戻る（a分）
3. Aさん、Cさんが渡る（C分）
4. Aさんが戻る（a分）
5. Aさん、dさんが渡る（d分）
②遅い2人を同時に渡らせる
1. Aさん、Bさんが渡る（b分）
2. Aさんが戻る（a分）
3. Cさん、Dさんが渡る（d分）
4. Bさんが戻る（b分）
5. Aさん、Bさんが渡る（b分）
①のパターンの時にかかる時間は、
2a+b+c+d分
②のパターンの時にかかる時間は、
a+3b+d分
です。
よって、①－②は
(2a+b+c+d)-(a+3b+d)
=a+c-2b
これが0より大きいか小さいか、すなわち
a+c>2bのときに②のパターンが最速
a+c<2bのときに①のパターンが最速
となります。
今回は10>8となりますので、②のパターンが最速です。
逆に言うと、もしbさんが今回のように4分でなく、例えば6分だったら、①のパターンが最速だったということですね。
こういう類の問題をただ知っていたというだけで、「あ、Google問題だし、これは②のパターンだよな」と完全に舐めてかかっている人は失敗するということです。①のパターンが最速のケースもあります。面白いですね。
コメントをお書きください