Author |
Topic: How far can a truck go carrying it own fuel? (Read 12330 times) |
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
Margit,
I guess what I should have done all along was to give my method for finding the solution instead of giving my solution!
My first insight was that the efficiency of a solution is determined by the total distance that the truck travels (not very insightful, but it gets better). As you drive forward, you have less gas to move, so you don't have to make as many trips. Over the first stretch of road, you have 10100 miles of gas to move, and you can depart with a maximum of 200 miles at a time, so you must depart at least 51 times. However, as soon as you have gone 2 miles forward these 51 times, you have burned up 102 miles worth of gas, leaving you with 9998 miles of gas. If 2 miles were your first "waypoint", then you could leave the first waypoint only 50 times and carry all the gas.
This is the basis for all the solutions. When you look at the solution on a position-time graph, you get graphs like the ones attached. As you get farther and farther from the starting point, you take fewer trips back and forth.
The first realization I had was that the very last waypoint was 66 2/3 miles from the waypoint before it. This is easy to figure out: you want the last leg of the journey (driving off into the sunset so to speak) to start out with 200 miles of gas. The journey to the last waypoint starts twice, with 200 miles of gas each time. You want to exactly burn up those 200 miles of gas when you make the trip three times, so you need to travel 66 2/3 miles, drop off 66 2/3 miles worth of gas, travel back, pick up 200 miles of gas, then drive to the last waypoint, fill up, and head off into the sunset. This is a perfectly optimal solution (especially if you start with 3 tanks of gas).
After trying many methods, I realized that working backwards from the end was the only way I had ever gotten success. The same way I found the distance to the last waypoint could be used to find the distance to the second-last waypoint as well. We set out for the second-last waypoint 5 times, and we use up 200 miles of gas, so it should be 40 miles from the third-last waypoint. We should use up 40 miles of gas, drop off 120, then use up 40 miles more going back. This raised the problem that you cannot drop off 120 miles of gas. The most you can drop off is 100 miles worth. As shown in the diagram below, there are three times that you must fill up from the second-last waypoint. Since you can drop off at most 100 miles of gas, you can fill up with at most 33 1/3 miles of gas each time, making the second-last waypoint 33 1/3 miles from the third-last.
The third-last waypoint calculation shows the final complication. Using the same calculation as for the second-last waypoint, we would get a distance of 20 miles. However, we do not actually need to fill up fully 5 times. Noticed that when we get back from the second-last waypoint the first time, we have an extra 33 1/3 miles of gas. Therefore, we don't have to fully fill up after the first two trips, because 33 1/3 miles worth are available. So the equation we solve is 5x = 133 1/3 (the 1 tank of gas we can drop off plus the 33 1/3 available). This gives us x = 26 2/3. All the other waypoints can also be calculated in this manner.
|
|
 IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Margit
Guest
|
 |
Re: How far can a truck go carrying it own fuel?
« Reply #26 on: Dec 22nd, 2003, 1:12pm » |
 Quote  Modify
 Remove
|
Ah, thanks James, neatly explained.
I shall now get out the pencil and paper 
Without having worked it out, shouldn't this mean we get 326 2/3 with 6 tanks ?
|
|
IP Logged |
|
|
|
Nigel_Parsons
Junior Member
Gender:
Posts: 63
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #27 on: Jul 17th, 2005, 1:31pm » |
Quote Modify
|
Going for a maximised distance, shouldn't the initial waypoint be at 50 miles, with a fuel dump of 100 spare tanks?
There's a truck ready to depart from a petrol station.
This truck has a gas tank, when it's full, will allow the truck to travel 100 miles. This truck can also fit a removable tank which is of the same volumn as the gas tank.
The current situation is that the gas tank is full and there are 100 removable tanks full of petrol sitting in the petrol staion.
Question, how far can this truck travel?
The truck picks up a spare tank, takes it to dump#1 and returns to the station using up its own tankful. It then refills from the petrol station and takes the next spare out.
This adds almost fifty miles to any other answer given, as the truck starts at the fifty mile point with half a tank of its own, plus 100 spares
Nigel
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #28 on: Mar 19th, 2007, 2:52pm » |
Quote Modify
|
There are two possible formulations: One with no more gas in the gas stattion. The other with infinite amount of gas. Let n be the number of removable tanks.
This seems to me that the 2nd formulation allows us to go nearly n.50 miles. ... left a halffull tank each 50 miles to allow way back for next tank. This creates n.50 miles long starting chain. Now starts the task how far you can go starting with such chain ... I let it open for others 
This puzzle was concerned on the first formulation.
It was almost solved by James ... sorry I should reread it. ... As the amount of gas is limited, you must minimize the distance traveled by car.
It's easier for me to think about it in "projections" of the car positions onto the "distance from origin axes".
If you don't use all the gas, the solution can be improved.
----------
Suppose you left some gas on position x in the best solution.
Let x is maximum such position in a best solution.
We should prove that you can move some gas to position x+d for d>0. This would lead to contradiction. (Let v be the fulltank ratio of the left gas ... On last way through cordinate x you can modify the solution ... change removeble tanks, move 100v/3 forward, refil car tank with as much of v/3 as possible and left rest of the v here. Than return back for the removable tank. At cordinate x+100v/3 fill what does not fit to car previous try.
This will left v/3 at coordinate x+100v/3 ... the contradiction.)
-----------
Therefore you should return for each gas tank whenewer it is not empty.
This defines coordinates xk,xk-1 ... such that you must go at least k times from xk to xk-1 and k-1 times back. As you can use 2 tanks for each return you must return to starting position upper part of (n+1)/2 times.
So the initial portion of way was traversed n+1 times for n even and n times for n odd.
Suppose at first you can leave gas at any place (no tank needed to left the gas there) ... we will think about the constrain later.
So the initial portion traversed (n+1) resp. n times can be chosen such a way you consumed exactly one tank of gas. This reduces problem size from n to (n-1) and we can continue (actually two consecutive portions of path obtained by this approach can be glued together as they represent the same number of traversals).
This leads to 100(1+1+1/3+1/3+1/5+1/5+1/7+1/7+...) upper bound.
Think now about the restrictions for leaving gas anywhere. ... I will continue on the next post.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #29 on: Mar 19th, 2007, 3:18pm » |
Quote Modify
|
BTW: the argument you use all the gas in some of the best solutions can be simplified ... just run 100v/2 forward and backward ... so you can waste the gas ... sorry 
... so the constraints in the next post
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #30 on: Mar 20th, 2007, 7:00am » |
Quote Modify
|
Wow it seemed to be easier at the first look ... James made good job so far. Discrete simulation using something like f,b,d,t used by him will be required ... there may be local changes ... may be it is important where the empty used tanks remain ... so it should be distinguished if you take the tank or not ... (I am not sure it realy helps to take empty tank back). The simulation should not use exact distances but rather "distance intervals".
You can add some constrains ... you neednot leave halfempty tank on the maximal distance so far; comute the ways if halpful; return with nonempty car only for n even ... such tricks can bound the computation space a bit.
The actual distances should be computed at the end solving corresponding equations.
These tricks were used by James so I am reinventing wheel  ...
I hope the empty tank tricks are helpful especialy for big n. ...
|
|
IP Logged |
|
|
|
Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #31 on: Mar 23rd, 2007, 3:52pm » |
Quote Modify
|
what if you carry the max, drive the 1 mile, drop off all but 1, drive back, repeat, i am to lazy to calculate but it does sound good..... hmmm
|
|
IP Logged |
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?
|
|
|
hypocryt
Newbie
Posts: 3
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #32 on: Mar 30th, 2007, 6:35am » |
Quote Modify
|
Although James has advanced the debate on this topic quite far, I think his final number (I believe it was 560 or so) is too high. Indeed, with 128 tanks of gas or less (including the initial tank in your truck), the most one could go is 529.94 miles. Now why is that?
I like James's idea of checkpoints, so let's use'em. If you want to move x tanks forward to the next checkpoint, it will take at least 2x-1 trips to do so (the first tank moved only takes one trip, where as each additional tank moved takes two trips). It is obvious that an Efficient Pickup will add a full 2 tanks (200 miles) to the car's fuel supply. In other words, the car should depart from its checkpoint with only the minimum amount of fuel necessary to get back to the previous checkpoint. As long as a method uses the least number of trips possible and always uses an Efficient Pickup, it should be the best solution for that leg of the trip.
My hypothesis is that the most efficient way to move x tanks of gas is to use up an additional x tanks of gas to move those x tanks (100 * x/(2^x - 1)) miles. So working inductively (and working backwards):
On your last full tank you drive 100 miles.
Use 1 tank to move this 1 tank 100 miles.
Use 2 tanks to move these 2 tanks 66.67 miles.
Use 4 tanks to move these 4 tanks 57.14 miles.
Use 8 tanks to move these 8 tanks 53.33 miles.
Use 16 tanks to move these 16 tanks 51.61 miles.
Use 32 tanks to move these 32 tanks 50.79 miles.
Use 64 tanks to move these 64 tanks 50.39 miles.
This uses 128 tanks in total, to go about 529.94 miles. Since each pickup here is Efficient, one cannot go *more* than 529.94 miles on 128 tanks, and one should certainly go less far with fewer tanks. I know I can get the car 508.68 miles on 101 tanks (i.e. the problem), and optimization can probably push it a little further, but not much.
P.S. To give an example of how this works using a modified version of James's parlance---(1/7) represents the amount of a tank dropped off or picked up or used up in driving. If I want to move 4 tanks the maximum distance, I would: p(2), f(4/7) (i.e. 57.14 miles), d(6/7), r(4/7), p(2), f(4/7), d(6/7), r(4/7), p(2), f(4/7), d(6/7), r(4/7), p(2), f(4/7). At that point you'll have 3 cans 6/7 full, 1 can (onboard) that is 7/7 full, and one gas tank that is 3/7 full. ( 3*6 + 7 + 3 = 28 )/7 = 4 full tanks left.
|
|
IP Logged |
|
|
|
hypocryt
Newbie
Posts: 3
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #34 on: Mar 30th, 2007, 8:08am » |
Quote Modify
|
Although the Jeep Problem is interesting, it's distinguishable. In the Jeep Problem, the Jeep can carry only 1 tank at a time. Moreover, the Jeep has no restrictions on what it can drop off once it gets to a checkpoint.
Dividing the size of the Truck's tanks by 2 (for equivalence with the Jeep), I'd suggest that the Jeep will beat the Truck everytime---the Jeep is able to drop off more than half its fuel at any given checkpoint, whereas the Truck cannot do so (since it can only leave one container behind).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #35 on: Mar 30th, 2007, 8:19am » |
Quote Modify
|
Hmm, yes, I seem not to have looked closely enough at both problems to notice they are not in fact equivalent.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #36 on: Mar 30th, 2007, 8:45am » |
Quote Modify
|
I notice you use a hypothesis to get your figure. The fact James provided figures that contradict your conclusion suggests that at least one of the following hold:
1) His working is in error (in which case it should be possible to find his mistake)
2) Your working is in error (in which case it should be possible to find your mistake)
3) Your hypothesis is wrong (in which case there may be no mistakes to find)
I suspect you do better having an even number of tanks at each checkpoint than having a power of two at each checkpoint, but I don't have the time to work it out at the moment...
[edit]James' figure for 7 extra tanks is 2 miles higher than your "optimum" figure[/edit]
|
| « Last Edit: Mar 30th, 2007, 8:54am by rmsgrey » |
IP Logged |
|
|
|
hypocryt
Newbie
Posts: 3
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #37 on: Apr 1st, 2007, 2:15am » |
Quote Modify
|
rmsgrey, you're totally right. My figures are definitely too low and James's total of 560 may be correct. So let me change my hypothesis from before. An Efficient Pickup is a *necessary* condition of the most efficient trip, but it's not a *sufficient* condition.
Let me think about this a while.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #38 on: Apr 1st, 2007, 11:09am » |
Quote Modify
|
on Apr 1st, 2007, 2:15am, hypocryt wrote:rmsgrey, you're totally right. My figures are definitely too low and James's total of 560 may be correct. So let me change my hypothesis from before. An Efficient Pickup is a *necessary* condition of the most efficient trip, but it's not a *sufficient* condition.
Let me think about this a while. |
|
It's not clear that an efficient pick-up is always optimal when you have constraints on how much fuel you can leave where. James' upper bounds reflect the optimum when you can leave arbitrary amounts of fuel at any drop-point, and his "best" figures work from that by adding a few extra trips to build up fuel storage capacity at the checkpoints...
|
|
IP Logged |
|
|
|
Nigel_Parsons
Junior Member
Gender:
Posts: 63
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #39 on: Aug 26th, 2007, 12:00pm » |
Quote Modify
|
I like James' method on working backward, but I'm not too happy with the method working from the start point. Quote:. As you drive forward, you have less gas to move, so you don't have to make as many trips. Over the first stretch of road, you have 10100 miles of gas to move, and you can depart with a maximum of 200 miles at a time, so you must depart at least 51 times. However, as soon as you have gone 2 miles forward these 51 times, you have burned up 102 miles worth of gas, leaving you with 9998 miles of gas. If 2 miles were your first "waypoint", then you could leave the first waypoint only 50 times and carry all the gas.
|
|
In covering that first 2 miles to the waypoint, you do not burn up 102 miles worth of gas, but 202 miles worth (another full tank!) as there are also the 50 return journeys (of 2 miles each) to the depot to be considered.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Truck with Removable Gas Tanks
« Reply #40 on: Sep 19th, 2008, 4:16pm » |
Quote Modify
|
on Jan 3rd, 2003, 1:40pm, James Fingas wrote:
The directions to implement the best solution are just a sequence of actions. I'll use these actions:
fXXX - go forward XXX miles
rXXX - go backward XXX miles
pXXX - pick up XXX miles worth of gas
dXXX - drop off XXX miles worth of gas
tanks: (bound) distance: solution
0: (100) 100: f100
1: (200) 200: p100, f200
2: (233) 233: p100, f33.3, d100, r33.3, p100, f33.3, p100, f200
3: (266) 266: p100, f66.6, d66.6, r66.6, p200, f66.6, p66.6, f200
4: (286) 286: p100, f20, d60, r20, p200, f20, p20, f66.6, d66.6, r66.6, p20, r20, p200, f20, p20, f66.6, p66.6, f200
5: (306) 300: p100, f50, d100, r50, p200, f50, p50, f50, d50, r100, p200, f50, p50, f50, p50, f200
6: (320) 319: p100, f19, d61.3, r19, p100, f19, p4.6, f33.3, d100, r52.3, p200, f19, p19, f33.3, p33.3, f66.6, d66.6, r66.6, p33.3, r33.3, p19, r19, p200, f19, p19, f33.3, p33.3, f66.6, p66.6, f200
7: (335) 326: p100, f50, d100, r50, p200, f50, p20, f10, d100, r60, f60, p60, f66.6, d66.6, r66.6, p30, r10, p30, r50, p200, f50, p50, f10, p10, f66.6, p66.6, f200
8: (346) 342: p100, f16, d80, r16, p100, f42.6, d100, r42.6, p200, f16, p16, f26.6, p20, f33.3, d100, r60, p16, r16, p200, f16, p16, f26.6, p26.6, f33.3, p33.3, f66.6, d66.6, r66.6, p33.3, r33.3, p26.6, r26,6, p16, r16, p200, f16, p16, f26.6, p26.6, f33.3, p33.3, f66.6, p66.6, f200
|
|
The missprints were mentioned in the discussion, I don't want to talk about them ...
At least the case 7 is not optimal: I use fractions instead of percents (or 100 miles): and adding notation
txxx - take the amount form the tank (p means take the tank, d means drop the tank)
bxxx - return to the tank from the truck (not needed here, but simplifies description ... you can tank less instead)
7: 644/195  3.30
1) repeat 6 times[p1, f7/195,d1,r7/195];p1,f7/195,
2) f4/15,d1,r4/15,
3) t1,p1,f4/15,t4/15,f1/3,d1,r1/3,t4/15,t(-1/3),r4/15,
4) t1,p1,f4/15,t4/15,f1/3,t1/3,f2/3,d2/3,r2/3,t1/3,r1/3,t4/15,r4/15,
5) t1,p1,f4/15,t4/15,f1/3,t1/3,f2/3,t2/3,f1,d1,t1,f1
1) moves all 7 tanks to distance 7/(13*15) using 7/15 of tank
2) creates base 0 at distance 4/(3*5) using 8/15 of tank so one tank emptied so far
3) creates base 1 at distance 1/3 from base 0
4) creates base 2 at distance 2/3 from base 1, leaving 2/3 there
5) final trip to distance 2 form base 2.
base 0 ... initialised with d1, t4/(3*5) used 5 times, but t(-1/3) after the 2nd, so 4/3 in and out.
base 1 ... initialised with d1, t1/3 used 3 times, so 1 in and out.
base 2 ... initialised with d2/3, t2/3 used once, so 2/3 in and out.
I am not sure this is the optimal solution for 7(+1) tanks.
This can be improved to
7/(9*15)+4/15+1/3+2/3+23.32
|
| « Last Edit: Sep 19th, 2008, 5:14pm by Hippo » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #41 on: Sep 21st, 2008, 4:57pm » |
Quote Modify
|
While we are on the subject:
An explorer and his crew want to explore a desert. There are 6 drivers and 6 jeeps with GPS. Each jeep carries a tank of fuel and 6 jerry cans that can contain exactly one tank's worth. Every driver and jeep must make it back to base, but they can transfer fuel before doing so.
If a tank of fuel is worth 80 miles what is the furthest the explorer can drive into the desert and still get back to base camp safely?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #42 on: Sep 22nd, 2008, 4:34am » |
Quote Modify
|
686?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #43 on: Sep 22nd, 2008, 8:56am » |
Quote Modify
|
on Sep 22nd, 2008, 4:34am, Grimbal wrote:
I have about 30% less than that. 
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #44 on: Sep 22nd, 2008, 12:44pm » |
Quote Modify
|
I convert them to hybrid cars 
Or maybe because I assume you can drive 7/12 of 80 miles and refill all cars with 3.5 jerrycans, leaving one half-empty.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #45 on: Sep 24th, 2008, 7:40am » |
Quote Modify
|
Return to the original thread ...
I have planned to code search with dynamic constraints to solve the problem since I have found this thread. Dynamic maintanance of the linear constraints would not be problem, but I have needed good heuristic to eliminate nonperspective branches fast. So I have reread the thread ... especialy James Fingas notes ...
on Dec 22nd, 2003, 11:21am, James Fingas wrote:
After trying many methods, I realized that working backwards from the end was the only way I had ever gotten success. The same way I found the distance to the last waypoint could be used to find the distance to the second-last waypoint as well. We set out for the second-last waypoint 5 times, and we use up 200 miles of gas, so it should be 40 miles from the third-last waypoint. We should use up 40 miles of gas, drop off 120, then use up 40 miles more going back. This raised the problem that you cannot drop off 120 miles of gas. The most you can drop off is 100 miles worth. As shown in the diagram below, there are three times that you must fill up from the second-last waypoint. Since you can drop off at most 100 miles of gas, you can fill up with at most 33 1/3 miles of gas each time, making the second-last waypoint 33 1/3 miles from the third-last.
The third-last waypoint calculation shows the final complication. Using the same calculation as for the second-last waypoint, we would get a distance of 20 miles. However, we do not actually need to fill up fully 5 times. Noticed that when we get back from the second-last waypoint the first time, we have an extra 33 1/3 miles of gas. Therefore, we don't have to fully fill up after the first two trips, because 33 1/3 miles worth are available. So the equation we solve is 5x = 133 1/3 (the 1 tank of gas we can drop off plus the 33 1/3 available). This gives us x = 26 2/3. All the other waypoints can also be calculated in this manner. |
|
This seems almost solves the problem. The method: Incrementaly bound the distances with at most i returns first and than return to solution with given number of tanks works perfect. Actually there is a complication mentioned at most implicitly. When the total distance of several bases is less than 1/2 of tank distance, there is fuel excess so you must "carefully plan tanking/leaving fuel in middle bases". This is generalization of the 1/5->1/3 example above. Even when the optimal "base" distances are computed, the order of their visits is the crucial point of planning.
I have made table upto 8 returns by hands ... I am lazy to implement rational arrithmetics ...
e ... denoting fuel excess reusable in "recurence interface" it's recurrence enter at the same time
[0]: 2 (p1 f1 d1 t1 f1)
[1]: 2/3 (p1 f2/3 d1 t1/3 r2/3 e0 p1 t1 f2/3 t2/3 d1 [0])
[2]: 1/3 (p1 f1/3 d1 r1/3 e1/3 p1 t1 f1/3 t1/3 d1 [1](0) t1/3 r1/3 e0 p1 t1 f1/3 t1/3 d1 [1])
[3]: 4/15 (p1 f4/15 d1 r4/15 e7/15 p1 t1 f4/15 t4/15 d1 [2](1/3) t4/15 t(-1/3) r4/15 e0 p1 t1 f4/15 t4/15 d1 [2] ...
... I must make more compact notation ... I will continue editting the post after a while ... the interesting cases are [4] and [5]
[2]: x=1/3 (p1 fx d1 rx e1/3 p1 t1 fx tx d1 [1](0) tx rx e0 p1 t1 fx tx d1 [1])
[3]: x=4/15 (p1 fx d1 rx e7/15 p1 t1 fx tx d1 [2](1/3) tx t(-1/3) rx e0 p1 t1 fx tx d1 [2](0) tx rx e0 p1 t1 fx tx d1 [2])
[4]: x=1/5 (p1 fx d1 [3](7/15) rx e1/15 p1 t1 fx d1 rx e3/5 {p1 t1 fx tx d1 [3](0) tx rx e0}2 p1 t1 fx tx d1 [3])
Now we use {}k to denote repetition k-times.
Let us denote by Tik the pattern {p1 t1 fx tx d1 [i](0) tx rx e0}k p1 t1 fx tx d1 [i].
So [4]: x=1/5 (p1 fx d1 [3](7/15) rx e1/15 p1 t1 fx d1 rx e3/5 T32)
[5]: x=5/27 (p1 fx d1 rx e17/27 p1 t1 fx tx [4](1/15) tx t(-1/15) rx e0 p1 t1 fx tx [4](3/5) tx t(-3/5) rx e0 T42)
Note that the order in [4] was crucial ... the excess 3/5 is higher than 2x (of 5), but total excess 2/3 is less than 4x.
[6]: x=1/9 (p1 fx d1 [5](17/27) rx e11/27 p1 t1 fx d1 rx e7/9 T54)
[7]: x=1/9 (p1 fx d1 [6](11/27) rx e5/27 p1 t1 fx d1 [6](7/9) rx e5/9 p1 t1 fx d1 rx e7/9 T64)
For the next recurence we will see we should reorder the 3 initial calls (this is possible as they all had excess)
So rewrite the results in better form (at least for [6] this is the final one ... may be some commutative notation would be preferable ... [6]4,5 noting the original one and [6]5,4 noting the following one, some notation for yet nondetermined order ... OK let {x|y|...|z} denotes x,y,...,z in unknown order):
[6]: x=1/9 (p1 fx d1 rx e7/9 p1 t1 fx d1 [5](17/27) rx e11/27 T54)
[7]: x=1/9 ({p1 fx d1 [6](7/9) rx e5/9|p1 t1 fx d1 rx e7/9} p1 t1 fx d1 [6](11/27) rx e5/27 T64)
[8]: x=32/297 ({p1 fx d1 [7](5/9) rx e103/297|p1 t1 fx d1 [7](7/9) rx e169/297|p1 t1 fx d1 rx e233/297} p1 t1 fx tx d1 [7](5/27) tx t(-5/27) rx e0 T74)
What is common for the paths [i]: Once the number of trips to bases having excess is known to be ni than x=1+excess of all trips to further bases/(2i+1-2ni). The order of the trips that loose excess in this step can be choosen such that the further bases are visited first. This allows us to empty the tank on the base such that following higher excesses fit well. The condition for the k-th trip to loose the excess is that average distance of first k such trips is bigger than 1/2. We are looking for minimal ni having compatible xni (x n can be easily computed). The correct ordering of trips having excess so far is delayed to the time they loose the excess. Trips with excess goes first, then trips loosing excess now from furthest. The order of the rest was determined in previous steps.
Trips having excess so far ignore the newly created base, the trips loosing excess now tank to full whenever going through the new base, this allows them to leave the excess in the new base on return. Remaining trips tank to full whenever going through the new base, too.
(n2=0 leads to 1/5 n2>0, so n2=1 leading to compatible x2=1/3.
n3=1 leads to compatible x3=4/15 (ni(>2)=0 obviously fails, ...)
In the next post, I will show some first results using [i].
|
| « Last Edit: Sep 25th, 2008, 8:09am by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #46 on: Sep 24th, 2008, 10:22am » |
Quote Modify
|
Let i: denotes problem starting with filled car and i additional full tanks.
0:  =1 (f1)
1: =2 ([0])
2: y=1/3 =7/3 2.33(p1 fy d1 ry p1 fy d1 t1 [0])
3: =8/32.67 ([1](0) t1 [1])
4: y=1/5 =43/152.87 (p1 fy d1 ry t(2y-1) t1 p1 fy ty d1 [1](0) ty ry t(1-2y) p1 fy ty t(2y) [0])
5: y=1/21 =64/213.05 ({p1 fy d1 [2](1/3) ry t(2y-1/3) t1|p1 fy d1 ry t(2y-1) t1} p1 fy ty d1 [2](0) ty ry t(1/3-4y) p1 fy ty t(4y) d1 [2]) ... 7y=1/3
6: y=4/21 =67/213.19 (p1 fy d1 ry t(2y-1) t1 p1 fy ty d1 [2](1/3) ty t(-1/3) ry t1 p1 fy ty [2](0) ty ry t(1-2y) p1 fy ty t(2y) d1 [2]) ... 7y=4/3
7: y=7/135 =448/1353.32 ({p1 fy d1 [3](7/15) ry t(2y-7/15) t1|p1 fy d1 ry t(2y-1)} p1 fy ty d1 [3](0) ty ry t1 p1 fy ty d1 [3](0) ty ry t(7/15-4y) p1 fy ty t(4y) d1 [3]) ... 9y=7/15
8: y=22/135 =463/1353.42 ... 9y=22/15 ... uff it's time to write a program ... but the pattern can be seen
|
| « Last Edit: Oct 1st, 2008, 1:26pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?  truck2.PNG
« Reply #47 on: Sep 30th, 2008, 1:07pm » |
Quote Modify
|
Finaly I have generated a spreadsheet upto [50], just ni's are important.
Here is the code:
Sub Truck()
' Truck Makro 1.10.2008, Hippo
Dim i
Cells(1, 1) = "i" 'cells(i+3,1)=i
Cells(1, 2) = "n_i" 'cells(i+3,2)=n_i number of trips with excess for [i]
Cells(1, 3) = "excess_end" 'cells(i+3,3)=total excess from stage n_i-1 of trips having no excess on n_i stage
Cells(1, 4) = "dx_i" 'cells(i+3,4)=distance of bases i and i+1
Cells(1, 5) = "x_i" 'cells(i+3,5)=coordinate of the i+1 base (measured from base 0)
Cells(1, 6) = "sum x_i" 'cells(i+3,6)=sum of coordinates of bases 0 to i+1
Cells(1, 7) = "tot end len" 'cells(i+3,7)=total length of trips ending in this stage
Cells(1, 8 ) = "tot len" 'cells(i+3,7)=total length of the journey
Cells(2, 5) = 0
Cells(2, 6) = 0
' i<=2 are precomputed special cases
Cells(3, 4) = 2
Cells(4, 4) = 2 / 3
For i = 0 To 1
Cells(i + 3, 1) = i
Cells(i + 3, 2) = 0
Cells(i + 3, 5) = Cells(i + 3, 4) + Cells(i + 2, 5)
Cells(i + 3, 6) = Cells(i + 3, 5) + Cells(i + 2, 6)
Cells(i + 3, 8 ) = (3 + 2 * Cells(i + 3, 1)) * Cells(i + 3, 5) - 2 * Cells(i + 3, 6)
Next i
i = 1
While Cells(2, 1) > Cells(i + 3, 8 )
i = i + 1
Cells(i + 3, 1) = i
Cells(i + 3, 2) = 0
Cells(i + 3, 7) = 0
While Cells(i + 3, 7) < 1 + Cells(i + 2, 2) - Cells(i + 3, 2) ' number of ending trips < total ending len
Cells(i + 3, 2) = Cells(i + 3, 2) + 1
Cells(i + 3, 3) = (1 + Cells(i + 2, 2) - Cells(i + 3, 2)) * (1 - 2 * Cells(i + 2, 5)) + 2 * (Cells(i + 2 - Cells(i + 3, 2), 6) - Cells(i + 1 - Cells(i + 2, 2), 6))
' = (1+n-n')(1 - 2x(i)) + 2 * (sum x(i - n') - sum x(i - n - 1))=
' = (1-2(x(i)-x(i-n))+...+(1-2(x(i)-x(i-n'))
Cells(i + 3, 4) = (1 + Cells(i + 3, 3)) / (2 * i + 1 - 2 * Cells(i + 3, 2))
Cells(i + 3, 5) = Cells(i + 3, 4) + Cells(i + 2, 5)
Cells(i + 3, 7) = 2 * ((1 + Cells(i + 2, 2) - Cells(i + 3, 2)) * Cells(i + 3, 5) - (Cells(i + 2 - Cells(i + 3, 2), 6) - Cells(i + 1 - Cells(i + 2, 2), 6)))
' = (1+n-n')(2x(i+1)) - 2 * (sum x(i - n') - sum x(i - n - 1))=
' = (2(x(i+1)-x(i-n))+...+(2(x(i+1)-x(i-n'))
Wend
Cells(i + 3, 6) = Cells(i + 3, 5) + Cells(i + 2, 6)
Cells(i + 3, 8 ) = (3 + 2 * Cells(i + 3, 1)) * Cells(i + 3, 5) - 2 * Cells(i + 3, 6)
'x(i)+2((i+1)*x(i)-sum x(i))=x(i)+2(x(i)-x(0))+2(x(i)-x(1))+2(x(i)-x(2))+...+2(x(i)-x(i-1))+2(x (i)-x(i))
Wend
End Sub
I hope ... there is no bug there
on Jan 6th, 2003, 12:08pm, James Fingas wrote:After doing some serious spreadsheeting, I have come up with a method for moving 560.754 miles from the beginning. I worked backwards from the end, and ended up with 57 waypoints (including the end but not the beginning).
|
|
Surprisingly ... I have got for 50 returns value only 5,51. What the 100: value be ...
BTW: I didn't check the fractions shown by excell are exact values. May be they are approximations.
Yes, they are approximations ... dx10=(47+297)/297*13=344/3861 67/752.
[edit]I have replaced the code by the version not ending on 50 returns but on wasting all 101 tanks.[/edit]
Using only 100.995 tanks we can travel 5.611. The 5/1000 of tank will increase result to value rounded to the same 5.611.
|
| « Last Edit: Oct 1st, 2008, 1:36pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel? truck.pdf
« Reply #48 on: Oct 1st, 2008, 1:31pm » |
Quote Modify
|
I am planning to close this by creating a picture discribing the jurney so I allocate this post for the purpose.
It may take a day, but may be delayed much much longer ... OK here is *.ps.zip file
[edit]Replaced by .pdf[/edit]
|
| « Last Edit: Oct 16th, 2008, 2:20pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel? truck15.png
« Reply #49 on: Oct 12th, 2008, 3:59pm » |
Quote Modify
|
So here it is, unfortunately at least for the choosen paths the METAPOST capacity exceeded for 100 tanks. The paths can be optimised not to tank on a trip at a base and later on return leave the fuel at the same base. For such paths the capacity will not exceed probably.
There are two paths on each page. One from top letf to bottom right (returning to left repeatedly) and the other from bottom right to top left (returning to right repeatedly). Each path is scaled to fit on the page. Page "number" correspond to the number of tanks at the start.
The x coordinate corresponds to distance from the start in both cases, the y coordinate corresponds to fuel at the car plus fuel on start in downward path and to fuel at start plus twice fuel at start in upward path. Tanking at bases can be seen by vertical lines in both cases, but tanking at the start can be seen only on upward path. I am not sure which method better describes the situation.
Oops ... file is too long ... I should make just some screen shots.
|
| « Last Edit: Oct 12th, 2008, 4:21pm by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print