0
$\begingroup$

Suppose you've got a car. But, you can only take 4 jerrycans with you. And one full tank (which can hold exactly the contents of one jerrycan). The content of every jerrycan is enough for travelling 1km. At the start are $\infty$ jerrycans!

Now, there are a few questions and we couldn't find an answer for it. So can you help us with those questions?

With 20 jerrycans you can travel 10km if you want to travel back. Now, if you want to travel in one straight line without going back, you can travel 10km. What is the best strategie to travel more than 20km?

What is the longest distance you can travel without going back to the start?

What is the minimum number of jerrycans needed to travel more than 20km?

  • 0
    Your $\infty$-many jerrycans are they full or empty? Never mind how you ever get/got them filled, if you can take only $4$ of them in the car and are not allowed to go back to the start for more, what use are the others, and how can one ever get more than $5$ tanks=$5$km away?2012-01-08

3 Answers 3

2

The longest distance you can travel without returning to start is 5 km-you start with a full tank and four jerrycans.

For a straight run away from start you basically fill up at start, travel a distance $d$, drop all the fuel you can, and return to start. You will burn $5$ cans to drop $(5-2d)$ at position $d$. If we want the most can-km out of our $5$ we can maximize $d(5-2d)$ and find $d=\frac54$ and we drop $\frac52$ cans. This means that in this model (I have not proved it optimum) you need twice the fuel you want at point $a$ to be at $a-\frac54$. To do an outbound $20$ km, we need to fill at $15$ km. That needs $5$ cans at $15$. To do that we need $10$ cans at $13\frac34$, $20$ at $12\frac12$, on to $20*2^{10}=20480$ cans at the start. You may be able to do better for a $10$ km out an back, but this shows one way to think about it.

Your first question says you can go 10 km out and back on 20 cans, but I think it is clear you cannot unless you can carry 19 of them, not the 4 you specify.

The second paragraph demonstrates that you can go arbitrarily far from start if you have enough fuel. Though the required quantity rises rapidly, it is always finite.

  • 0
    @Ruud:One way to prove a strategy is optimal is to find some quantity that is required to be a certain size and show any change to the strategy makes it worse. I haven't found it. For the 10km out and return, I suspect you want many small dumps, as the fuel you burn on the way back went out too far.2012-01-09
1

Assuming that you can refuel from your cans as you go, and that you can add any fraction of a can into the tank, you may as well think of your tank is holding 5 cans.

This is the classic Jeep problem, see the link for its standard solution. I haven't found a proof online that isn't behind a copyright wall; if you have JSTOR access, then David Gale's article "Jeeper by the Dozen" is pretty clear.

  • 0
    @Ruud: this is a more efficient way than mine. I believe it will need a factor $e$ for every 2.5 km instead of a factor $4$. For distance $4$ (measured in full cars) you need 419 loads=2095 gallons. The way you specified the problem, you can't dump more than 0.8 tank=4 gallons, which will lead to some inefficiency. Maybe being clever with bringing back empties and dropping them will help.2012-01-10
0

Disclaimer: I haven't read about the Jeep problem (yet). Here's my solution.

This problem has some similarity to the one confronted when bringing satellites into orbit: in order to be able to have one unit of fuel available to give the final acceleration, many more units are needed to get that unit of fuel at the elevation and the speed where it is to be consumed. The amount of fuel increases exponentially with the final result to be attained. In the current problem the factor is distance from the start rather than elevation/speed.

I will argue below that the most economic way to transport fuel in a sustainable way (with the car returning to its starting point) consists of steps in which one starts with a full tank and four jerry-cans, stops after half a km dropping the jerry-cans and returns to the starting point, having emptied the tank on arrival. Since halves will be present throughout, I take half a jerry-can as unit of fuel, and half a km as unit of distance. I assume one is allowed to leave half-full jerry-cans along the route (or other fractions, but I will not use them); in practice this occurs after filling-up when the tank is still half-full. However I suppose one can only dump at most $4$ jerry-cans of fuel ($8$ units) at once, i.e., one cannot recover any fuel from the tank. This is the reason I chose the unit distance: making shorter round trips than that would imply there would be unused fuel in the tank on return, which is not optimal.

To get $n$ units of fuel at a distance of $d+1$ units, how many do we need at distance $d$? Basically we need $\frac54n$ units, using the above method. However the final trip from level $d$ to $d+1$ can be one-way, so in it we can transport up to $9$ units of fuel and consume only one unit (we cannot unload more than $8$ units, but the remaining fuel unit will serve for the next, forward, trip). The final trip can be suboptimal if $r$ is small, but there is no point in putting fuel at distance $d$ just to fill the car for this last trip. So we decompose $n$ into $q$ groups of $8$ and one final group of $r\leq 9$ units; we shall need $10q+r+1$ units of fuel when stating from level $d$. Therefore define $f:\mathbb N\to\mathbb N$ by $f(n)=n+2((n-2)\div8)+1$ for $n\geq2$ (where $\div$ denotes the quotient of integer division), and $f(n)=n+1$ for $n<2$. Since we must travel $40$ units and need no fuel left at the end, the required amount of fuel is $f^{40}(0)=7348$ units of fuel, or $3674$ jerry-cans. The list of amounts of fuel needed at successive distances is [7348, 5879, 4704, 3763, 3010, 2409, 1928, 1543, 1234, 987, 790, 633, 506, 405, 324, 259, 208, 167, 134, 107, 86, 69, 56, 45, 36, 29, 24, 19, 16, 13, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0].

To see that moving using $10$ units of fuel to place $8$ units at the next distance is the optimal sustainable move, argue as follows. I claim that the "free-market" price of a unit of fuel at distance $d$ is $(\frac54)^d$ (at least when $d\in\mathbb N$). If one imagines getting paid this amount when leaving fuel, and having to pay the same amount when picking it up again, then the proposed move is without profit or loss, while all other moves operate at a loss. For instance using $10$ units bought at distance $d$ (price $10(\frac54)^d$) to deliver $6$ units at distance $d+2$ (price $6(\frac54)^{d+2}$) and drive back turns out a loss, since $6(\frac54)^2=\frac{75}8<10$. The same price for non-integer $d$ shows that using intermediate distances is not profitable (taking into account that one cannot deliver more than $8$ units; without this restriction very short moves would be very slightly profitable). This means that one cannot actually deliver fuel at non-integer distances at this price (I'll leave computing the true free-market price at such distances as an exercise).

Note that if a commercial fleet of vehicles provides fuel at all integer distances at the free-market price, then one can do better that the given solution: start with $10$ units of fuel, fill up ($1$ unit) at every integral distance from $1$ to $30$, and then use the $10$ units aboard for the remaining $10$ units of distance. The cost is then $ 10+\sum_{i=d}^{30}(\frac54)^d = 10+\frac{(5/4)^{30}-1}{1-4/5} \approx 4043.97 $ units of fuel, say $2022$ jerry-cans. The difference is due to the absence of sub-optimal tours in the commercial model.