沙漠穿越问题

hbghlyj

求吉普车在给定 $n$ 个单位燃料的情况下行驶到沙漠中的最大距离。吉普车载油量不超过 1个单位。用 1 个单位的燃料可以行驶 1 个单位的距离（假设吉普车的油耗是恒定的）。它可以在行程中任何地方堆放和收集燃料：可以堆放其携带的燃料的一部分，或者可以收集上一次行程中留下的任意量的燃油。
en.wikipedia.org/wiki/Jeep_problem
这个问题最早出现在 9 世纪 Alcuin 的 Propositiones ad Acuendos Juvenes（磨练年轻人的问题）中，其中的谜题是关于一只旅行的骆驼吃谷物。

hbghlyj

A strategy that maximizes the distance traveled on the final trip for the "exploring the desert" variant is as follows:

• The jeep makes $n$ trips. On each trip it starts from base with 1 unit of fuel.
• On the first trip the jeep travels a distance of $1\over2n$ units and leaves $n-1\over n$ units of fuel at a fuel dump. The jeep still has $1\over2n$ units of fuel – just enough to return to base.
• On each of the subsequent $n$-1 trips the jeep collects $1\over2n$ units of fuel from this first fuel dump on the way out, so that it leaves the fuel dump carrying 1 unit of fuel. It also collects $1\over2n$ units of fuel from this first fuel dump on the way back, which is just enough fuel to return to base.
• On the second trip the jeep travels to the first fuel dump and refuels. It then travels a distance of $1\over2n-2$ units and leaves $n-2\over n-1$ units of fuel at a second fuel dump. The jeep still has $1\over2n-2$ units of fuel, which is just enough to return to the first fuel dump. Here it collects $1\over2n$ units of fuel, which is just enough fuel to return to base.
• On each of the subsequent $n-2$ trips the jeep collects $1\over2n-2$ units of fuel from this second fuel dump on the way out, so that it leaves the fuel dump carrying 1 unit of fuel. It also collects $1\over2n-2$ units of fuel from the second fuel dump on the way back, which is just enough fuel to return to the first fuel dump.
• The jeep continues in this way, so that on trip $k$ it establishes a new $k$th fuel dump at a distance of $1\over2n-2k+2$ units from the previous fuel dump and leaves $n-k\over n-k+1$ units of fuel there. On each of the subsequent $n$-$k$ trips it collects $1\over2n-2k+2$ units of fuel from the $k$th dump on its way out and another $1\over2n-2k+2$ units of fuel on its way back.

When the jeep starts its final trip, there are $n-1$ fuel dumps. The farthest contains $1\over2$ of a unit of fuel, the next farthest contain $1\over3$ of a unit of fuel, and so on, and the nearest fuel dump has just $1\over n$ units of fuel left. Together with 1 unit of fuel with which it starts from base, this means that the jeep can travel a total round trip distance of
\[1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \sum_{k=1}^n \frac{1}{k} \equiv 2\times\mathrm{explore}(n)\]
units on its final trip (the maximum distance traveled into the desert is half of this).

abababa

hbghlyj 发表于 2022-12-3 09:01
A strategy that maximizes the distance traveled on the final trip for the "exploring the desert" var ...

试着翻译一下，不一定准确，大家看有什么问题指出一下，我再修改：

对于“探索沙漠”变体，最大化最后一次旅行的行程的策略如下：
这辆吉普车的行程是$n$。在每次行程中，从基地开始，携带$1$单位燃料。

在第一次行程中，吉普车行驶了$\frac{1}{2n}$单位的距离，并将$\frac{n-1}{n}$单位的燃料留在当地，成为$1$号燃料堆。吉普车仍有$\frac{1}{2n}$单位燃料，刚好可以回到基地。
在随后的每个$n-1$行程中，吉普车在离开途中从$1$号燃料堆中收集$\frac{1}{2n}$单位燃料，因此它离开燃料堆时已经携带$1$单位燃料。它还在返回途中从$1$号燃料堆中收集$\frac{1}{2n}$单位燃料，这刚好足够返回基地。
在第$2$次行程中，吉普车行驶到$1$号燃料堆并收集燃料。然后它行驶$\frac{1}{2n-2}$单位距离，并在$2$号燃料堆处留下$\frac{n-2}{n-1}$单位燃料。吉普车仍有$\frac{1}{2n-2}$单位的燃料，这刚好足够返回第$1$个燃料堆。在这里它收集$\frac{1}{2n}$单位燃料，这刚好足够返回基地。

在随后的每个$n-2$行程中，吉普车在离开途中从第$2$个燃料堆中收集$\frac{1}{2n-2}$单位燃料，从而在离开燃料堆时已经携带$1$单位燃料。它还在返回途中从第$2$个燃料堆中收集$\frac{1}{2n-2}$单位燃料，这刚好足够返回第一个燃料堆。

吉普车继续以这种方式行驶，因此在第$k$次行程中，它在距离前一个燃料堆$\frac{1}{2n-2k+2}$单位距离处建一个新的第$k$号燃料堆，并在那里留下$\frac{n-k}{n-k+1}$单位燃料。在随后的每个$n-k$行程中，它从$k$号燃料堆中收集$\frac{1}{2n-2k+2}$单位燃料，并在返回途中再收集$\frac{1}{2n-2k+2}$单位燃料。

当吉普车开始它的最后一次行程时，会有$n-1$单位燃料转储。最远的燃料堆有$\frac{1}{2}$单位燃料，次远的燃料堆有$\frac{1}{3}$单位燃料，依此类推，而最近的燃料堆有$\frac{1}{n}$单位燃料。加上从基地出发时所带的$1$单位燃料，这意味着吉普车可以行驶的总往返距离为
\[1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}\]


单位（进入沙漠的最大距离是这个距离的一半）。

但这个不能证明它是最大距离吧，只是给了一个方案。