Trip around the Earth

You are standing at an airport (that lies somewhere) on equator (of the earth) and have an unlimited number of identical aircrafts (same model, make and fuel capacity etc.) to make a complete trip of equator. Each of the aircraft has the fuel capacity to fly exactly 1/3 (one-third) around the earth along equator. Any flying plane can transfer fuel to any other plane in air instantaneously (without spillage) but after transfer, it should have left with sufficient fuel to come back to the airport (or get refuel again by someone else to eventually come to airport). In any case no plane should get crashed due to fuel outage.

Q(1). What is the minimum number of aircraft necessary to get one plane all the way around the equator assuming that all of the aircraft must return safely to the airport? Assume no other airport is available and unlimited supply of fuel is available (at the airport).

Q(2). What is the minimum number of aircraft necessary for a straight line to reach one of them from start to end point (assuming airport at the start point) and the fuel capacity is 1/3 (one-third) of the straight line (and other conditioned are same as that of Q1).

I can solve it using head and trial but I am looking for a mathematically way to derive the solution.

There is a symmetric solution with 11 aircrafts. If you manage to carry a plane with 5 assisting planes up to one third of the equator and leave it with its tank full, then let it fly through the middle third, and redo the same strategy in reverse with 5 other assisting planes, you get a solution.

Solving this kind of problem is hard, because you constantly have to maintain a delicate balance between how much you can support the aircraft while still being able to save the assisting aircrafts who in turn will need support that will have to be saved etc.

I kinda brute-forced over strategies running with time intervals of 1/6 to find this one (my first try needed a humble 20 aircrafts)

Here, I show how, with 6 aircrafts (flying at one unit of distance per unit of time and unit of fuel, where each aircraft has tank that can contain up to 6 units of fuel), you can send one of them to a distance of 12 units while still not crashing the other five. A pair $(p,f)$ denotes the number of planes $p$ with their combined fuel $f$ at that time and place. I don't detail explicitly how the fuel is distributed but you can infer it from the table easily.

$$\begin{array}c & d=0 & d=1 & d=2 & d=3 & d=4 & d=5 & d=6 & d=7\\ t=0 & (6,36) \\ t=1& & (6,30) \\ t=2 & (1,6) & & (5,24) \\ t=3 & & (2,5) & & (4,19) \\ t=4 & (2,12) & & (1,1) & & (3,14) \\ t=5 & & (3,10) & & (1,1) & & (2,10) \\ t=6 & (2,12) & & (2,5) & & & & (2,8) \\ t=7 & & (3,10) & & (1,3) & & (1,1) & & (1,5) \\ t=8 & (2,12) & & (1,5) & & (2,2)\\ t=9 & & (2,10) & & (3,4)\\ t=10 & (1,6) & & (4,6) \\ t=11 & & (5,7) \\ t=12 & (5,30) \\ \end{array} $$

Starting the solution in reverse at t=6 allows you to catch the aircraft when it reaches d=12 at time t=12, and finally to bring it at d=18 = 3 times the distance an aircraft can fly by itself.

Seeing as there is some fuel to spare sometimes and as I have almost solutions to doing the trip with 4+4+1 planes, I wouldn't be too surprised if there is a solution with only 10 aircrafts (and maybe 9).

It would be nice to know, for each $n$, the greatest distance you can possibly reach with $n$ aircrafts. Theoretically, you could do an A* search algorithm with hyperpolyedra in a phase space of dimension $2n$ to explore everything and obtain the solution after a horrifyingly long computation.

You could also write particular flight routes, deciding which aircraft meets which aircraft where and in what order, then leave unknowns for all the distances and the fuel exchanged at each meeting point, and try to solve the horrifying system of linear inequalities you obtain and get the best distance with that particular flight route. Looking at the near solutions one can brute force with 5 aircrafts, this might be doable to find the best distance for $n=5$.

Very interesting puzzle. Even though I have not fully solved it, I have found some patterns and bounds.

I will address Q1 (the equator problem). Q2 does not make sense to me the way it is phrased, but once clarified I suspect that some of my analysis probably applies there too.

Intuition tells us that the optimal solution will probably involve leaving the full-trip-airplane (let's call it 'target plane') with it's tank full at $1/3$ of the trip, let it complete the other $1/3$ on its own and then refuel it again for the last $1/3$. This is by no means proven but intuition guides us to fly the refuelling planes as little as possible, meaning as close to the airport as possible. I notice that all other solutions discussed here also work in this framework. Even though this remains to be proven, I will take it as a given and I will attempt these two subproblems:

• What is the minimum number of planes needed to leave one plane with full tank at $1/3$ of the equator?
• What is the minimum number of planes needed to bring back an empty-tank airplane from $1/3$ of the equator?

In our problem, fuel and distance are two faces of the same unit/quantity. Let's assume that a fuel tank can hold 1 unit of fuel, which in turn can keep us flying for 1 unit of distance. Hence the equator is $3$ units of distance long.

Let's look at the first subproblem. We will obviously need support planes to leave the target plane with its tank full at distance 1. Let's see what happens when we get $1$ support plane up in the air. We want to transfer as much fuel as possible and return the extra plane back. We can see that the extra plane can travel $1/3$ distance transfer $1/3$ fuel to the other plane making its tank full, and get back landing with an empty tank. How about if we have $n$ planes i.e., $(n-1)$ support planes? We want one of the planes to transfer as much fuel to all the rest, and get back landing with an empty tank. Let's name this distance $d$ and the fuel transferred $f$. The distance traveled, plus the fuel given, plus the distance travelled back should sum up to $1$. Moreover, the fuel given is upper bounded by the fuel spend by the rest of the nodes travelling distance $d$. These observations give us this $2\times2$ equation system that we can solve to obtain $d$ and $f$:

$$\left. \begin{array}{rl} 2d + f & = 1 \\ f & = (n-1)\times d \end{array} \right\} \iff \begin{array}{rl} d &= \frac{1}{n+1} \\ f & = \frac{n-1}{n+1} \end{array} $$

Let's see what values we get for $d$ and $f$ for the first few values of $n$. Let's also compute the sum of $d$ from $n=2$ to $n=i$. Why would we do this? Imagine that we start with i planes. We can travel a distance $d_i$ till one airplane goes back, leaving the others full. The remaining $i-1$ planes can travel $d_{i-1}$ until another plane goes back leaving the rest full. And so on, until the last two planes cover $d_2$ and then the target plane is left full to continue the trip on its own. If the sum of these distances is 1 or larger then we know that we can leave our target plane full at distance 1 (or larger).

$$ \begin{array}{c|ccc} n & 2 & 3 & 4 & 5 & 6 \\ \hline d & \frac{1}{3} & \frac{1}{4}& \frac{1}{5}& \frac{1}{6}& \frac{1}{7} \\ f & \frac{1}{3} & \frac{2}{4}& \frac{3}{5}& \frac{4}{6}& \frac{5}{7} \\ \sum_2^n d & \frac{1}{3} & \frac{7}{12}& \frac{47}{60}& \frac{19}{20}& \frac{153}{140} \end{array} $$

Notice however that with this method all support planes apart from the first that goes back, do not have enough fuel to get back to the airport. They only have enough fuel to go back to the point the previous support plane left them full. So we will need extra support planes, taking off after the first group, to help all support planes to get back.

What if we adjust our formulas to take into account the extra distance traveled? Can we get a group of planes all taking off together, leaving the target plane full at distance 1 and all getting back without extra support? The answer is no. Think about it this way. To leave the target plane full at distance 1, we need to have at least one plane there with non-empty tank. Otherwise, the target plane would have traveled a distance $\epsilon$ alone before reaching distance 1, and thus its fuel tank would have at most $1- \epsilon$ fuel. So there needs to be a support plane at distance 1. If we now put the extra restriction that this support plane has to make it back on its own, it means that it needs its tank full. Which means we have the same situation again! In other words, it will need another support plane there, which in turn will have to be full to get back and so on. This reasoning tells us that extra support planes that take off after the first group, are necessary. This further prompt us to think that in our initial formulation we do not need to restrict a support plane travelling the same distance back on its own fuel. A support plane can fly forward $d_{f}$ and then fly backwards for $d_{b}$. Also let's denote the fuel transferred as $V$ (not 'f' this time to avoid confusion with 'forward'). And let's have the extra restriction that the support plane that takes off afterwards (to bring back the returning support plane) also spends all its fuel. Here's the new set of 3 equations:

$$\left. \begin{array}{rl} d_f + d_b + V & = 1 \\ V & = (n-1)\times d_f \\ 3(d_f - d_b) &= 1 \end{array} \right\} \iff \begin{array}{rl} d_f &= \frac{4}{3n+3} \\ d_b &= \frac{-n+3}{3n+3} \\ V & = \frac{4n-4}{3n+3)} \end{array} $$

To help the discussion let's call the first group of support planes "$t_0$ planes" and let's call support planes that take off afterwards "$t_1$ planes". The first two equations are about $t_0$ planes. The third one is about the $t_1$ plane, refuelling the $t_0$ support plane getting back. It's interesting to note that $d_b$ is negative for $n>3$. This just means that for $n>3$ the distance travelled cannot be large enough so that the $t_1$ plane spends all its fuel. Remember though that this is for the case of $n$ planes taking off and one returning. It does not tell us what happens afterwards with the rest of the support planes. The general case would be each of the $n-1$ planes deciding on the amount of fuel to keep to go back (or equivalently the distance to go back), while the target plane reaches distance 1 with full tank. We would need to figure out how many $t_1$ planes we need for each different set of chosen $d_b$, and try to minimise the total number of planes used. This seems quite daunting, so let's ask a simpler question:

What is the minimum number of $t_0$ planes? In other words, what if each support plane in $t_0$ decided to go back a small amount $\epsilon>0$? (if $\epsilon =0$ this means the plane supporting the returning plane is right there when the decision to return is taken, so it is really a $t_0$ plane, and remember we proved that we need $t_1$ planes). Let's figure it out starting from the end. At distance 1 we have two planes: the target one and the last support one. The target plane must have 1 tank full, and has spend another full tank to get there. The last support plane has spent 1 fuel tank to get there, and will spend another $\epsilon$ to get a small distance back. This means that we need more than 3 tanks of fuel to achieve this position which means that we need more than 3 $t_0$ planes to carry that fuel. Let's name the target plane $p_0$, name the last support $t_0$ plane $p_1^0$, the second last $t_0$ support plane $p_2^0$,... $p_i^0$ the $i^{th}$ last $t_0$ support plane. We know we need at least 4 planes (i.e. $p_0, p_1^0, p_2^0, p_3^0$) and we know that $p_1^0$ needs to travel distance $1 + \epsilon$ before a $t_1$ plane supports it, but how long do $p_2^0$ and $p_3^0$ need to travel. Maybe their distances push the total fuel past 4 tanks, so we need to involve another $t_0$ plane (and redo the calculations for it to see if we need yet more). To answer that question we need to answer this one: How long can $n$ planes go together, starting full, and ending with $n-1$ being full? This translates to the equation $n = n-1 +n\times d \iff d = \frac{1}{n}$. So working our problem backwards: planes $p_0$ and $p_1^0$ can go on their own for $1/2$ distance, until the reach point 1 (i.e., distance from origin =1). Which means that plane $p_2^0$ has to follow them for distance $(1-1/2)=1/2$. Going another step backwards, the formula tells us that the 3 planes $p_0$, $p_1^0$, $p_2^0$ can travel for $1/3$ distance together until they reach point 1/2 (i.e., distance from origin =1/2). This means that plane $p_3^0$ has to follow them for distance $(1-1/2-1/3) = 1/6$. So now let's look again at the fuel needed, having this new information on the minimum distance each plane needs to travel.

• plane $p_0$ needs $1 + 1$ fuel
• plane $p_1^0$ needs $1 + \epsilon$ fuel
• plane $p_2^0$ needs $1/2 + \epsilon$ fuel
• plane $p_3^0$ needs $1/6 + \epsilon$ fuel

Since $\epsilon$ can be arbitrarily close to 0, we can show that the sum of fuel needed by the minimum number of $t_0$ airplanes is more than 3 and less than 4. Hence the minimum number of $t_0$ planes is 4. Of course we also have $t_1$ planes to account for. And intuition tells us that the smaller the amount $\epsilon$ the $t_0$ planes go back, the more $t_1$ planes we will need. Let's explore cases where $n=6,5,4$.

Let $n=6$, and apply the our first formulas as to when a plane goes back and how much fuel it gives. So $p_5^0$ goes back at $1/7$ and gives $5/7$ of its fuel to the 5 remaining nodes. Then after an additional $1/6$ distance, $p_4^0$ goes back giving $4/6$ of its fuel to the remaining 4 nodes, and so on. $p_5^0$ can get back on its own fuel, but all the rest have a deficit. How much of a deficit?

• $p_5^0$ needs $0$ fuel
• $p_4^0$ needs $1/7$ fuel
• $p_3^0$ needs $1/7 + 1/6$ fuel
• $p_2^0$ needs $1/7 +1/6 +1/5 = 107/210$ fuel
• $p_1^0$ needs x fuel ($x < $1/7 +1/6 +1/5 + 1/4$ $)

Let's find $x$. $1/7 +1/6 +1/5 + 1/4 + 1/3 = 153/140$ so we are overshooting 1 by $13/140$. This means that plane $p_1^0$ will have $1/3 + 26/140$ fuel when leaving the target plane full at distance 1. Thus it needs $1-(1/3 + 26/140) = 101/210$ more fuel to get to the origin. The aggregate fuel deficit is close to 1.5. This means we need at least 2 $t_1$ planes. Noticing how, in our specific scenario, $p_1^0$ and $p_2^0$ will need fuel close to the middle suggests that we will need even more planes (1-2 at least) and most probably a different distribution of the fuel to be more efficient. I have looked into case $n=5$ where similar problems arise. I have to revisit the problem later. At least some progress with bounds was made.

I will stop here and post the answer without going to the second subproblem (getting the target plane empty at distance 1 from the origin). I have done some work on it and I will edit my answer soon. The only thing I want to point out is that the problem is not symmetrical to the first one. We do not need to get a plane with a full tank at distance 1, so we can transfer it to the target plane. We can save it with less fuel, as long as other planes (travelling for less distance) provide the extra fuel.

For Q(1), I believe I have discovered a solution using only 8 airplanes. I will post that at a later date. For now, here is a simpler solution using 9 airplanes. Capacity of the fuel tank is 4, so a complete trip around the world is 12 units. Numbers in green shows the amount of fuel that has reached that node. Numbers in red show the number of airplanes travelling between nodes. Note the two planes that sit idle and unused at the airport for parts of the journey, suggesting 9 planes is not the best solution. I labelled node A since it is a bit tricky: The 1 plane leaving that node travelling east is only carrying 3 units of fuel, not the expected full tank. Similarly, for node B, the one returning plane entering the node arrives with 1 unit of fuel left, not the expected empty tank.

Q(1) solution using only 8 planes. Here, the capacity of a fuel tank is 36, so a full circumnavigation is 108. Red indicates number of airplanes on each segment. Blue is the length of each segment. Available fuel at each node is left as an exercise for the reader. Node A is a special case: The inbound plane entering node A still has 6 fuel left. He transfer 3 fuel to the outbound plane entering the node so that it again has a full tank, and keeps 3 fuel for the return to the airport. Node B does the opposite: The outbound plane transfers 3 fuel to the inbound plane, which gives it just enough fuel to make the next node and get rescued by another outbound plane.