[问题解答]运煤车的最大路程(更正)
By 苏剑林 | 2014-05-04 | 40527位读者 |刚刚在浏览卢昌海大师的微博时,发现他微博上有一道比较有趣的题目,于是饶有兴致地思考了一翻,构思了一个答案,希望读者们看看这个答案有问题不?
五一”长假微博很闷,出一道题给博友们解闷:
用重载列车运煤,每次可装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》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (May. 04, 2014). 《[问题解答]运煤车的最大路程(更正) 》[Blog post]. Retrieved from https://kexue.fm/archives/2587
@online{kexuefm-2587,
title={[问题解答]运煤车的最大路程(更正)},
author={苏剑林},
year={2014},
month={May},
url={\url{https://kexue.fm/archives/2587}},
}
May 5th, 2014
又想了一下,不在围脖说了,如果原题规定了除了最开始的起点以外的任意一点储存的煤都不能超过1万吨,那么就应该是你这个,如果没说,你这个不对,`(*∩_∩*)′
如果可以超过一万吨,还可以有另外的答案吗?请试举一例?^_^
已经在上面更正最新答案。欢迎常来~^_^
May 5th, 2014
latex 语句好漂亮,请教用的哪个插件?
直接加载mathjax。
May 7th, 2014
我觉得博主虽然讨论的是N是整数的情形,但是推导中用到了“共来回运输?N??1次”这种写法是为了在后面迭代的过程中避免讨论Ni非整数的情形,这样的话一开始就可以把N当成非整数来讨论。
但是把N当做非整数来讨论又会有另一个问题,假设y=0.2,而N=10.1,那么实际上正确的搬运方式是运完前面的10,最后的0.1留在原地不理?
所以N非整数时,$N_{i-1},y_{i-1},N_i$的关系应该是个分段函数。。
不过根据分段推出来的结果,发现好像这样考虑在后面求导的时候结果没变。。
我在推导过程中其实也想到了您说的问题,但是并没有提及,“故意”掩盖了它。因为后来想到主要的核心是利用$y\to 0$,因此这个问题也就没有了。一旦把$y_i$有限的时候的情况细化的话,那将复杂度又会提高,对于理解本文的主干思想无益。(就算N是正整数也不简单,因为从第二次开始,$N_i$就未必是正整数了,所以N是正整数的假设并没有带来太大的方便。)而像您这样的“有心人”,则自然会注意到这个问题的。^_^