主題
Search

吉普車問題


最大化吉普車使用給定數量的燃料可以深入沙漠的距離。吉普車可以向前行駛,卸下一些燃料,然後使用油箱中剩餘的燃料返回基地。在基地,它可以重新加油並再次出發。當它到達之前儲存的燃料時,它可以使用這些燃料部分加滿油箱。這個問題也被稱為探索問題(Ball and Coxeter 1987)。

給定 n+f (其中 0<=f<1)桶燃料在沙漠邊緣,以及一輛能夠裝載一桶燃料的吉普車(並且可以沿途在容器中儲存燃料),可以行駛的最大單程距離(假設吉普車每消耗一桶燃料行駛一個單位距離)是

d=f/(2n+1)+sum_(i=1)^(n)1/(2i-1)
(1)
=f/(2n+1)+1/2[gamma+2ln2+psi_0(1/2+n)],
(2)

其中 gamma尤拉-馬歇羅尼常數,而 psi_n(z)多伽瑪函式

例如,只有 n=1 桶燃料的吉普車可以行駛的最遠距離顯然是 1 單位。然而,對於 n=2 桶燃料,透過將第一個油桶加滿吉普車油箱,行駛 1/3 單位距離,在那裡儲存 1/3 桶燃料,然後用剩餘 1/3 油箱的燃料返回基地來實現最大距離。在基地,油箱用第二個油桶加滿。然後吉普車行駛 1/3 單位距離(消耗 1/3 桶燃料),使用儲存在那裡的 1/3 桶燃料重新加滿油箱,並以滿油箱繼續行駛額外的 1 單位距離,總距離為 4/3。對於 n=1, 2, ... 桶燃料的解是 1, 4/3, 23/15, 176/105, 563/315, ...,也可以寫成 a(n)/b(n),其中

a(n)=(1/1+1/3+...+1/(2n-1))LCM(1,3,5,...,2n-1)
(3)
b(n)=LCM(1,3,5,...,2n-1)
(4)

(OEIS A025550A025547)。


另請參閱

調和數

使用 探索

參考文獻

Alway, G. C. “穿越沙漠。”Math. Gaz. 41, 209, 1957年。Ball, W. W. R. 和 Coxeter, H. S. M. 數學娛樂與散文,第 13 版。 紐約:Dover,第 32 頁,1987年。Bellman, R. 習題 54-55 動態規劃。 普林斯頓,新澤西州:普林斯頓大學出版社,第 103 頁,1955年。Fine, N. J. “吉普車問題。”Amer. Math. Monthly 54, 24-31, 1947年。Gale, D. “再次吉普車問題或一打吉普車。”Amer. Math. Monthly 77, 493-501, 1970年。Gardner, M. 《科學美國人數學謎題與消遣第二集:新選集》。 紐約:Simon and Schuster,第 152 頁和 157-159 頁,1961年。Haurath, A.; Jackson, B.; Mitchem, J.; 和 Schmeichel, E. “Gale 的往返吉普車問題。”Amer. Math. Monthly 102, 299-309, 1995年。Havil, J. “穿越沙漠。”《伽瑪:探索尤拉常數》第 13.6 節。普林斯頓,新澤西州:普林斯頓大學出版社,第 127 頁,2003年。Helmer, O. “後勤學問題:吉普車問題。”蘭德專案報告編號 Ra 15015,1947年12月。Phipps, C. G. “吉普車問題,更通用的解決方案。”Amer. Math. Monthly 54, 458-462, 1947年。Sloane, N. J. A. “整數數列線上百科全書”中的數列 A025550A025547

在 中被引用

吉普車問題

請引用為

Weisstein, Eric W. “吉普車問題。” 來自 Web 資源。 https://mathworld.tw/JeepProblem.html

學科分類