Author Topic: 汽车能跑多远？  (Read 40501 times)

warren

• Full Member
• Posts: 148
汽车能跑多远？
« on: 十一月 01, 2004, 06:14:21 pm »

fzy

• Hero Member
• Posts: 520
汽车能跑多远？
« Reply #1 on: 十一月 02, 2004, 09:46:59 am »
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

warren

• Full Member
• Posts: 148
汽车能跑多远？
« Reply #2 on: 十一月 02, 2004, 12:22:23 pm »
Quote from: fzy
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.

sean

• Jr. Member
• Posts: 86
汽车能跑多远？
« Reply #3 on: 十一月 02, 2004, 12:40:14 pm »
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?

warren

• Full Member
• Posts: 148
汽车能跑多远？
« Reply #4 on: 十一月 04, 2004, 04:04:18 pm »

1） 0〈 N 〈= 2， 汽车在起点带上全部油出发，能行驶1000N公里。
2） 2〈 N 〈= 4，记 R=N-2，第一次汽车带油R桶，行驶1000R/3公里到A点，存R/3桶油在A点，返回。 第二次汽车带油2桶，到A点加油R/3桶，能继续行驶2000公里。共行驶（2+（N-2）/3）*1000公里。
3） 4〈 N 〈= 5+2/3，记 R=N-4，第一次汽车带油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+（N-4）/5）*1000公里。当N=5+2/3时，行驶距离是 3000 公里。

fzy

• Hero Member
• Posts: 520
汽车能跑多远？
« Reply #5 on: 十一月 05, 2004, 10:04:55 am »
I got some messy numbers and really do not want to put it up yet

fzy

• Hero Member
• Posts: 520
汽车能跑多远？
« Reply #6 on: 十一月 09, 2004, 01:04:02 pm »
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.)

warren

• Full Member
• Posts: 148
汽车能跑多远？
« Reply #7 on: 十一月 09, 2004, 01:21:06 pm »
Good job! I believe this is optimal. For N=10, the farest place the truck can reach is (3+29/55)*1000=3527km.

warren

• Full Member
• Posts: 148
汽车能跑多远？
« Reply #8 on: 十一月 09, 2004, 02:29:03 pm »
fzy的计算结果与我的计算结果一致,我认为这是最优解.关键是计算出数列 2,2/3,1/3,4/15,1/5,16/105,..., 它们分别是

sean

• Jr. Member
• Posts: 86
汽车能跑多远？
« Reply #9 on: 十一月 09, 2004, 07:26:01 pm »
Quote from: warren
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?

warren

• Full Member
• Posts: 148
汽车能跑多远？
« Reply #10 on: 十一月 09, 2004, 08:23:14 pm »
Quote from: sean
Quote from: warren
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?

fzy

• Hero Member
• Posts: 520
汽车能跑多远？
« Reply #11 on: 十一月 10, 2004, 02:04:32 pm »
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(N-1), 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 (2N-1)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.

万精油

• Hero Member
• Posts: 1831
汽车能跑多远？
« Reply #12 on: 十一月 12, 2004, 04:11:13 pm »
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.

warren

• Full Member
• Posts: 148
汽车能跑多远？
« Reply #13 on: 十一月 12, 2004, 08:18:13 pm »
Quote from: 万精油
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.