1
$\begingroup$

There are two cars, Car A and Car B. Each can only carry enough fuel to travel 100 miles. You set out on a journey with both cars. In the middle of the journey one car can transfer some amount of fuel to another car but should have enough fuel left to travel back home. One car has to go far away and one car has to return home. What is the highest possible distance you can travel from your home?

$\endgroup$
  • $\begingroup$ Does each car have its own driver? $\endgroup$ – 2012rcampion May 1 '16 at 23:48
  • $\begingroup$ Yes, each car has its own driver $\endgroup$ – mathnoob123 May 2 '16 at 16:21
5
$\begingroup$

Assuming they get the same gas mileage:

$133 \frac13$ miles.

Reasoning:

You drive both cars $33 \frac13$ miles. Then you transfer $33 \frac13$ miles worth of gas from one car to the other. That car now has enough gas to go another $100$ miles, and the other car has exactly $33 \frac13$ miles worth of gas left in the tank. That's just enough to get home.

$\endgroup$
  • $\begingroup$ But why is this the highest? $\endgroup$ – Trenin May 3 '16 at 12:15
8
$\begingroup$

There is (I think) an ambiguity in the question. I will (I hope) solve it each way.

[EDITED to add: after I wrote this, the question was edited to make it much less ambiguous. I'll leave what follows here in case other variants of the question arise later...]

Let me first dispose of a boring ambiguity. I take it the goal is to get as far away as possible rather than to travel as far as possible. Otherwise we can get both cars home with one of them travelling a total of 200 miles, as follows: car A just sits there, car B does a 100-mile round trip, car A transfers all its fuel to car B, car B does another 100-mile round trip. This is clearly best possible; it is also clearly boring.

OK; now I think we have the following interpretations.

Both cars must return home

Each car has a tank holding 100 miles' worth of fuel. Fuel can be transferred between colocated cars. Both cars must return home at the end. The goal is to maximize the furthest distance from home of whichever car goes further.

Only one car must return home; get it as far as possible

Each car has a tank holding 100 miles' worth of fuel. Fuel can be transferred between colocated cars. At least one car must return home at the end. The goal is to maximize the furthest distance from home of a car that returns home.

Only one car must return home; get either car as far as possible

Each car has a tank holding 100 miles' worth of fuel. Fuel can be transferred between colocated cars. At least one car must return home at the end. The goal is to maximize the furthest distance from home of the other car.

Before attacking any of these, and just to make sure the assumptions are clear, I'll solve two boring simpler problems. No fuel transfers; both cars must return home: in this case each car goes 50 miles, turns and comes back, so the answer is 50 miles. No fuel transfers; one car needn't return: in this case one car does the round trip and the other just drives 100 miles and stops, so the answer is 100 miles.

So the challenge in the first two cases is to do better than 50 miles; the challenge in the second case is to do better than 100 miles.

Both cars must return home

Clearly any solution must begin as follows: the two cars set out; after some distance d we transfer some fuel (say, f miles' worth) from A to B; B goes off leaving A behind. (If A continues with B then we might as well have done the fuel transfer later.) Then B must make a round trip. When A and B meet again, it seems like we have three options: transfer fuel from A to B, transfer fuel from B to A, don't transfer. We can ignore the B-to-A option because it's equivalent to just transferring less at the start. And after that we can't do better than just driving home again (remember that the goal is to get as far away as possible, not to travel as far as possible).

So, if there isn't another transfer at the tail end, car B goes a distance d; after the transfer it has $100-d+f$ miles' worth of fuel, of which it will need d to get home from where it is now; the remaining $100-2d+f$ will get it to (and back from) a further distance $50-d+f/2$, for a total distance of $50+f/2$. So we want to make $f$ as large as possible; the constraints are that we not transfer more fuel than A needs to return home (so $f\leq 100-2d$) and that we not overfill B's tank (so $f\leq d$). The biggest possible $f$ will occur when these constraints match up, so $100-2d=d$; that is, $f=d=\frac{100}{3}$ and the distance achieved will be $50+f/2=50+50/3=66\frac{2}{3}$ miles.

But maybe we can do better if there is another transfer, let's say of g miles' worth of fuel, at the tail end. Clearly it's wasteful if either car has any fuel left when they get home, so after the second transfer both cars must have exactly d left. So the second transfer takes A from $100-d-f$ to $d$, so we must have $g=100-2d-f$ or $f+g=100-2d$. So car B travels a distance $d$, then gets $f$, then does a round trip -- call its length $l$ --, then gets $100-2d-f$, then has exactly $d$ to get home. So $100-d+f-2l+100-2d-f=d$, which simplifies to $l=100-2d$. The actual distance attained is $d+l=100-d$, so we want $d$ as small as possible -- subject to the constraints that B's tank not overflow and that the transfer of $f$ is enough for the round trip. There is already too much algebraic manipulation in this paragraph so I will spare you the details; the optimum turns out to be to take $d=25$, $f=25$, $g=25$, leading to a distance of 75 miles. (Which, indeed, is better than without that transfer, which isn't so surprising since "no transfer" is just the special case $g=0$.)

One car must return home; get it as far as possible

This is just like the previous case except that now we don't need A to return. Otherwise, the structure has to be the same as in the previous case; we now want the final transfer to empty A's tank (unless it was already emptied by the first transfer). So now the process is as follows: both go $d$ and have $100-d$ in their tanks; transfer to get $100-d-f$ in A and $100-d+f$ in B; B goes a distance $2l$ and now has $100-d-f-2l$; transfer everything so B has $200-2d-2l$ which must equal $d$. We now readily find that the distance achieved is $100-d/2$ so we want $d$ as small as possible; the relevant constraints are that $100-d+f\geq 2l=200-3d$ or $d\geq (100-f)/2$ and that $100-d+f\leq100$ or $d\geq f$; we can make $d$ smallest when these are equal, leading to $d=f=100/3$ and a distance of $100-100/6$ or $83\frac{1}{3}$ miles.

One car must return home; get either as far as possible

It will of course turn out best to get the other car as far as possible. So now we drive them both a distance $d$, transfer $f$ from A to B, drive A home (so we want $f=100-2d$), and drive B until it runs out of fuel. Distance achieved by B is then $d+(100-d)+(100-2d)=200-2d$ so we want $d$ as small as possible. The constraint is that B not be overfilled, which means $100-d+f\leq100$ or $d\geq f$ or $d\geq 100-2d$, so the best we can do is $f=d=100/3$ for a distance of $200-200/3$ or $133\frac{1}{3}$ miles.

(This last solution is the one offered some time ago by paste, though s/he didn't prove it optimal.)

$\endgroup$
2
$\begingroup$

Adding to Gareth McCaughan's list of possible answers:

Another way to interpret the question is that the 'support' car can make an unlimited number of trips back and forth, in order to get the other car as far away as possible from the refuelling point, as long as the support car returns home at the end. In this case, the theoretical limit is 150 miles. Drive the 'goal' car to a distance A where A < 50. The number of miles worth of fuel the support car can transfer on each trip is Q = 100-2A. As A approaches 50, Q approaches 0 and the number of support trips approaches infinity. With enough support trips, the goal car can be completely filled, allowing it to go another 100 miles, so the limit it 150 miles.

$\endgroup$
  • $\begingroup$ I thought about this too, but the fuel transfer must be "in the middle of the journey"; I guess it depends on how strictly we interpret "middle". +1 $\endgroup$ – Jonathan Allan May 2 '16 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.