After the driver lamented the thought of walking all the way to the station and back, the passenger replied,

"Actually, you can shorten the walking distance if you drive the car once you've refueled it—just have one person walk to get the gas, then have the second person meet them halfway. While the first person waits at the halfway point, the second person can go refuel the car. When the car is refueled, the second person can pick up the first person. Overall, no one has to walk more than 3/2 km."

To which the driver responded,

"Here's a slightly better solution: have the first person walk to the gas station and one third of the way back. The second person meets the first person there, walks back to refuel the car, and picks up the first person on the way out. Overall, they each walk exactly 4/3 of the way there. I wonder if we can do better?"

In general, we're looking for a solution that looks like this: the first person walks to the gas station, then walks some amount of the way back. The second person walks to where the first person stops, then walks some amount of the way back. This continues until some final person walks all the way back to the car and picks everyone up.

Now we observe the following tradeoff principle: suppose everyone agrees on a solution strategy. While following the strategy, someone chooses to walk a little bit further than required. This alteration will not affect anyone who has already completed their part of the solution. However, everyone afterwards will walk a little bit less.

From this principle, we arrive at a surprising egalitarian principle: in the optimal solution, everyone must walk the same distance (!). To see that this is true, observe that:

1. The only way to allow someone to walk a little less is for someone else to walk a little more.
2. When everyone walks the same amount \(d\), then obviously the person who walks the most walks the amount \(d\).
3. If you alter the egalitarian solution so that someone walks less than \(d\), someone else must walk more than \(d\). Therefore the person who walks the most must walk more than \(d\), and so the altered solution is worse than the egalitarian solution.
4. Therefore the egalitarian solution is optimal.

Now we apply a second trick— the self-similarity principle: Suppose that there are \(n\) people in the car and the canister is at the gas station 1 km away. If one person goes to the gas station and brings the gas canister back \(x\) units, then effectively you have a new problem with \(n-1\) people in the car and the "gas station" / canister effectively \((1-x)\) km away (because that's where the first person brought the gas canister.)

Hence let \(f(n)\) denote "the distance the first person should walk back from the gas station in the optimal solution for \(n\) people."

Obviously we have the base case: \(f(1) = 1\), because if there's only one person in the car, that person should walk all the way back. And by the self-similarity principles, we know that if \(n\geq 2\), then the distance walked by the first two people is:

$$d_1 = 1 + f(n)$$

and

$$d_2 = [1 + f(n-1)] \cdot (1 - d_1)$$

To understand the second equation, note that \([1 + f(n-1)]\) is the optimal distance someone should walk back if there are \(n-1\) people in the car and the gas station is 1 km away. We scale this distance by \((1-d_1)\) to account for the fact that the canister is located \((1-d_1)\), not 1 km, away.

By the egalitarian principle, these two distances are equal. Hence we have:

\begin{align*} 1 + f(n) &= [ 1 + f(n-1) ] \cdot [1-f(n)]\\ 1 + f(n) &= 1 + f(n-1) - f(n) - f(n-1) f(n) \\ 0 &= f(n-1) - f(n-1)f(n) - 2 f(n) \\ 0 &= - f(n) [ f(n-1) + 2 ] + f(n-1) \\ f(n) &= \frac{f(n-1)}{f(n-1) + 2}\\ \end{align*}

We have reduced the problem to a recurrence relation: solve for \(f(n)\), given the recursive definition

$$f(1) = 1, \qquad f(n+1) = \frac{f(n)}{f(n)+2}.$$

In general, we find that the solution is given by:

$$f(n) = \frac{1}{2^{n}-1},$$

so that \(f(1) = 1\), \(f(2) = \frac{1}{3}\), \(f(3) = \frac{1}{7}\), \(f(4) = \frac{1}{15}\), etc.

If you want to find the solution that minimizes the total or average amount of walking, the solution is brutally simple: have one person walk there and back.

Indeed, that person will walk 2 km, the absolute minimum distance it is possible to walk when retrieving a gas canister from a station that is 1 km away.

If you want minimize the amount of time it takes to retrieve the gas from the gas station, the solution is similarly simple: have everyone leave the car at the same time, stopping at their designated spots along the way to the gas station. The first person will reach the gas station, and walk back to where the second person has been waiting, etc.

Overall, with some simplifying assumptions, this takes essentially the same amount of time as having one person walk 2 km there and back, which is the absolute minimum.