9
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ How did you find $d(2) = 3/5$? $\endgroup$ – Fimpellizieri Aug 5 '18 at 17:12
  • 1
    $\begingroup$ @Fimpellizieri: The two planes can travel 1/5 of the way together, and then the first can completely refuel the second and still return safely. The full tank allows the second plane to reach 4/5 of the way, where the second plane can meet it (traveling the other way around the world, but stopping for a refuel on the way). At that point, the second plane can share enough fuel to get both planes home. They will be both be empty when they return. $\endgroup$ – Jared Aug 5 '18 at 17:57
  • $\begingroup$ So the same plane can be used twice (one way and the other), is that so? $\endgroup$ – Fimpellizieri Aug 5 '18 at 19:44
  • $\begingroup$ @Fimpellizieri: I guess the way I interpret the riddle, the answer is yes. I think this makes the riddle harder, because you have to keep track of when the returning planes arrive at the airport and are able to be sent out again in the other way. If you want to interpret the riddle to mean that planes can only be used once, then I think the solution is a little easier, but still an interesting problem. $\endgroup$ – Jared Aug 5 '18 at 20:26
  • $\begingroup$ @Jared as you said that the planes can refuel, then is the answer below correct? $\endgroup$ – user572932 Aug 5 '18 at 21:25
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is a really nice approach, and again, I'm very intrigued by how the solution changes when allowing for planes to travel arbitrarily fast supposing they have enough fuel. I'll make note of my assumptions in the question. Thanks. $\endgroup$ – Jared Aug 7 '18 at 2:25
2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Is it clear that your previous answer applies (considering questions of timing)? It's okay if a car runs out of fuel in the desert and waits for a rescue car with additional fuel, but the same cannot be said of a plane. $\endgroup$ – Fimpellizieri Aug 7 '18 at 4:36
  • $\begingroup$ You are correct that some of the cars in the previous question sit and wait for others to come back. Here I have assumed the planes can land and wait. $\endgroup$ – Ross Millikan Aug 7 '18 at 5:19
  • $\begingroup$ Not sure I understand your answer. Are you assuming that planes can land and wait anywhere along the equator? According to comment by the OP, planes may only land at that one airport on the equator. $\endgroup$ – Jens Aug 9 '18 at 23:33
1
$\begingroup$

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

enter image description here

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.

$\endgroup$
2
  • $\begingroup$ This is great. Yes, I realized that I was a bit premature in conjecturing the lower bound for $d(n)$. I now agree that for any $\epsilon >0$, there is an $n$ such that $d(n)<\epsilon$. I think the general idea is that, given enough planes, one can effectively construct a floating airport a positive distance away from the grounded airport by sending enough planes back and forth (as you've done here). Iterating this process gets us arbitrarily far. $\endgroup$ – Jared Aug 10 '18 at 2:43
  • $\begingroup$ Glad to help. Regarding your main question, it is difficult to see a general strategy for finding $d(n)$. For $d(2)$ and $d(3)$ the same strategy is used, i.e. send all planes off together, let single planes refuel the others and send the single planes unassisted back to the airport, where they take off individually to assist returning planes. It is not hard to work out that this strategy gives $d(n) = \frac{n+1}{3n-1}$. But this strategy is clearly only optimal for small $n$. $\endgroup$ – Jens Aug 10 '18 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.