#+TITLE: A roadside refueling relay
# "There and back again"
#+AUTHOR: Dylan Holmes
#+SETUPFILE: ../../logical/org/template-export-setup-2.org
#+OPTIONS: toc:nil title:nil
#+INCLUDE: ../../logical/org/template-include.org
#+LATEX_HEADER: \usepackage{listings}
# 2016/09/02
#+TOC: headlines 2

* Rules of the game

# ** A conundrum
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:

#+BEGIN_QUOTE
"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!"
#+END_QUOTE

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.) :

#+BEGIN_QUOTE
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.
#+END_QUOTE

# requires the least walking

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,
#+BEGIN_QUOTE
"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."
#+END_QUOTE

To which the driver responded,
#+BEGIN_QUOTE
"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?"
#+END_QUOTE


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 egalitarian principle allows us to solve for the solution
# directly.

** 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\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*}

** A recurring problem
# The other passengers
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.

** COMMENT There and back again

But of course $f$ is only a component of our overall solution. We
recall that $f$ is the distance that the first person should walk back
if the car has $n$ people in it. By the egalitarian principle, we also
know that everyone will walk $1+f(n)$ distance overall. But we have
not yet determined specifically how far each person will walk from the
car, and how far each person will walk back.

Letting $d_1$, $d_2$, $d_3, \ldots$ denote the distance each person
will have to walk back, we have that:

\begin{align}
d_1 &= f(n) &= \frac{1}{1-2^{-n}}\\
d_2 &= f(n-1) [1-d_1] & \\
d_3 &= f(n-2) [1 - d_1 - d_2] &\\
\end{align}




# We have not yet determined how far
# the other occupants of the car should walk.




* 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.

# Have one person walk there and back.

** 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.

** COMMENT