最大化吉普车使用给定数量的燃料可以深入沙漠的距离。吉普车可以向前行驶,卸下一些燃料,然后使用油箱中剩余的燃料返回基地。在基地,它可以重新加油并再次出发。当它到达之前储存的燃料时,它可以使用这些燃料部分加满油箱。这个问题也被称为探索问题(Ball and Coxeter 1987)。
给定 (其中
)桶燃料在沙漠边缘,以及一辆能够装载一桶燃料的吉普车(并且可以沿途在容器中储存燃料),可以行驶的最大单程距离(假设吉普车每消耗一桶燃料行驶一个单位距离)是
(1)
| |||
(2)
|
例如,只有 桶燃料的吉普车可以行驶的最远距离显然是 1 单位。然而,对于
桶燃料,通过将第一个油桶加满吉普车油箱,行驶 1/3 单位距离,在那里储存 1/3 桶燃料,然后用剩余 1/3 油箱的燃料返回基地来实现最大距离。在基地,油箱用第二个油桶加满。然后吉普车行驶 1/3 单位距离(消耗 1/3 桶燃料),使用储存在那里的 1/3 桶燃料重新加满油箱,并以满油箱继续行驶额外的 1 单位距离,总距离为 4/3。对于
, 2, ... 桶燃料的解是 1, 4/3, 23/15, 176/105, 563/315, ...,也可以写成
,其中
(3)
| |||
(4)
|