主题
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.net.cn/JeepProblem.html

学科分类