情趣生活
情趣生活 => 灵机一动 => Topic started by: warren on 十一月 01, 2004, 06:14:21 pm

假设有一辆车，它的油箱恰好和一个油桶一样大，而且车上恰好可以运载一个
桶。假设一桶油可以让车开一千公里。现在在起点有10桶油。问，这车最远能
离开起点多远？ 如果有N桶油，汽车能跑多远？

It depends on whether the truck can carry an empty barrel in addition to a barrel of gas. This will determine whether it can store more than one barrel at any given place. If yes, the result is
(2 + 2/3 + 2/5 + 2/7 + 2/9) * 1000 = 3574 km
If no, the best I got so far is (3 + 5/12) * 1000 = 3416 km

It depends on whether the truck can carry an empty barrel in addition to a barrel of gas. This will determine whether it can store more than one barrel at any given place. If yes, the result is
(2 + 2/3 + 2/5 + 2/7 + 2/9) * 1000 = 3574 km
If no, the best I got so far is (3 + 5/12) * 1000 = 3416 km
If the truck can carry an empty barrel in addition to a barrel of gas,
this puzzle is not difficult, and I think your answer is right. I am interested
in the case when only one barrel can be carried. The difficulty is that
at most one barrel of gas can be stored at one place, this makes the
calculation complex.

I think it would be harder to obtain a tight upper bound than a tight lower bound for this kind of problem; if one can show his result is optimal, that would be really good. I am more interested in this, but do not know how.
There is a bicycle problem posted below. I think the problem has been considered solved, but there is no optimality proof either.
Has anyone tried this direction?

这个问题发了三天了，不知有几人在考虑。这里对比较小的 N 说说我的方法。
设起点有 N 桶油（N 不一定是整数）。
1） 0〈 N 〈= 2， 汽车在起点带上全部油出发，能行驶1000N公里。
2） 2〈 N 〈= 4，记 R=N2，第一次汽车带油R桶，行驶1000R/3公里到A点，存R/3桶油在A点，返回。 第二次汽车带油2桶，到A点加油R/3桶，能继续行驶2000公里。共行驶（2+（N2）/3）*1000公里。
3） 4〈 N 〈= 5+2/3，记 R=N4，第一次汽车带油R桶，行驶1000R/5公里到A点，存3R/5桶油在A点，返回。 第二次汽车带油2桶，到A点加油R/5桶，继续行驶2000/3公里到B点，存油2/3桶，返回A点，加油R/5桶，返回起点。第三次汽车带油2桶，到A点加油R/5桶，继续行驶2000/3公里到B点，加油2/3桶，继续行驶2000公里。共行驶（2+2/3+（N4）/5）*1000公里。当N=5+2/3时，行驶距离是 3000 公里。

I got some messy numbers and really do not want to put it up yet

There seem to be a sequence of optimal storage point on the route, and a corresponding sequence of maximal amount of gasoline you can have without using the next storage point, and a sequence of maximal distance you can travel with it. Let's call the sequeces X1, X2, X3, ..., Y1, Y2, Y3, ..., and Z1, Z2, Z3, .... Here is what I got so far:
X1 = 2 away from the final destination. (Lets omit all the 000.)
Y1 = 4 barrels
Z1 = 2 + 2/3
X2 = 2/3 from X1
Y2 = 5 + 2/3
Z2 = 3
X3 = 1/3 from X2
Y3 = 7 + 8/15
Z3 = 3 + 4/15
X4 = 4/15 from X3
Y4 = 9 + 1/3
Z4 = 3 + 7/15
X5 = 1/5 from X4
Y5 = 11 + 1/105
Z5 = 3 + 13/21
X6 = 16/105 from X5
Y6 = 12 + 91/105
Z6 = 3 + 16/21
The answer from my sequences to the original problem is between z4 and z5. (z4 + 2/33 = 3 +87/165 to be precise.)

Good job! I believe this is optimal. For N=10, the farest place the truck can reach is (3+29/55)*1000=3527km.

fzy的计算结果与我的计算结果一致,我认为这是最优解.关键是计算出数列 2,2/3,1/3,4/15,1/5,16/105,..., 它们分别是
终点,第一个存油点,第二个存油点,第三个存油点,...,起点之间的距离.从这些存油点出发到终点所需油量分别是 2,2+3*2/3,2+3*2/3+5*1/3,2+3*2/3+5*1/3+7*4/15,2+3*2/3+5*1/3+7*4/15+9*1/5,2+3*2/3+5*1/3+7*4/15+9*1/5+11*16/105,...,
计算出来就是2,4,5+2/3,7+8/15,9+1/3,11+1/105,.... 对于N=10,9+1/3<N<11+1/105,
离起点最近的存油点距离是(N(9+1/3))/11=2/33, 其他各存油点之间的距离分别是1/5,4/15,1/3,2/3. 有兴趣的网友可以考虑详细的过程.

Good job! I believe this is optimal. For N=10, the farest place the truck can reach is (3+29/55)*1000=3527km.
How do you show it is optimal?

Good job! I believe this is optimal. For N=10, the farest place the truck can reach is (3+29/55)*1000=3527km.
How do you show it is optimal?
只是"believe", 要严格证明很繁琐,我没时间去证.也许fzy有最优性证明.

The way I got my strategy is iterative and incremental. I believe it is locally optimal, which means small tweaks will not improve the result. But I cannot rule out that some dramatically different strategies may have better results, in particular for larger amount of fuel. This is my way:
1. We assume that a sequence of optimal storage points exist and their relative positions will not change. There is one criteria: When the truck leaves a storage point for the last time, it should have a full tank and a full barrel.
2. When a truck starts between Storage Point N (SP(N)) and SP(N+1), it will make N round trips back to the start point, first time to SP(N), then SP(N1), and so on. Each time one full barrel of fuel is stored, except at SP(1), where 1/3 barrel is stored.
3. For one round trip to an SP that is less than 1/2 unit (we assume one barrel of fuel can go 1 unit) away, we carry 1 + 2d barrels (d the distance). Other wise we carry 2 barrels.
4. If we start near SP(N) and (2N+1)d < 1 + 2d, we carry (2N+1)d and store (2N1)d for the first trip. And this is how I got the answer for the original problem.
5. The value of the distance between SP(N) and SP(N+1) is the largest number such that the above is possible. It turns out the only trip we need to worry about is the first one over 1/2.
As examples, I show here how I got SP(4) and SP(5). We already knew that SP(1) = 2, SP(2) = 2/3, and SP(3) = 1/3. (From now on we make no difference between an SP and its distance from the previous one.)
For SP(4) the first trip exceeding 1/2 is the second one. Let SP(4) = x. During this trip the fuel amounts added and dumped are (2  1 + (1  3x)). Here 1 dumped at SP(2) and (1  3x) added at SP(3) so that 3x left for the 3 future passes. The distance traveled is 2(SP(3) + x). Solve the equation and we get x = 4/15.
For SP(5) the first trip exceeding 1/2 is the third one. (If you solve for the second trip you will not get a solution.) Let SP(5) = x. The fuel amounts added and dumped are (2  1 + 1/5 + (1  3x)). Here 1/5 barrel is added at SP(3) from the previous calculation. The distance traveled is 2(SP(4) + SP(3) + x). Solve the equation and we get x = 1/5.
Another strategy that might look attractive for large amount of fuel is to go all out: Carry as much fuel as possible on each trip, use about half of it and store the other half at the 1/2 point. But since the SP sequece is decreasing and the fuel consumption graph is concave, we can see that the first strategy is always better than the second one.

I've been following the discussion of this problem. Don't like the stage by stage solution. I've been trying to develope a general solution, but failed. Now, I think the current stage by stage solution (by fzy and Warren) may be the best we can do. I have a minor problem with the stage though. It seems that no matter what, the first storage spot has to be at the half point (i.e. 500 km). At the begining, when you first drive out with 2 barrels (one in the tank of the car, one in the barrel), there's no other place to store the barrel other than the 500 km place (can't be longer or shorter). However, none of your solutions mention the 1/2 point storage place. May be I didn't read it careful enough. I think the best thing to do is to write out the exact procedure of doing the barrel problem.

I've been following the discussion of this problem. Don't like the stage by stage solution. I've been trying to develope a general solution, but failed. Now, I think the current stage by stage solution (by fzy and Warren) may be the best we can do. I have a minor problem with the stage though. It seems that no matter what, the first storage spot has to be at the half point (i.e. 500 km). At the begining, when you first drive out with 2 barrels (one in the tank of the car, one in the barrel), there's no other place to store the barrel other than the 500 km place (can't be longer or shorter). However, none of your solutions mention the 1/2 point storage place. May be I didn't read it careful enough. I think the best thing to do is to write out the exact procedure of doing the barrel problem.
The first storage point needs not be at 500km. For example, when N=5,
as shown in my previous poster(the 5th floor), the first storage point is
1000/5=200km away from the start point, and it is easy to show that this
plan is optimal.

Yes, I can see that, just like when you have 3 barrel, the first storage place is 1/3, this is because you want to reduce the round trips, thus, make the number of barrels to be even. When you have even number of barrels, anything shorter than 1/2 point will make more trips. You may be able to have shorter storage place later when you have an empty barrel, but the first time, you have to do a 1/2 point stop, I think.

I've been following the discussion of this problem. Don't like the stage by stage solution. I've been trying to develope a general solution, but failed. Now, I think the current stage by stage solution (by fzy and Warren) may be the best we can do. I have a minor problem with the stage though. It seems that no matter what, the first storage spot has to be at the half point (i.e. 500 km). At the begining, when you first drive out with 2 barrels (one in the tank of the car, one in the barrel), there's no other place to store the barrel other than the 500 km place (can't be longer or shorter). However, none of your solutions mention the 1/2 point storage place. May be I didn't read it careful enough. I think the best thing to do is to write out the exact procedure of doing the barrel problem.
I did not like the way either, and that is why I waited for so long in the hope of some one can provide a better answer first. But if our solution is indeed the best, the only way to reach it is iteration, because each number depends on the ones before it.
Also in my solution, the 1/2 point plays an important role in calculating the numbers. The whole problem may be reduced to how to reach the 1/2 point (and beyond) in the most efficient way. The way you described (called the allout way in my earlier post) did not take advantage of storing some fuel in the middle, and most likely will not be optimal. In fact, it uses about 1/2 of the total fuel to reach the 1/2 point. For our way, it is about 43%. So any method that can reach the 1/2 point using less than 43% wil be better than ours. But it cannot be by a lot. It is mathematically not possible to use less than about 40%:
With 2N barrels of fuel, you need 2N1 trips to carry them anywhere. So it suggests the differential equation of dy/dx = y  1, where y is fuel consumption and x distance. Solve it and we have y = exp(x) +1. Now we see that y(x  1/2) is about 60% of y(x).

You are right. Somehow, I got stuck somewhere. This happens all the time when solving a problem, once stuck in a position, it is very hard to get out of it. Thanks.

I know why I was stuck. I think if you have to do a storage longer than 1/2 point, you can always do it later. e.g. for 5 barrels, the ideal place is 2/3 point, but you can always do a 1/2 storage for the first trip. Then, in the second trip, when you arrive at the 1/2 point, do 3 one way trip of 1/6 to reach the 2/3 trip. It is equivalent to the 2/3 stop. The way I was thinking, whatever you can do with longer than 1/2 trip, you can always do it with 1/2 point trip first. That's why I was stuck. Now, I feel better. :)

You said it. I got this problem about 6 months ago. At first I tried to work out a general way for N barrels of gas, but soon I found I was in a wrong way, the step by step mathod is more effictive, and the calculation is tedious. The original value of N is 100. Since the calculation is complex, I changed the value of N to 10, made the puzzle easier and more interesting.

This is probably over the tolerance of most people for a single problem. But if you are among the minorities, here is a little more spice:
Let's define the 1/2 point efficiency H to be the percentage of fuel you can carry through the 1/2 point. Carry through means the amount of fuel you carry when passing the 1/2 point minus the fuel you carry when you come back by the 1/2 point. I showed earlier that H < 60%. And for our strategy its 1/2 point efficiency for large amount of fuel is the solution of the equation x = exp(x), or approximately 0.567143. Some other facts about this H: The fuel consumption equation is f = exp(2*H*d), where d is the distance traveled, and f fuel used. The average fuel carried from the start point is (1/H) = 1.7632 barrels; ie if you have 1.7632*N barrels of fuel, you will make N round trips.
Now I am a little more confident about the optimality of the solution, because it involves a nice number.

This is probably over the tolerance of most people for a single problem. But if you are among the minorities, here is a little more spice:
Let's define the 1/2 point efficiency H to be the percentage of fuel you can carry through the 1/2 point. Carry through means the amount of fuel you carry when passing the 1/2 point minus the fuel you carry when you come back by the 1/2 point. I showed earlier that H < 60%. And for our strategy its 1/2 point efficiency for large amount of fuel is the solution of the equation x = exp(x), or approximately 0.567143. Some other facts about this H: The fuel consumption equation is f = exp(2*H*d), where d is the distance traveled, and f fuel used. The average fuel carried from the start point is (1/H) = 1.7632 barrels; ie if you have 1.7632*N barrels of fuel, you will make N round trips.
Now I am a little more confident about the optimality of the solution, because it involves a nice number.
I did not calculate the point efficiency, but I think it is a good view point. Though not proven, I am quite sure this scheme is optimal.