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

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

用重载列车运煤,每次可装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}$$

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


转载到请包括本文地址:http://spaces.ac.cn/archives/2587/

如果您觉得本文还不错,欢迎点击下面的按钮对博主进行打赏。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!