While browsing Master Lu Changhai’s Weibo just now, I found an interesting problem. I spent some time thinking about it and formulated an answer. I hope readers can review it and see if there are any issues.
The May Day holiday Weibo is quite dull, so here is a problem for my fellow netizens to pass the time:
A heavy-haul train is used to transport coal. Each trip it can carry 10,000 tons, and it consumes 1 ton of coal per kilometer traveled. There are N million tons of coal at the starting point (for simplicity, assume N is a positive integer). What is the maximum distance the coal can be transported? (Assume a state-owned coal boss where cost is not an issue; as long as the quantity delivered is greater than 0, it is considered successful). Also, find the asymptotic form as N \to \infty.
Analysis:
Simply put, this problem asks how far the train can travel at most. The key is to consume all the coal as efficiently as possible. To achieve this, multiple round trips are necessary, and the train’s carrying capacity should be utilized to its maximum. Another requirement is not to consume too much coal on the same stretch of road. (i.e., the number of round trips should be as few as possible; the error in the previous incorrect solution below was consuming too much coal in the early stages.)
Thanks to the inspiration from netizen Wu Ling, the optimal approach should be “incremental advancement.” That is, first concentrate the coal at a point ahead (with consumption during transport), and then start from that point to transport the coal to a point even further ahead. By repeating this process, we obtain the maximum distance. Below is an analysis of this process.
The problem assumes N is a positive integer, but the same analysis applies even if N is not an integer. (In fact, assuming N is an integer does not provide much extra convenience.) We use the “ceiling function” \lceil x \rceil, defined as the smallest integer not less than x.
Starting from the origin, each trip carries 1 unit (10,000 tons) to a point y units (10,000 km) ahead. A total of \lceil N \rceil - 1 round trips are made. After unloading a portion of the coal each time, the train returns to the origin just as it exhausts its fuel. The final trip does not require a return. Thus, after this operation, the train is at a distance y from the origin, and the remaining coal there is: (\lceil N \rceil-1)(1-2y) + N + 1 - \lceil N \rceil - y = N + y - 2y\lceil N \rceil This process is repeated for each segment. Let N_i represent the remaining coal after each step, and y_i represent the distance advanced in each step. Thus: N_i = N_{i-1} + y_{i-1} - 2y_{i-1}\lceil N_{i-1} \rceil; \quad i=1,2,\dots,N; \quad N_0=N This is a recurrence problem involving a ceiling function and adjustable parameters y_i. A brief analysis reveals that in each segment, the closer the segment is to the origin, the higher the average coal consumption. Therefore, each y_i should be as small as possible. Consequently, the optimal case is when all y_i \to 0.
This is a process of: transporting coal, traveling a tiny distance, unloading, returning, and repeating. Strictly speaking, this operation is impossible to implement in reality. However, this does not prevent us from understanding it mathematically. On the other hand, continuous results can serve as an approximation for discrete ones. Then: \frac{N_i - N_{i-1}}{y_{i-1}} = 1 - 2\lceil N_{i-1} \rceil As y_{i-1} \to 0, let N_i = N(s), where s is the distance from the starting point. From the definition of the derivative, we have: \frac{dN(s)}{ds} = 1 - 2\lceil N(s) \rceil This is a differential equation with a ceiling function. Although the ceiling function prevents us from directly applying general solution formulas from textbooks, in a sense, this equation is simpler. After piecewise decomposition, it becomes the simplest form of \frac{dy}{dx} = \text{Constant}.
The above derivation does not rely on N being an integer. However, it appears that N being an integer yields a formally simpler solution. When N(s) \in (N-1, N], we have: \frac{dN(s)}{ds} = 1 - 2N The solution is: N(s) = (1 - 2N)s + N This solution is valid for the interval N(s) \in (N-1, N], which covers exactly one unit of coal. Thus, in the first step, the train travels a distance of \frac{1}{2N-1}.
In the second step, when N(s) \in (N-2, N-1], we have: \frac{dN(s)}{ds} = 1 - 2(N-1) The solution is (resetting the origin at each step): N(s) = (3 - 2N)s + N - 1 This solution is valid for N(s) \in (N-2, N-1], so in the second step, the train travels \frac{1}{2N-3}. We find that this process can be iterated, and the final result is: S = 1 + \frac{1}{3} + \dots + \frac{1}{2N-1} This can be estimated as: \frac{1}{2}\ln(2N-1) < S < \frac{1}{2} \ln(2N-3) + 1
When N is not an integer, let \tilde{N} = \lceil N \rceil - 1, then: S = \frac{N-\tilde{N}}{2\tilde{N}+1} + 1 + \frac{1}{3} + \dots + \frac{1}{2\tilde{N}-1}
I look forward to further corrections from readers.
The following is the author’s incorrect solution from yesterday (May 4, 2014):
===========================================
Simply put, this problem asks how far the train can travel at most. The key is to consume all the coal. To achieve this, multiple round trips are needed, maximizing the train’s capacity. Under the assumption that N is an integer, an ideal situation is to make N trips. Each trip starts with 10,000 tons, unloads a portion midway, and returns. Upon returning to the start, the coal on the train is exactly exhausted. This repeats for subsequent trips. On the final trip, since there is no need to return, the train consumes coal as it goes. When it encounters the first pile of coal unloaded previously, it reloads to full capacity; when it hits the next pile, it reloads again... this way, all coal is consumed. Let’s analyze this case.
Suppose there are N trips (each departure from the start is one trip), each carrying 1 unit. Let a_i be the distance (in 10,000 km), which is also the coal consumption a_i (in 10,000 tons), for i=1, 2, \dots, N-1. The amount of coal unloaded midway during each trip is 1-2a_i. Considering the final trip, according to the assumption above, when it meets the previously unloaded coal, it reloads to exactly 1 unit. Thus: (1-2a_i) + [1-(a_i-a_{i-1})] = 1, \quad i=1,2,\dots,N-1, \quad a_0=0 Which simplifies to: 1 + a_{i-1} = 3a_i Solving this recurrence gives: a_i = \frac{1}{2}\left(1 - \frac{1}{3^i}\right) Thus, the distance traveled on the final trip is: s = a_{N-1} + 1 = \frac{1}{2}\left(1 - \frac{1}{3^{N-1}}\right) + 1 Its asymptotic form (N \to \infty) is: s = \frac{3}{2}
This was a solution developed behind closed doors; I welcome corrections from readers. ^_^
When reposting, please include the original address of this article: https://kexue.fm/archives/2587
For more details on reposting, please refer to: Scientific Space FAQ