ジープの問題

ジープ問題^[1] 、砂漠横断問題^[2]、または探検問題^[3]は、ジープが与えられた量の燃料で砂漠まで移動できる距離を最大化しなければならないという数学の問題です。ジープは固定された限られた量の燃料しか運ぶことができませんが、砂漠のどこにでも燃料置き場を置いて燃料を回収することができます。

この問題は、アルクインの作とされる9世紀の問題集「若者を研ぎ澄ます問題集」に初めて登場し、旅するラクダが穀物を食べるという内容だった。^[4]ルカ・パチョーリの 「De viribus quantitatis」（1500年頃）でもこの問題が取り上げられている。 1947年にNJファインが現代的な解釈を与えた。^[1]

固定された基地にn単位の燃料が保管されています。ジープは一度に最大 1 単位の燃料を運ぶことができ、1 単位の燃料で 1 単位の距離を移動できます (ジープの燃料消費量は一定であると想定されます)。ジープは、燃料積載量が 1 単位を超えない限り、移動中のどの時点でも、運んでいる燃料を任意の量だけ燃料ダンプに残したり、前回の旅行で燃料ダンプに残した燃料を任意の量だけ回収したりできます。この問題には 2 つのバリエーションがあります。

• 砂漠の探検 - ジープは毎回の旅の終わりに基地に戻らなければなりません。
• 砂漠を横断する – ジープは、燃料が尽きる前にできる限り遠くまで移動する最後の旅を除き、すべての旅の最後に基地に戻らなければなりません。

どちらの場合も、最終旅行でジープが移動する距離を最大化することが目的です。あるいは、最終旅行で特定の距離を移動するために必要な燃料の最小量を見つけることが目的になることもあります。

古典的な問題では、ジープ内の燃料と燃料ダンプの燃料は連続量として扱われます。この問題のより複雑なバリエーションとして、燃料を離散的な量だけ残したり収集したりできるものが提案されています。^[5]

「砂漠の探検」バリアントの最終旅行で移動距離を最大化する戦略は次のとおりです。

• ジープはn回走行します。各走行で、燃料 1 ユニットを搭載した状態でベースから出発します。
• 最初の旅では、ジープは 1/(2 n ) 単位の距離を移動し、燃料投棄所に( n  − 1)/ n単位の燃料を残します。ジープにはまだ 1/(2 n ) 単位の燃料が残っており、基地に戻るのにちょうど十分です。
• 後続のn − 1 回の飛行のそれぞれにおいて、 ジープは出発時にこの最初の燃料ダンプから1/(2 n ) 単位の燃料を収集し、燃料ダンプから 1 単位の燃料を積んで出発します。また、帰路でもこの最初の燃料ダンプから 1/(2 n ) 単位の燃料を収集します。これは基地に戻るのにちょうど十分な燃料です。
• 2 回目の移動では、ジープは最初の燃料集積所まで移動して燃料を補給します。その後、1/(2 n  − 2) 単位の距離を移動し、 2 番目の燃料集積所に( n  − 2)/( n − 1) 単位の燃料を残します。ジープにはまだ 1/(2 n  − 2) 単位の燃料があり、これは最初の燃料集積所に戻るのにちょうど十分な量です。ここでジープは 1/(2 n ) 単位の燃料を集めますが、これは基地に戻るのにちょうど十分な燃料です。
• 以降のn − 2 回の走行では、 ジープは 出発時にこの 2 番目の燃料ダンプから1/(2 n − 2) 単位の燃料を収集し、燃料ダンプから 1 単位の燃料を積んで出発します。また、帰り道でも 2 番目の燃料ダンプから 1/(2 n  − 2) 単位の燃料を収集します。これは、最初の燃料ダンプに戻るのにちょうど十分な量の燃料です。
• ジープはこのようにして走行を続け、k回目の走行では、 前の燃料ダンプから1/(2 n  − 2 k + 2) 単位の距離に新しいk番目の燃料ダンプを設置し、そこに ( n  −  k )/( n  −  k  + 1) 単位の燃料を残します。その後のn  −  k回目の走行では、往路でk番目のダンプから1/(2 n  − 2 k  + 2) 単位の燃料を収集し、 復路でさらに 1/(2 n  − 2 k + 2) 単位の燃料を収集します。

ジープが最後の旅を始めるとき、燃料置き場はn  − 1 か所あります。最も遠い場所には 1/2 単位の燃料が、その次に遠い場所には 1/3 単位の燃料が、というように続いていき、最も近い燃料置き場には 1/ n単位の燃料しか残っていません。基地から出発するときの 1 単位の燃料と合わせると、ジープは往復で次の距離を移動できます。

${\displaystyle 1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}=\sum _{k=1}^{n}{\frac {1}{k}}\equiv 2\times \mathrm {explore} (n)}$

最終行程では、半分のユニットを砂漠に進入します（砂漠への最大移動距離はこの半分です）。^[3]出発時に各ダンプで残りの燃料の半分を収集し、タンクを満タンにします。最も遠い燃料ダンプを離れた後、砂漠にさらに1/2ユニット移動し、最も遠い燃料ダンプに戻ります。各燃料ダンプから戻る途中で残りの燃料を収集しますが、これは次の燃料ダンプに到達するか、最終段階で基地に戻るのにちょうど十分な量です。

最後の移動で移動した距離はn番目の高調波数、H _nです。高調波数は無制限なので、基地に十分な燃料がある限り、最終移動で任意の距離を超えることが可能です。ただし、必要な燃料の量と燃料投棄の数は、移動距離とともに指数関数的に増加します。

「砂漠を横断する」変種も同様の戦略で解決できますが、最後の旅行で戻る途中で燃料を集める必要がなくなります。したがって、k回目の旅行では、ジープは前の燃料ダンプから 1/(2 n  − 2 k  + 1) 単位の距離に新しいk番目の燃料ダンプを設置し、 そこに(2 n  − 2 k  − 1)/(2 n  − 2 k + 1) 単位の燃料を残します。次のn  −  k  − 1 回の旅行では、往路でk番目のダンプから 1/(2 n  − 2 k  + 1) 単位の燃料を集め、復路でさらに 1/(2 n  − 2 k  + 1) 単位の燃料を集めます。

ジープが最後の旅を始めるとき、燃料ダンプはn  − 1 個あります。最も遠いダンプには 1/3 単位の燃料が、次に遠いダンプには 1/5 単位の燃料が、というように、最も近い燃料ダンプには 1/(2 n  − 1) 単位の燃料しか残っていません。基地から出発するときの 1 単位の燃料と合わせると、ジープは合計で次の距離を移動できることになります。

${\displaystyle 1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}=\sum _{k=1}^{n}{\frac {1}{2k-1}}=H_{2n-1}-{\frac {1}{2}}H_{n-1}\equiv \mathrm {cross} (n)}$

最後の旅では1ユニットを走行します。^{[1] [3]}出発時に各ダンプで残りの燃料をすべて収集し、タンクを満タンにします。最も遠い燃料ダンプを出発した後、さらに1ユニットの距離を走行します。

以来

${\displaystyle \mathrm {cross} (n)=\sum _{k=1}^{n}{\frac {1}{2k-1}}>\sum _{k=1}^{n}{\frac {1}{2k}}={\frac {1}{2}}H_{n}=\mathrm {explore} (n)}$、

理論上は、基地に十分な燃料があれば、どんな大きさの砂漠でも横断できます。以前と同様に、必要な燃料の量と燃料投棄場所の数は、移動距離に応じて指数関数的に増加します。

要約すると、ジープ（燃料容量が常に1単位の距離）がn回の走行（途中でn-1回の燃料補給があり、合計n単位の燃料を消費）で到達できる最大距離は 、

• ${\displaystyle \mathrm {explore} (n)={\frac {1}{2}}H_{n}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{6}}+\cdots +{\frac {1}{2n}}}$砂漠を探索するため、ジープは毎回の旅の終わりに基地に戻らなければなりません。
• ${\displaystyle \mathrm {cross} (n)=H_{2n-1}-{\frac {1}{2}}H_{n-1}=1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}}$砂漠を横断するジープは、最後の旅程を除いて毎回最後に基地に戻らなければなりません。最後の旅程では、ジープは燃料が尽きる前にできる限り遠くまで移動します。

ここでn 番目の高調波数です。 ${\displaystyle H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}}$

基地で利用できる燃料ユニットの数は整数である必要はありません。一般的なケースでは、nユニットの燃料で「砂漠を探索する」問題で達成可能な最大距離は、

${\displaystyle \mathrm {explore} (n)=\int _{0}^{n}{\frac {\mathrm {d} f}{2\lceil nf\rceil }}}$

最初の燃料ダンプは開始基地から単位距離離れた場所に配置され、2 番目の燃料ダンプは最初の燃料ダンプから単位距離離れた場所に配置され、3 番目の燃料ダンプは2 番目の燃料ダンプから単位距離離れた場所に配置され、というように続きます。ここではnの小数部分を示します。 ${\displaystyle \{n\}/(2\lceil n\rceil )}$${\displaystyle 1/(2\lceil n\rceil -2)}$${\displaystyle 1/(2\lceil n\rceil -4)}$${\displaystyle \{n\}=n-\lfloor n\rfloor }$

「砂漠を横断する」問題において、n単位の燃料で達成可能な最大距離は、

${\displaystyle \mathrm {cross} (n)=\int _{0}^{n}{\frac {\mathrm {d} f}{2\lceil nf\rceil -1}}}$

最初の燃料ダンプは開始基地から単位距離離れた場所に配置され、2 番目の燃料ダンプは最初の燃料ダンプから単位距離離れた場所に配置され、3 番目の燃料ダンプは2 番目の燃料ダンプから単位距離離れた場所に配置され、というように続きます。ここではnの小数部分を示します。 ${\displaystyle \{n\}/(2\lceil n\rceil -1)}$${\displaystyle 1/(2\lceil n\rceil -3)}$${\displaystyle 1/(2\lceil n\rceil -5)}$${\displaystyle \{n\}=n-\lfloor n\rfloor }$

ジープの走行順序は固定されていません。たとえば、問題の「砂漠の探検」バージョンでは、ジープは基地と最初の燃料貯蔵所の間をn − 1往復し、そのたびに( n − 1) / n単位の燃料を燃料貯蔵所に残し、次に最初の燃料貯蔵所へのn回目の片道走行を行い、合計で( n − 1) + 1/(2 n )単位の燃料を持って到着します。1 /(2 n )単位は最後に基地に戻るために取っておかれ、残りのn − 1単位の燃料は最初の燃料貯蔵所と 2 番目の燃料貯蔵所の間で燃料を移動するために使用され、n − 2回の往復を行った後、 2 番目の燃料貯蔵所への( n −1)回目の片道走行を行います。以下同様に続きます。

この問題は、特に燃料効率に関して、戦時状況に実際的な応用が可能である。第二次世界大戦中のB-29による日本爆撃の文脈で、ロバート・マクナマラは映画「フォッグ・オブ・ウォー」の中で、燃料を前線基地に輸送する必要があることによる燃料効率の問題を理解したことが、中国本土から爆撃を開始する戦略を放棄し、島嶼を飛び越える戦略を採用した主な理由であったと語っている。

「我々はカンザス州の基地からインドまで飛行機を飛ばさなければならなかった。そして、燃料を山を越えて中国まで運ばなければならなかった。[...] 我々はこれらのB-29 を飛ばすことになっていたが、そこにはタンカー機はなかった。我々は燃料を補給し、インドから成都まで飛んで燃料を降ろし、インドに戻り、成都で燃料を蓄えるのに十分な任務をこなし、日本の八幡まで飛んで製鉄所を爆撃し、インドに戻ることになっていた。我々はこの問題の [燃料] 効率を最大化する訓練をほとんど受けていなかったので、燃料を降ろす代わりに B-29 の一部を戻すことを実際に試みなければならなかった。長い話を短くすると、それはまったく価値がなかった。そして、実際にその結論に達したのはルメイであり、日本を壊滅させたマリアナ諸島への全機移動をチーフスに指示した。」^[6]

（第二次世界大戦末期の原爆投下作戦は、北マリアナ諸島の太平洋の島、テニアン島からB-29スーパーフォートレス戦闘機を使用して実施されました。）

• これらのアイデアの応用についてより深く理解するには、ブラックバック作戦をお読みください。フォークランド紛争中に行われたこれらの作戦では、イギリス空軍は、アセンション島に駐留するバルカン爆撃機がフォークランド諸島の標的を爆撃できるように、空中給油機による空中給油を実施しました。
• 調和級数（数学）
• 最適化（数学）