あなたたちは、とても大切な荷物を車で砂漠の向こうの町に運ばなければなりません。あなたたちは全員車を持っていますが、砂漠はとても広大で、砂漠の手前の町でガソリンを満タンに入れても、どの車も目的地までのちょうど半分の地点でガス欠になってしまいます。もちろん、砂漠の中にガソリンスタンドはありません。その上ワイヤーやロープの類もないため、けん引して運ぶということもできません。

しかし、運のよいことにあなたたちはポンプを手に入れることができたので、車のガソリンタンクに入っているガソリンを他の車のタンクに移すことができるようになりました。

何台かの車とポンプだけを使って砂漠の向こうの町に荷物を運ぶには、どうしたらよいでしょうか？

なお、車は1台でも目的地にたどり着けばよいものとします。

……さて、実はこの問題、使用する車の台数が最少の場合「何台かを砂漠の途中に乗り捨てて最短手順で行く方法」と「手順は多いけど全ての車が目的地もしくは砂漠の手前の町にたどり着ける方法」の2種類の解法があります。片方の答えが分かった方は、ぜひもう片方にチャレンジしてみてください！

以下はヒントです（反転して読んでください）

ヒント①：ガソリン満タンでも半分しか進めないということは、当然ながら荷物を運ぶ1台は、中間地点で満タンになるように他の車から補給を受けないといけません。

ヒント②：最短手順で行く場合、車は一度も砂漠の手前の町に引き返しません。逆に1台も乗り捨てない場合、何度か補給に戻ることになります。

ヒント③：ずばり、使用する車の台数は4台です。

それでは、正解発表です！

ヒントにも書いた通り、使用する車の台数は4台です。仮に荷物を運ぶ1台をX、それ以外の3台をA,B,Cと名付けることにします。また、説明がしやすいように、砂漠の手前の町から砂漠の向こうの町までの距離を600km（＝車はガソリン満タンで300km走れる）とします。

解法1⃣（最短手順）

①　ガソリン満タンのX,A,B,Cが同時に出発する

②　ガソリンが半分になる150km地点でB,Cの残りのガソリンをX,Aに移す

③　さらに150km進んだ300km地点でX,Aのガソリンが半分になるので、AのガソリンをXに移す

④　満タンになったXが残り300kmを走る

解法2⃣（1台も乗り捨てない）※ここでは更に説明を分かりやすくするため、ガソリン満タン＝30L（10Lで100km進める）として解説します

①　ガソリン満タンのX,A,B,Cが同時に出発する

②　Xはガソリンが切れる300km地点まで行き、Aは200km地点（ガソリン残り10L）、BとCは100km地点（ガソリン残り20L）で止まる

③　Cは10LのガソリンをBに移し、砂漠の手前の町に引き返してガソリンを補給し、再び100km地点に戻る（ガソリン残り20L）

④　満タンになったBはガソリン10Lを消費して200km地点まで進み、10LをAに移し、残り10Lで再び100km地点に戻ってCと合流する

⑤　CはBに10L移す→町に引き返して30L補給する→100km地点に戻ってBに10L移すという行動を繰り返して、Bのタンクを満タンにする

⑥　Bは200km地点まで進み、Aに10L移して再び100km地点に引き返してCと合流する

⑦　満タンになったAは300km地点まで進み、Xに10L移してから200km地点に引き返す

⑧　③～⑦の手順を、Xが満タンになるまで繰り返す

⑨　満タンになったXが残り300kmを走る

⑩　Aが200km地点に戻ったところで③～⑥の手順を行い、A,B,Cがそれぞれ砂漠手前の町に帰還する

いかがでしたか？　両方の正解にたどり着けたあなたは、相当のやわらか頭ですね！

それではまた次回！

Tweet