飛機環球問題 怎樣加油可環球一圈？

一種型號飛機加滿油可以繞地球飛半圈，要讓一架飛機繞地球赤道飛一圈，至少需要幾架飛機？至少要起飛幾次？假設所有飛機都在一個機場起落，飛機可以在空中互相加油，加油時間不計。

1. ABC 滿油同時起飛。
2. ABC 飛全程 1/8 時各自消耗 1/4 的油，C 給 AB 各 1/4，自己剩 1/4 返航；AB 滿油。
3. AB 飛全程 1/4 時各自消耗 1/4 的油，B 給 A 1/4，自己剩 1/2 返航；A 滿油。
4. A 飛全程 1/2 時 B 滿油從起點沿反方向出發。
5. A 飛全程 3/4 時耗盡所有油，與 B 相遇，B 還有 1/2 的油，給 A 1/4，自己剩 1/4，與 A 一同返航。C 滿油從起點反方向出發。
6. AB 飛全程 7/8 時耗盡所有油，與 C 相遇，C 還有 3/4 的油，給 AB 各 1/4，自己剩 1/4，與 AB 一同返航。

慢慢寫點推廣好了。假設一架飛機滿油可以飛全程的 x，滿足 0 &< x &< 1。顯然兩邊取等意義不大。

比較簡單的情況是 x = 2/3，此時只要兩架：A 飛到全程 1/3 時 B 反方向滿油出發即可。但從 2/3 到 1/2 突然複雜得多，這個數學模型搞不好會比較複雜。

即使 x 非常小，我們也可以靠數量來刷距離。一架飛機最遠可以飛到 x/2 並返航，如果有兩架飛機的話，就可以飛到途中 B 把油轉給 A 並返航，A 返航時 B 加滿了油去接它。如果靠多架飛機可以飛到並返航的最遠距離超過 1/2，那麼這時同樣的方案便可以保證至少有一架飛機環球一圈。

考慮兩架飛機 AB 的情形。AB 同時出發，飛到途中某一點時 B 把油給 A 然後返航，A 繼續向前飛，油量減半即返航，B 算好時間出去接它。令從起點到加油點的距離爲 m，那麼這段距離消耗的燃料爲 m/x。這個過程中要滿足：

1. B 給 A 加油後油量不能低於返航需要的油。換言之加油後 B 剩下的油不能少於 m/x。
2. A 的油量不能超過滿載油量。否則 B 相當於多帶了油。雖然現實中飛機會有最大起飛重量的限制，但爲了簡化模型我們不考慮。

這應該是一個比較出名的面試難題，原問題的解答 @yukirock 已經給出。

我幾個月前寫了一篇關於推廣問題的討論：一道飛機環球飛行面試題的後續討論。文章中給出了一組基於遞歸的策略，使得在直線上某架飛機可以飛到離機場任意遠（圓上的策略可以基於直線上的策略構造）。文章中詳細計算了策略使用的油量（等價於起飛次數）。如果我們用飛機加滿一箱油能夠飛行的距離表示單位距離的話，那麼文章中用油量最少的遞歸策略，在直線上可以用大概 O(25^x) 箱油使得一架飛機飛到離機場x單位距離遠的地方；對於周長為x的圓，可以用大概 O(5^x) 箱油使得一架飛機繞飛一周。不過，這些遞歸策略使用的飛機數量比較難算，一個平凡的估計是飛機的數量不會超過用油的箱數。而觀察一些例子後可以猜測這些策略的飛機使用數量，其中2架飛機編組的策略估計使用8^x架飛機可以保證一架飛機飛到離機場x+1單位遠的地方，對於周長為x的圓估計需要 架飛機。

至於推廣問題的最優解（以及最優性證明），我覺得應該不會簡單。