N cars travelling the greatest distance

Question

Considering $n$ cars, each can travel 100km with a full tank of fuel.They are travelling along a road. They must all return to the starting point, with one car travelling the furtherest to deliver a letter. What is the maximum distance between the letterbox and the starting point?

I consider this question as this: assume the maximum distance is $X$.

As $n=1,X=50$

$n=2,X=75$

Note for $n=2$:both car drive 25km, then car 1 give 25km of fuel to car 2, car 2 keep driving 50 and back, car 1 give 25km of fuel to car 2 and they both drive back.

...

As $n\rightarrow \infty, X\rightarrow \infty$ since one car can just give fuel to every other car after $0.0000000001m$.

But how can one generalise this in terms of $n$ and $X$?

Any help appreciated.

Answer 1

Your solution for $n=2$ is good and points the way to the general solution. We assume the cars cannot refuel at the starting point. Clearly the last leg is made by one car alone, starting with with a full tank and making a $100$ km round trip, so the leg is $50$ km. As you say, two cars setting off with full tanks can go $25$ km and transfer fuel to one to do the final stage, then get home. Now if we have three cars, we want them to drive a distance $d$, fill two cars that do the $75$ km thing, then return home. We have three cars making the round trip of $d$ plus the $200$ km for the last two stages. We have $6d+200=300, d=\frac {100}6$, using $300$ of fuel. Add a fourth car to the mix and they make eight round trips of $d'$ plus the $300$ of fuel for the last three stages, so $8d'+300=400, d'=\frac {100}8$

Car number $k$ adds $\frac {100}{2k}$ to the distance covered, so the total distance for $n$ cars is $\sum_{i=1}^n\frac {50}i$, which is $50$ times the $n^{th}$ Harmonic number, or about $50(\ln n+\gamma)$

We need to convince ourselves that it is more efficient to just add one to the fleet at each stage than have (say) three cars go together to refuel the last one and have nine go together to refuel those three. The intuitive approach is to note that fuel far from the start of the road is precious so we want as few cars as possible driving out there.

Answer 2

For convenience of notation, we can scale the problem by a factor of ${\large{\frac{1}{100}}}$ so that a car can go a distance of at most $1$ on a full tank. At the end, we can multiply by $100$ to undo the initial scaling.

With the scaled version, let $f(n)$ be the maximum achievable distance, given $n$ cars.

Partial result: $$\;f(n) \ge \sum_{k=1}^n \frac{1}{2k}$$ Proof:

Proceed by induction on $n$.

Clearly we have $f(1)={\large{\frac{1}{2}}}$, so the claim holds for the base case, $n=1$.

Suppose the claim holds for some positive integer $n$.

Consider the case of $n+1$ cars.

At a distance ${\large{\frac{1}{2(n+1)}}}$ from the starting point, let car $n+1$ refuel all the other cars to full capacity, and wait for their return.

By the inductive hypothesis, one of the cars $1,...,n$ can achieve a distance of $f(n)$ from the point where car $n+1$ waits, with the all cars returning to that point.

On their return, car $n+1$ has exactly enough fuel to get all $n+1$ cars back to the starting point.

Thus, we have $$ f(n+1) \ge \frac{1}{2(n+1)}+f(n) \ge \frac{1}{2(n+1)}+\sum_{k=1}^n \frac{1}{2k} = \sum_{k=1}^{n+1}\frac{1}{2k} $$ which completes the induction.

Undoing the initial scaling, it follows that for $n$ cars, a distance $$X=50\sum_{k=1}^n \frac{1}{k}$$ is achievable. I don't know whether or not it's the maximum possible value of $X$.