[问题解答]运煤车的最大路程（更正）

刚刚在浏览卢昌海大师的微博时，发现他微博上有一道比较有趣的题目，于是饶有兴致地思考了一翻，构思了一个答案，希望读者们看看这个答案有问题不？

五一”长假微博很闷，出一道题给博友们解闷：

用重载列车运煤，每次可装1万吨，每行驶1公里耗煤1吨，起点处共有N万吨煤（简单起见N为正整数），请问最远可运至何处（是国营煤老板，成本不计，只要运到的数量大于0就算成功）？并求$N\to\infty$时的渐进形式。

分析：
说白了，这个问题就是问火车最远可以走多远，问题的关键是要尽可能地消耗完所有的煤。为了达成这个目的，需要来回多趟，并且尽可能用满列车的运载量。还有一个要求，就是不要在同一段路上消耗太多的煤。（即来回的次数尽可能少，下面的错误解法的错误就在于在前面的路消耗了太多的煤。）

得益于伍岭博友的启示，最优的做法应该是“逐步推进”，也就是说先把煤集中运到前方的一个点上（运输过程中会有消耗），然后再从前方的那个点出发，把煤运输到更前方的一个点上，如此重复下去，就得到最远的距离。下面对这个过程进行分析。

题目假设了$N$是正整数，当然，就算$N$不是整数也可以进行同样的分析。（事实上，假设$N$是整数并没有带来太大的方便。）我们这里用到“上取整函数”$\lceil x \rceil$，定义为不小于$x$的最小整数。

从原点出发，每次运输1万吨，运输到前方$y$万公里处，共来回运输$\lceil N \rceil-1$次，每次卸下一部分煤后，回到原点刚好消耗完。最后一次不用返回去，所以经过这样一折腾，火车在距离原点$y$处，并且那里剩下的煤量为
$$(\lceil N \rceil-1)(1-2y)+N+1-\lceil N \rceil-y=N+y-2y\lceil N \rceil$$
每一段路都是重复这个过程，用$N_i$表示每次剩下的煤量，用$y_i$表示每次前进的路程，于是
$$N_i=N_{i-1}+y_{i-1}-2y_{i-1}\lceil N_{i-1} \rceil;\ i=1,2,\dots,N;\ N_0=N$$
这是一个带有取整函数的递推问题，同时带有可调参数$y_i$。稍微经过分析就可以发现，每一段路中，都是越靠近原点的那一段路，平均耗煤量越大。因此，每个$y_i$都是越小越好，因此，最优的情况是所有的$y_i$都有$y_i\to 0$。

这是这样的一个过程：运煤，然后走一丁点的距离，卸煤，回去，然后运煤，走一丁点的距离，卸煤，回去。严格意义上来说，这种运作是无法实现的。但是，这不妨碍我们在数学上理解它。另一方面，连续的结果也可以作为离散的一个近似。那么
$$\frac{N_i-N_{i-1}}{y_{i-1}}=1-2\lceil N_{i-1} \rceil$$
当$y_{i-1}\to 0$时，记$N_i=N(s)$，$s$是到起点的距离，由导数的定义得
$$\frac{dN(s)}{ds}=1-2\lceil N(s) \rceil$$
这是一道带有取整函数的微分方程。虽然取整函数使得我们不能直接应用我们教科书上的通解公式，但是某种意义上来说，这种方程更加简单。因为经过分段之后，它就是一道$\frac{dy}{dx}=Constant$的最简单的方程了。

以上的推导并没有基于$N$是整数。当然，现在看来，$N$是整数能够给出形式上比较简单的解。在$N(s)\in (N-1,N]$时，有
$$\frac{dN(s)}{ds}=1-2N$$
它的解是
$$N(s)=(1-2N)s+N$$
这个解的生效区间是$N(s)\in (N-1,N]$，即只维持一个单位，所以在第一步，火车走了$\frac{1}{2N-1}$。
第二步，在$N(s)\in (N-2,N-1]$时，有
$$\frac{dN(s)}{ds}=1-2(N-1)$$
它的解是（每一步都重新选择原点）
$$N(s)=(3-2N)s+N-1$$
这个解的生效区间是$N(s)\in (N-2,N-1]$，所以在第二步，火车走了$\frac{1}{2N-3}$。我们发现，这个过程是可以递推的，最终的结果是
$$S=1+\frac{1}{3}+\dots+\frac{1}{2N-1}$$
可以估算
$$\frac{1}{2}\ln(2N-1) < S < \frac{1}{2} \ln(2N-3)+1$$

当$N$不是整数时，记忆$\tilde{N}=\lceil N \rceil -1$，则
$$S=\frac{N-\tilde{N}}{2\tilde{N}+1}+1+\frac{1}{3}+\dots+\frac{1}{2\tilde{N}-1}$$

望各位读者继续指正。

以下是站长昨天（2014年5月4日）的错误解答：
===========================================
说白了，这个问题就是问火车最远可以走多远，问题的关键是要尽可能地消耗完所有的煤。为了达成这个目的，需要来回多趟，并且尽可能用满列车的运载量。在N是整数的假设下，比较理想的情况是走N趟，每趟的出发都运1万吨，然后中途放下一部分，再回去，回去到起点时，列车上的煤刚好用完，再运一万吨，以此类推。在最后一趟时，由于不用再回去了，所以尽可能地消耗所有的煤，再遇到第一堆之前卸下的煤时，装上去，刚好装满；遇到下一堆煤时，装上去，刚好装满...这样子就完全消耗了所有的煤。下面分析这种情况。

设走$N$趟（从起点出发一次叫一趟），每趟装1万吨，走$a_i$路程（万公里），路程也就是耗煤量$a_i$（万吨），$i=1,2,\dots,N-1$，每趟在途中卸下的煤量为$1-2a_i$。考虑最后一趟，根据上面的假设，它跟之前卸下的煤相遇时，把煤装上，刚好装满，于是有
$$(1-2a_i)+[1-(a_i-a_{i-1})]=1,i=1,2,\dots,N-1,a_0=0$$
也就是
$$1+a_{i-1}=3a_i$$
解这个递推得
$$a_i=\frac{1}{2}\left(1-\frac{1}{3^i}\right)$$
于是最后一趟走的路程为
$$s=a_{N-1}+1=\frac{1}{2}\left(1-\frac{1}{3^{N-1}}\right)+1$$
其渐进形式（$N\to\infty$）为
$$s=\frac{3}{2}$$

闭门造车之解答，望各位读者指正。^_^

转载到请包括本文地址：https://kexue.fm/archives/2587

更详细的转载事宜请参考：《科学空间FAQ》