Rules of the game

While driving across the country one hot summer day, two of my friends noticed that they were running dangerously low on fuel. The driver pointed this out to the passenger and said:

"Suppose we run out of gas and have to walk down the road until we find the closest gas station. Someone'd have to walk all the way down to get a canister of gas, then walk all the way back!"

They debated whether there was a better solution than this for a while (as I detail below). Eventually, I heard about the conundrum and turned it into the following general puzzle (In any case, their car did not run out of gas, so the problem became purely academic.) :

Suppose a car full of n people runs out of gas. There is a gas station 1 km away. Assuming they must walk to retrieve a canister of gas from the station, find the best cooperative solution. (That is, find the solution which minimizes the distance walked by whoever walks the most.)

Assume that the solution genuinely involves individuals going to retrieve gas; they cannot push the car, carry each other, etc.

Feel free to pause at this time and solve this problem yourself. In the rest of this article, I will detail the complete solution.

The general solution

Discussion

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.

The egalitarian principle

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.

The self-similarity principle

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≥2, then the distance walked by the first two people is:

d1=1+f(n)

and

d2=[1+f(n−1)]⋅(1−d1)

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−d1) to account for the fact that the canister is located (1−d1), not 1 km, away.

By the egalitarian principle, these two distances are equal. Hence we have:1+f(n)1+f(n)00f(n)=[1+f(n−1)]⋅[1−f(n)]=1+f(n−1)−f(n)−f(n−1)f(n)=f(n−1)−f(n−1)f(n)−2f(n)=−f(n)[f(n−1)+2]+f(n−1)=f(n−1)f(n−1)+2

A recurring problem

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

f(1)=1,f(n+1)=f(n)f(n)+2.

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

f(n)=12n−1,

so that f(1)=1, f(2)=13, f(3)=17, f(4)=115, etc.

Other optimizations

Minimize the maximum/average

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.

Minimize the time

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.