Author 
Topic: How far can a truck go carrying it own fuel? (Read 9930 times) 

Feijia Zhu
Guest


How far can a truck go carrying it own fuel?
« on: Dec 22^{nd}, 2002, 4:49am » 
Quote Modify
Remove

Please help me with this question. Urgent! 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? Assume: The truck (apart from its gas tank) can only fit one removable tank, despite whether it's full, half full or empty. Also, petrol can be transferred from the gas tank to removable tank or the other way around at any time. The answer should be a bit more than 500 miles, but I need to know how it is done. Please help me as much as you can. Thank you very much. //Thread title changed by Icarus

« Last Edit: Sep 2^{nd}, 2003, 7:37pm by Icarus » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13638


Re: urgent! A really hard maths question!
« Reply #1 on: Dec 22^{nd}, 2002, 7:11am » 
Quote Modify

If it doesn't need to travel in a straight line, I'd say it could travel 10100 miles on the gas at the petrol station in removable tanks.. It can just travel 100 miles away on the gas tank, than put the petrol from the removable tank in the gas tank and drive back, pick up two other tanks of gas (tranfer the fuel from one to the gas tank), and repeat 50.5 times..

« Last Edit: Dec 22^{nd}, 2002, 7:29am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Feijia Zhu
Guest


Re: urgent! A really hard maths question!
« Reply #2 on: Dec 22^{nd}, 2002, 4:50pm » 
Quote Modify
Remove

Sorry, I didn't state the question properly. I need to know the largest possible displacement the truck can have from the petrol station. Not the total distance this truck can travel.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13638


Re: urgent! A really hard maths question!
« Reply #3 on: Dec 23^{rd}, 2002, 1:36am » 
Quote Modify

in that case I don't see how it could get over 200 miles. Unless it's going downhill/downmountain for an extra 300 miles. And under the rules in the problem that wouldn't even count since a tank of gas gives 100 miles, apparantly regardless of the terrain. Since the truck can carry a total of 2 tanks, 200 miles is the limit. Unless it can carry more tanks than it 'fits' (fit in this interpretation being 'equip', rather than 'have place for'). But since it's not specified how much it then could carry unequipped it could be anything from 0 to 99, and three wouldn't be an obvious answer.. Oh wait.. I think I see another way.. You could carry a tank for 50 miles, drop it off, get two new tanks from the petrol station (one to fill the gas tank), repeat that a few times. That will leave 50 tanks at the dropoff point provided nobody steals them in the mean time. Now you can repeat that for another 50 miles further up, etc.. It's like the camels and bananas riddle.. Though I think it should have been mentioned you can leave the tanks in the middle of nowhere..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Kozo Morimoto
Junior Member
Posts: 114


Re: urgent! A really hard maths question!
« Reply #5 on: Dec 23^{rd}, 2002, 7:41pm » 
Quote Modify

Its the same problem as the camel problem, but in the camel problem, the amount of fuel is an integer multiple of the total capacity (3000/1000) I'm having problems here cause the total fuel is not on integer multiple (1100/200) and am not sure of how to deal with this. I'm getting 366.55 as the total distance, but it seems like this needs a brute force approach which I'm trying to avoid...


IP Logged 



Feijia Zhu
Guest


Re: urgent! A really hard maths question!
« Reply #6 on: Dec 23^{rd}, 2002, 11:19pm » 
Quote Modify
Remove

Please help me, please help me ... ... It's a matter of life and death ... ...


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13638


Re: urgent! A really hard maths question!
« Reply #7 on: Dec 24^{th}, 2002, 1:25am » 
Quote Modify

on Dec 23^{rd}, 2002, 7:41pm, Kozo Morimoto wrote: I'm having problems here cause the total fuel is not on integer multiple (1100/200) and am not sure of how to deal with this. 
 You don't have to use integer amounts of fuel here, I think.. You could drive f.i. half a mile, rather then 0 or 1. Fuel doesn't go bad like bananas if you don't use integer amounts


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Kozo Morimoto
Junior Member
Posts: 114


Re: urgent! A really hard maths question!
« Reply #8 on: Dec 24^{th}, 2002, 3:00am » 
Quote Modify

Not integer amounts, integer multiple of max capacity. From looking the camel/banana problem, the max cap is 1000 and after every checkpoint, you've spent 1000. So at the first checkpoint, you have 2000 left. Then after the second checkpoint, you have 1000 left. This is so that you always start on your 'trip' with a full tank. I was thinking of doing this with this problem. Say checkpoint is at distance A from start. Starting with a full load each time, so to get to A and back, you can leave 2002A of fuel there. If you do this five times, you'll have 100010A of fuel at A and 100 left at start. So when you get to A for your last trip, you are at A and have 100010A + 100A = 11009A of fuel left. You want this to be 900 (1100200), so A = 200/9. But then I realized that you can't leave more than 100 at A on the first trip cause 1 spare tank can only hold 100 max. And number of spare tanks has to be integers... OK, say you want to use up 100 fuel by each checkpoint. So you want to transfer 1000 fuel to checkpoint A using only 100 fuel. You'll need (101)*2+1 trips = 19 trips so check point A is 100/19 from the start. This means that you fill up the truck but don't refill until you've got all the 10 tanks to A. Do same to point B, which is 100/17 from A. You get to checkpoint I 113.325553 from the start and you have 200 left, which you can carry and go, so in total you can get to 313.325553 using this method. However, this is not optimal as you drive around with near empty truck for some of the trips and I think you can utilize this. I *believe* this is a brute force optimization problem. The complexity is higher than the camel/banana problem.


IP Logged 



Feijia Zhu
Guest


Re: urgent! A really hard maths question!
« Reply #9 on: Dec 24^{th}, 2002, 7:59pm » 
Quote Modify
Remove

on Dec 24^{th}, 2002, 3:00am, Kozo Morimoto wrote:Not integer amounts, integer multiple of max capacity. From looking the camel/banana problem, the max cap is 1000 and after every checkpoint, you've spent 1000. So at the first checkpoint, you have 2000 left. Then after the second checkpoint, you have 1000 left. This is so that you always start on your 'trip' with a full tank. I was thinking of doing this with this problem. Say checkpoint is at distance A from start. Starting with a full load each time, so to get to A and back, you can leave 2002A of fuel there. If you do this five times, you'll have 100010A of fuel at A and 100 left at start. So when you get to A for your last trip, you are at A and have 100010A + 100A = 11009A of fuel left. You want this to be 900 (1100200), so A = 200/9. But then I realized that you can't leave more than 100 at A on the first trip cause 1 spare tank can only hold 100 max. And number of spare tanks has to be integers... OK, say you want to use up 100 fuel by each checkpoint. So you want to transfer 1000 fuel to checkpoint A using only 100 fuel. You'll need (101)*2+1 trips = 19 trips so check point A is 100/19 from the start. This means that you fill up the truck but don't refill until you've got all the 10 tanks to A. Do same to point B, which is 100/17 from A. You get to checkpoint I 113.325553 from the start and you have 200 left, which you can carry and go, so in total you can get to 313.325553 using this method. However, this is not optimal as you drive around with near empty truck for some of the trips and I think you can utilize this. I *believe* this is a brute force optimization problem. The complexity is higher than the camel/banana problem. 
 Well said Kozo. You guys can save my life by solving this maths problem. I need the full solution by the end of this year, please help me. I posted the problem here because I truly believe you guys are the best for the job. Merry Christmas, hope I would greet again next year ...


IP Logged 



Kozo Morimoto
Junior Member
Posts: 114


Re: urgent! A really hard maths question!
« Reply #10 on: Dec 26^{th}, 2002, 4:01pm » 
Quote Modify

Are you sure its >500? It may be helpful to think backwards... To get to 500 on the last gallon, you need to have 200 gallons at the 300 mile mark. (or 150gallon at 350 mile mark etc etc) 200 gallons is 1 full spare and 1 full onboard tank... It may be helpful if YOU provided some work you've done as well 'cause you haven't given us anything! Or start with less spare tanks: if you have 1 full truck and 1 spare tank, the best you can do is obviously 200 miles. What happens if you have 1 full truck and 2 spares? How much can you do? 233 1/3? Can you do more?


IP Logged 



Kozo Morimoto
Junior Member
Posts: 114


Re: urgent! A really hard maths question!
« Reply #11 on: Dec 26^{th}, 2002, 5:04pm » 
Quote Modify

After more thought, I still think just over 313 is the best solution. Say you want to transfer as much fuel to the 1 mile point. You start out with 100+100, and then drop off the 100 and go back, and you use 2 gallons. You do this 8 more times, and you have 900 gallons at 1 mile point and you used up 18 gallons and you are back at start with 182 gallons. You take that to the 1 mile point and you end up with 1081 gallons at 1 mile point. So you did 9 return trips and 1 oneway trip doing the 1 mile 19 times at a cost of 19 gallons. You can keep doing this, but at some point, you have less fuel and you reduce the number of return trips necessary to fetch the fuel. This happens at 100/19 miles when you use up the first 100 gallons. After that, you cost per mile reduces to 17 gallons instead of 19 gallons. This keeps going with 15gallons/mile, 13gallons/mile etc until you end up with 200 gallons left, whereby you just go on a oneway trip. This method nets you a total displacement of 313.3256 miles. I'm not sure if there are any tricks you can do with filling up tanks and unfilling tanks etc etc to increase the distance.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13638


Re: urgent! A really hard maths question!
« Reply #12 on: Dec 27^{th}, 2002, 6:17am » 
Quote Modify

I get to 428.43 miles. That's by using 1 gastank at a time to move all the others to the next point. Taking N to be the number of times you go back to pick up a gastank, 2N+1 is the number of times you drive the same distance between one point and the next. so first you pick up 99 (after bringing the first tank to point 1) on one tank of gas you can get 100/199 miles from your starting point this way. After that you've used one tank of gas, so for the next point you need to return only 98 times, and you can get 100/197 miles further.. the total distance you can drive = sum(100/(2*x+1), x, 0, 99) + 100 I'm sure it can be improved.. Seeing how you drive the same piece of road a lot at the start.. If you use 50 tanks of gas to the first checkpoint (which is thus further away) you allready gain about 16 miles I think..

« Last Edit: Dec 27^{th}, 2002, 6:18am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Kozo Morimoto
Junior Member
Posts: 114


Re: urgent! A really hard maths question!
« Reply #13 on: Dec 28^{th}, 2002, 6:13pm » 
Quote Modify

I misread he question initially... If you make the checkpoints at 50 mile intervals, you get exactly 500 miles. (you'd have 200 gallons left at the 300mile mark) So if you fiddle around with the checkpoint intervals, you should be able to get more than 500 miles.


IP Logged 



Feijia Zhu
Guest


Re: urgent! A really hard maths question!
« Reply #14 on: Dec 29^{th}, 2002, 1:31am » 
Quote Modify
Remove

Thanks for the help. Here's what I got for the question, but it's not good enough, I'll be most grateful if anyone can get as far as 520 miles. Kozo is right, if you fiddle around with the checkpoint intervals, you do get a better solution. My answer is 510.8749 miles There are altogether 101 tanks of petrol. 1st checkpoint: 100/199 miles from start, you can transport 100 tanks of petrol here, but 1 tankful petrol is consumed. 2nd checkpoint: 50 miles from the 1st checkpoint. You will have 50.5 tanks of petrol left. 3rd checkpoint: 100/198 miles from the 2nd checkpoint. That is to use the half tank of petrol to transport 50 tanks of petrol to 3rd checkpoint. So 50 tanks left. 4th checkpoint: 50 miles from the 3rd checkpoint. You will have 25.5 tanks of petrol left. 5th checkpoint: 100/98 miles from the 4th checkpoint. That is to use the half tank of petrol to transport 25 tanks of petrol to 5th checkpoint. So 25 tanks left. Keep going and you'll eventually get 13 checkpoints altogether. 6th checkpoint: 100/47 miles more and 24 tanks left. 7th checkpoint: 50 miles more and 12.5 tanks left. 8th checkpoint: 100/46 miles more and 12 tanks left. 9th checkpoint: 50 miles more and 6.5 tanks left. 10th checkpoint: 100/22 miles more and 6 tanks left. 11th checkpoint: 50 miles more and 3.5 tanks left. 12th checkpoint: 50 miles more and 2 tanks left. 13th checkpoint: 200 miles more and 0 tanks left. Add up the total and you get: 500+100/199+100/198+100/98+100/47+100/46+100/22=510.8749 miles This is definitely NOT good enough. Please find out a way to get more than 520 miles and only then my life can be saved. I don't have much time left, 48 hours is all I've got. Help me ...


IP Logged 



Kozo Morimoto
Junior Member
Posts: 114


Re: urgent! A really hard maths question!
« Reply #15 on: Dec 29^{th}, 2002, 6:30pm » 
Quote Modify

I think you can better the first leg. Instead of 100/199, say you want the last 'trip' to the first check point to start out with 200 gallons. So excluding the last 1way trip, you need to carry 10100200=9900 gallons. Since you want to reduce the number of return trips by at least one each checkpoint, you want to use up at least 100 gallons, so the total amount you want to end up at checkpoint 1 (excluding the last trip) is only 9800. Which mean you only need 196 trips (or 98 return trips) so you can set checkpoint 1 to be 100/196 miles from the start. Then you have the 200 left to get to check point 1 and end up with 200100/196. You should try to set the trips so that you always have 200 to start the one way trip to the next checkpoint. I don't understand why you switch between 50 mile runs and shorter runs on your answer, but your answer seems to work out higher than mine. There must be something to tell you when it is beneficial to go 50 miles or go shorter for the next checkpoint. Hope this helps.


IP Logged 



S W F
Guest


Re: urgent! A really hard maths question!
« Reply #16 on: Dec 30^{th}, 2002, 12:25pm » 
Quote Modify
Remove

It looks like you are unecessarily constraining yourself to completing each stage before moving on to the next. For example, between checkpoint 9 and 10, you progress 100/22 miles in going from 6.5 to 6 tanks. It is possible to progress 50/7 miles when going from 6.5 to 6 tanks, if you also work on checkpoint 11 before checkpoint 10 is complete. Just that one change increases your total by 2.6 miles. Changing all your non50 mile stages this way may give you the 520 miles needed to save your life. Or maybe you need to completely rethink the problem without constraining yourself in this way. Here are some hints for moving from your checkpoint 9 to 10 in 50/7 miles. Start with 2 full tanks and go to checkpoint 10, drop off a full tank, return to checkpoint 9. Take another full tank to checkpoint 10. Fill up the truck's tank from one of the tanks at checkpoint 10, and take a full tank to checkpoint 11, and return to checkpoint 10. At that point the truck's tank is empty. Fill the truck's tank with just enough fuel to get back to checkpoint 9, and continue. If you keep transferring fuel around between the truck's tank and the movable tanks so you are not wasting space by arriving back at checkpoint 9 with excess fuel, you will be able to have 50/7 miles between checkpoints 9 and 10.


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: urgent! A really hard maths question!
« Reply #17 on: Jan 2^{nd}, 2003, 1:56pm » 
Quote Modify

I think you may be missing the fact that the truck is sitting at a petrol station! Don't use the tanks at all for the first 50 milesjust fill 'er up from the pump


IP Logged 
Doc, I'm addicted to advice! What should I do?



James Fingas
Uberpuzzler
Gender:
Posts: 949


Truck with Removable Gas Tanks
« Reply #18 on: Jan 3^{rd}, 2003, 1:40pm » 
Quote Modify

I have come up with a reasonably tight upper bound on the distance that the truck can travel. It is based on the following considerations: How can we get the truck to travel the maximum distance? By taking the smallest number of trips possible to go back and get more gas. Consider that, to start with, you have 10100 miles worth of gas at the petrol station. You can remove up to 200 miles worth at a time, so you must leave from the petrol station at least 51 times in order to carry all the gas away. There is obviously no point in leaving gas behind. If you leave from the gas station 51 times, you must return to the gas station 50 times. Therefore, the first section of road going away from the gas station will be driven over a minimum of 101 times. How long is this first section of road? Well, long enough that we no longer have 10100 miles worth of gas to carry. After merely 100/101 miles, we have used up 100 miles worth of gas in making these 101 oneway trips. If 10000 miles worth of gas were located there, we would need to leave there only 50 times to get all the gas, and return 49 times. We would then use up 200 more miles worth in 200/99 miles, getting us down to 9800 miles worth of gas. This creates the following sum as an upper limit for the problem: 100/101 + 200/99 + 200/97 + 200/95 + ... + 200/3 + 200/1 = 588.5 miles This, as I have said, is an upper limit. The complicating factors are that you can never drop off more than 100 miles worth of gas, you can never have more than 100 miles worth of gas after you drop some off, etc. For example, if you travel 100/101 miles, you can only drop off 100 miles worth of gas, and you will return with an almostfull tank, meaning that you cannot pick up 200 miles worth of gas. Because you don't pick up 200 miles worth, you increase the number of trips you must take. I'm going to try to compute an upper bound that takes this into account. That being said, here are nearoptimal solutions for a few cases where you start with fewer than 100 removable tanks. Here is the format I present my answers in: number of tanks: (theoretical upper bound) best solution so far: directions to implement best solution 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 Some of these numbers are rounded off for simplicity's sake, so they might not work out perfectly the way they're shown here (eg. there's a little gas left somewhere, or there isn't quite have enough to do one step). You can see that in all these cases, I manage to come pretty close to the theoretical bound. I believe that it gets harder as we get more gas tanks, but this is a start anways. I have also found out how to go exactly 519 miles, but it's a hybrid of this and a binary method.


IP Logged 
Doc, I'm addicted to advice! What should I do?



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: urgent! A really hard maths question!
« Reply #19 on: Jan 6^{th}, 2003, 12:08pm » 
Quote Modify

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). It takes 56.5 round trips (one going to each waypoint from the beginning) to complete the solution. Coincidentally (or is it?), this takes 10099.88 miles worth of gas. Each round trip has five stages: 1) In the first stage, you drive out from the beginning, topping up at every waypoint you get to (this stage may have zero length). 2) In the second stage, you drive out towards the destination waypoint, without topping up at every waypoint. 3) The third stage is dropping off the gas tank at the destination waypoint. 4) In the fourth stage, you head back towards the petrol station without picking up any gas. 5) In the fifth stage, you keep going back towards the petrol station, picking up just enough gas at every waypoint to make it to the next waypoint. The transition between stages 1 and 2 occurs at the same point as the transition between stages 4 and 5, and may involve partially topping up the tank at some waypoint. This may be the optimal solution given the constraints on the truck, but I'm still trying to find some optimization...


IP Logged 
Doc, I'm addicted to advice! What should I do?



Kugar
Guest


Re: How far can a truck go carrying it own fuel?
« Reply #20 on: Nov 19^{th}, 2003, 4:18am » 
Quote Modify
Remove

i am only 14 but here is the way i see it. i would think that you would drive out 50 miles drop off a tank then drive back another 50 to pick a tank up. seeing you have used 100 miles you would need to fill up your tank and pick up another one. Then drive out and drop it off. i will work this out and how far you will have to drive out but i like the problem thanks. I would see it you slowly work your way out maybe building your way up so you would have 40 full tanks 100 miles out and 20 200 miles out and 10 300 miles out then you would start moveing out furthur basicly moveing the pertol station in a way. you probably wont make any sence of this but i just wrote it to help


IP Logged 



LZJ
Junior Member
Gender:
Posts: 82


Re: How far can a truck go carrying it own fuel?
« Reply #21 on: Nov 25^{th}, 2003, 7:32am » 
Quote Modify

To Kugar: Well...I think you should take a closer look at the question...in this manner, one can only move half the oil tanks left a distance of 50 miles, and not 100 miles. Furthermore, there would be half a tank extra: For example, if you start off with 40 tanks, if you move it 50 miles away, you will end up with 20.5 tanks worth of petrol.


IP Logged 



Margit SchubertWhile
Guest


Re: How far can a truck go carrying it own fuel?
« Reply #22 on: Dec 18^{th}, 2003, 7:36am » 
Quote Modify
Remove

James, in reply 18 for 4 tanks, you begin : 4: (286) 286: p100, f20, d60 Ermm, where do you put the 40 ?


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: How far can a truck go carrying it own fuel?
« Reply #23 on: Dec 18^{th}, 2003, 12:52pm » 
Quote Modify

on Dec 18^{th}, 2003, 7:36am, Margit SchubertWhile wrote:James, in reply 18 for 4 tanks, you begin : 4: (286) 286: p100, f20, d60 Ermm, where do you put the 40 ? 
 Hmm ... good point. I think I screwed up, although you'll notice that there are only 20 of the 40 left when you get there. The same problem applies to the 6 tank and 8 tank solutions I gave. Maybe I should check my full solution ... nope, it uses a different waypoint method (always dropping off 100 except for the last waypoint). And there's another error too. You can't pick up 200 unless you're empty (and you won't be after driving only 40 miles). Try the following instead: 4: (286) 286: p100, f20, d100, r20, p140, f20, p20, f66.6, d66.6, r66.6, p20, r20, p160, f20, p60, f66.6, p66.6, f200 A fix like this should also be applicable to the 6 and 8 tank solutions too.


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 #24 on: Dec 18^{th}, 2003, 2:13pm » 
Quote Modify
Remove

That looks as though it works James. Tell me, how did you arrive at these waypoint distances versus # of tanks ? Why is (apparently) 20 and 66 2/3 optimal ? (and the splits for 5,6,7,8 tanks) Seems extremely weird to me.


IP Logged 



