Getting an airplane around the world

Question

I'm interested in a generalization to the following riddle:

You're the director at an airport on the equator, and each plane at your airport can hold enough fuel to fly half way around the world. Your planes can also meet up in midair to share fuel. Your task is to use as few planes as possible to successfully fly one plane around the world, but all planes that you use must safely land back at your airport. How many planes do you need?

The answer to the riddle is $3$ (you can try to figure this out, or do a quick search of the internet for a solution).

Here is my formulation of a generalization, which I have yet to solve and would love for the community here to think about.

Let $n$ be the number of planes at your airport. What is the minimum distance $d(n)$ each plane can fly on a full tank (measured as a proportion of the whole distance around the world) to ensure that it is possible to successfully fly one plane around the world with all planes landing safely at your airport?

Here is what I think I know so far. If $n=1$, we need the only plane to be able to fly all the way around the world, so $d(1)=1$. If I haven't made any mistakes, then I believe that $d(2)=\frac{3}{5}$. I also believe that $d(3)=\frac{1}{2}$, or in other words, the original riddle is "sharp" in some sense. I don't know $d(n)$ for $n\ge 4$, but I have reason to believe that

$$\lim_{n\to\infty}d(n)=\frac{1}{4}$$

so that if our planes can travel one fourth of the way around the world (or less) on a full tank, then we have no hope of flying one around the world no matter how many planes we have.

I intentionally leave out justification for this information about $d(n)$, because I don't want to pollute someone else's thinking, and I'd love independent confirmation.

For a further challenge, one could also define $f(D,n)$ to be the maximum total amount of fuel "left over" among $n$ planes that can travel a distance $D$ on a full tank upon successfully flying one plane around the world. Intuition might suggest that $f(d(n),n)=0$ (i.e. if we have any left-over fuel at the end of the flights, then our planes must be able to fly a longer distance than necessary), but I don't think this is true. In fact, I think that $f(\frac{1}{2},3)=\frac{1}{4}$, that is, there is a solution to the original riddle in which the planes will be left with enough fuel to still fly one plane one fourth of the way around the world.

I have more to say, but I'll end here because the question is already quite lengthy. Perhaps in a few days after giving the community time to think, and if my results haven't been verified (or proven incorrect), I'll post my justification.

---

Addition: As pointed out by Fimpellizieri below, I should state that I'm assuming planes all travel at the same constant speed at all times. The end of his answer provides a better solution to the case $n=3$ if we don't make these assumptions and rid ourselves of time constraints. This time-free problem is also very interesting to me.

Also, I'd like to note that this question (of which I was unaware when I originally posted) and its answers are relevant. In particular, Brian Trial's answers claim that $d(8)\le \frac{1}{3}$ and provide a great way to visualize the planes' trips graphically.

Answer 1

This is not quite an answer, but rather musings about the problem. Perhaps someone can find another approach.

For $d = d(3)$, consider the following strategy, separated in two parts.

---

Part ($\mathbf 1$):

• $P_1, P_2$ and $P_3$ will leave the airport in 'clockwise' direction. $P_3$ will be the plane to make the round trip.

• $P_1$ will fly $r$ distance, refund each of the other two planes for $r$ distance, and go back another $r$ distance to the airport.

• $P_2$ will hence have fuel for a total of $d+r$ distance at its disposal. We write $d+r =$ $x+ y + u$, indicating that:

  • $P_2$, along with $P_3$, will fly $x$ distance away from the airport in the clockwise direction.
  • At this point, $P_2$ will donate $y$ fuel to $P_3$.
  • $P_2$ will then fly back $u$ distance, arriving at a distance of $x-u$ from the airport with no fuel.

• $P_3$ will hence have fuel for a total of $d+r+y$ distance at its disposal.

• After refuelling at the airport, $P_1$ will fly the $x-u$ distance towards $P_2$ and refund it for $x-u$ distance. They will both head back to the airport together.

From this, we must have

• $0\leqslant r\leqslant d/4$: $P_1$ can fly $r$ distance forward and backwards, and refund each other plane $r$ distance
• $x\geqslant r$: $P_2$ must fly at least $r$ distance away from the airport
• $0\leqslant y \leqslant x- r$: fuel donated can neither be negative nor exceed $P_3$'s tank's capacity
• $0\leqslant u\leqslant x$: $P_2$ cannot go back some negative distance and cannot go back more than it flew forward
• $2\cdot r + (x-u) \leqslant x+u$: $P_2$ must not run out of fuel before $P_1$ can reach it again
• $x-u \leqslant d/3$: $P_1$ can reach $P_2$, refund it, and the two of them will have enough fuel to head back to the airport

Putting it all together, the conditions we have so far are

$$\left\{\begin{array}{ccccc} d + r &=& x+y+u&&\\ 0&\leqslant &r &\leqslant& d/4 \\ r &\leqslant& x &\leqslant & u + d/3\\ 0&\leqslant &y &\leqslant& x-r\\ 0&\leqslant &u &\leqslant& x\\ r&\leqslant &u \end{array}\right.$$

In this part, we have that

• $P_1$ covers a total of $2\,r+ 2\,(x-u)$ distance.
• $P_2$ covers a total of $2x$ distance.
• $P_3$ covers a total of $d+ r + y$ distance.

---

Part ($\mathbf 2$):

• Planes $P_1$ and $P_2$ will leave the airport in the 'counter-clockwise' direction to meet up and refuel $P_3$.

• $P_1$ will fly $s$ distance, refund $P_2$ for $s$ distance, and go back another $s$ distance to the airport.

• $P_2$ will hence have fuel for a total of $d+s$ distance at its disposal. We write $d+s =$ $\big[1-(d+r+y)\big] + 2z$, indicating that

  • $P_2$ will fly $\big[1-(d+r+y)\big]$ distance away from the airport in the counter-clockwise direction to meet up with $P_3$.
  • At this point, $P_2$ will donate $z$ fuel to $P_3$.
  • $P_2$ and $P_3$ will then both fly back $z$ distance, arriving at a distance of $1-d-r-y-z$ from the airport with no fuel.

• After refuelling at the airport, $P_1$ will fly the distance towards $P_2$ and $P_3$ and refund each of them for that much fuel. All three planes will then head back to the airport together.

From this, we must have

• $0 \leqslant s\leqslant d/3$: $P_1$ can fly $s$ distance forward and backwards, and refund $P_2$ for $s$ distance
• $z\geqslant 0$: cannot donate negative fuel
• $2x + 1-d-r-y \leqslant d+r+y$: $P_3$ must not run out of fuel before $P_2$ can reach it again
• $1-d-r-y - z \leqslant d/4$: $P_1$ can reach $P_2$ and $P_3$, refund them both, and the three of them will have enough fuel to head back to the airport
• $2x + 2s + 1-d-r-y - z\leqslant d+r+y + z$: $P_2$ and $P_3$ must not run out of fuel before $P_1$ can reach them again

Putting these together:

$$\left\{\begin{array}{ccccc} 2d+s+r+y &=& 1 + 2z&&\\ 0&\leqslant& s&\leqslant&d/3\\ z&\geqslant& 0&&\\ x+1/2&\leqslant& d+r+y&&\\ 1 &\leqslant& 5d/4 + r + y + z&&\\ x + s + 1/2&\leqslant &d + r + y + z&& \end{array}\right.$$

---

We could hope that maybe some solution to this with $d<1/2$ could exist, but it appears there is not. Indeed, already if we consider the sub-system

$$\left\{\begin{array}{ccc} 2d+s+r+y &=& 1 + 2z\\ y &\leqslant& x-r\\ x + 1/2 &\leqslant& d + r + y\\ 1 &\leqslant& 5d/4 + r + y + z\\ x + s + 1/2 &\leqslant& d + r + y + z\\ d&<&1/2 \end{array}\right.$$

Wolfram Alpha indicates that no solutions exist. While not a definitive proof, this means that in order for $d(3) < 1/2$, one must use an entirely different strategy.

---

If the planes could slow down or speed up (burning the same fuel per distance), then some inequalities could be discarded (the ones that relate to planes running out of fuel before another one can reach it). We'd get the following system

$$\left\{\begin{array}{ccccc} d + r &=& x+y+u&&\\ 2d+s+r+y &=& 1 + 2z&&\\ \\ 0&\leqslant &r &\leqslant& d/4 \\ 0&\leqslant& s&\leqslant&d/3\\ r &\leqslant& x &\leqslant & u + d/3\\ 0&\leqslant &y &\leqslant& x-r\\ 0&\leqslant &u &\leqslant& x\\ 0&\leqslant& z&&\\ 1 &\leqslant& 5d/4 + r + y + z&& \end{array}\right.$$

You can check that the following is a solution with $d<1/2$:

$$\left\{\begin{array}{ccc} d&=&9/20\\ r&=&9/80\\ x&=&11/40\\ y&=&13/80\\ u&=&1/8\\ s&=&3/20\\ z&=&13/80 \end{array}\right.$$

Answer 2

This is a variant of the Jeep problem in the crossing the desert version. You follow the solution for the crossing the desert solution, the last jeep goes as far as possible, then is met by planes coming around the other way to get it home. If $d$ is the range of a vehicle with a full tank and $D(n)$ is the distance from base that the last vehicle of $n$ can set off with a full tank of fuel, you need $d+2D(n)$ to be the circumference of the world. Presumably because they are aircraft they burn fuel while loitering, so we need $n$ planes to take off to replicate $n$ units of fuel at the base in the standard problem where fuel can be cached.

Using the information from the Wikipedia article, for $d=1$ we can handle a circumference of $2(H_{2n-1}-\frac 12H_{n-1})-1$ for $n$ aircraft where $H_k$ is the $k^{th}$ Harmonic number $H_k=\sum_{i=1}^k\frac 1i\approx \log k+\gamma$.

I did the Jeep problem where the plane has to return in this answer.

Answer 3

I don't see any lower boundary for $d(n)$. For example, here's a solution for $d(n)= \frac{1}{4}$, using Brian Trial's visualization technique (the numbers shown are the number of planes moving in that direction):

Assume each plane has a tank capacity of $3$ fuel units (meaning it would take $12$ fuel units to circle the globe). In the figure above, the distance away from the airport is given in fuel units.

In the figure, a plane moving away from the airport, will always have a full tank at its starting node. A plane moving towards the airport will always have $\frac{1}{3}$ tank.

The principle is the following:

A plane moving away from the airport uses $1$ fuel unit to get from its current node to the next node. When it arrives at the next node, the plane does one of the following:

1. Refuels a returning plane with $1$ fuel unit and heads for the airport with $1$ fuel unit in its tank.
2. Refuels a fellow sister plane (doing the same node movement) with $1$ fuel unit and heads for the airport with $1$ fuel unit in its tank.
3. Is itself refueled with $1$ fuel unit by a sister plane and continues away from the airport with a full tank.

A plane moving towards the airport only does one thing: it is refueled with $1$ fuel unit by a plane arriving from the airport and continues towards the airport.

Looking at the figure, the maximum number of planes in the air at any moment is $172$, so $d(172) \le \frac{1}{4}$.

The above procedure should be applicable to any $d(n)$ as far as I can see.

Let me know if I made a mistake.