3
$\begingroup$

Inspired by this puzzle.

You have many airplanes starting at the same airport. Each plane has a fuel tank that holds just enough fuel to allow the plane to travel $\frac{1}{10}$ the distance around the world. These airplanes possess the special ability to transfer fuel between their tanks in mid-flight: it is possible for multiple airplanes to transfer fuel simultaneously for just one plane, or for one airplane to transfer fuel simultaneously for multiple other planes. We assume an airplane's fuel decreases linearly proportional to the distance traveled.

What's the minimum number of airplanes you need for one of them to make a round the world trip?


Hint

You should be able to achieve the round trip with less than 400 airplanes!

$\endgroup$
6
  • $\begingroup$ Related: A camel transporting bananas, Stranded Nomad Riddle, Travellers across a desert. $\endgroup$
    – justhalf
    Commented Aug 12, 2022 at 5:30
  • 2
    $\begingroup$ I believe this question is almost equivalent to the Stranded Nomad Riddle with n=15.5, the difference is that there is no stranded nomad at the oasis (just need to get there and back), but the strategy would be the same. $\endgroup$
    – justhalf
    Commented Aug 12, 2022 at 5:35
  • 1
    $\begingroup$ do we care about the the airplanes whether any drops or not in the midair cuz of fuel except the one make a round the world trip? or we assume they can land whenever thy want? $\endgroup$
    – Oray
    Commented Aug 12, 2022 at 6:15
  • $\begingroup$ @Oray We don't care, or we assume they can land instantly. $\endgroup$
    – Eric
    Commented Aug 12, 2022 at 6:35
  • $\begingroup$ Ah, ok so that's another difference with the nomad one, where all nomads are required to get back. $\endgroup$
    – justhalf
    Commented Aug 12, 2022 at 11:00

2 Answers 2

5
$\begingroup$

Edit 2: The 189-plane solution assumed that planes could return to base, refuel, and take off again. If this is not allowed, the math gets simpler, to the point that we can get an almost-analytic solution. Let $D(n_0)=\sum_{i=1}^{n_0}\frac{1}{i}$ be the distance a fleet of $n_0$ planes can travel before its last plane runs out of fuel. Also let $R(n_1,n_2,...)$ be the distance from which a plane can be retrieved by a sequence of rendezvous fleets of sizes $n_1, n_2, ...$ To make it around a globe of size 10, we need $D(n_0)+R(n_1,n_2,...)\geq 10$, and the goal of the problem is to find the minimum $N=\sum_i n_i$ that makes that possible.

To retrieve a plane at distance $R$, the $n_1$ fleet must fly out the full distance $R$, and then enough distance back to get them within $R(n_2,n_3,...)$ before running out of fuel. As a recursion relation, $$R(n_1,n_2,...)=D(n_1)-R(n_1,n_2,...)+R(n_2,n_3,...)$$$$\rightarrow R(n_1,n_2,...)=\frac{1}{2}\left(D(n_1)+R(n_2,n_3,...)\right)$$$$\rightarrow R(n_1,n_2,...)=\sum_{i=1}^{imax} \left(\frac{1}{2}\right)^iD(n_i)$$$$\rightarrow D(n_0)+R(n_1,n_2,...)=\sum_{i=0}^{imax} \left(\frac{1}{2}\right)^iD(n_i)$$

If $n_i$ could be continuous, we would maximize this for a given $N$ by equalizing the derivatives with respect to all $n_i$; this results in $n_i=N/2^{i+1}$. Since $n_i$ is discrete, the optimum takes a little more fiddling to find, but we still expect $n_i\approx n_{i-1}/2$. Whether by exactly solving the discrete difference equation or with a little numerical searching, we can get a solution with 328 planes, split into fleet sizes 166, 83, 41, 20, 10, 5, 2, 1.

Edit: Incorporating the tips in the comments, we can do a lot better yet. Compared to my original answer below, we can increase efficiency with two insights:

  1. Even if a given plane isn't going to fly out with a fleet and go until its tank is empty, it is a waste to leave it parked in the base. Instead, it should fly out briefly with the fleet, supply fuel for as long as it can, and then fly home; this gives the fleet a little extra fuel at no extra cost. More precisely, if we have $N_{\textrm{tot}}$ planes and we want $N_1$ of them to fly 'til they drop, the first plane can use $\frac{N_{\textrm{tot}}}{N_{\textrm{tot}}+1}$ fuel to supply the fleet for a distance $\frac{1}{N_{\textrm{tot}}+1}$ before turning back and using its last fuel to get home. The second plane can then use $\frac{N_{\textrm{tot}}-1}{N_{\textrm{tot}}+1}$ to supply the fleet for the same distance, and use $\frac{2}{N_{\textrm{tot}}+1}$ to get all the way home. Conveniently, every plane that flies partway out and returns in this way gives us the same amount of extra distance; all together, the planes that would otherwise stay home can carry the fleet out to $d=\frac{N_{\textrm{tot}}-N_1}{N_{\textrm{tot}}+1}$. This not only directly increases the distance covered for a given $N_1$ and $N_2$, but increases the optimal $N_2$ for a given $N_{\textrm{tot}}$.

  2. We don't have to stick with just one rendezvous fleet. When the rendezvous planes set off to meet the main fleet, some fraction of them can go part of the way, peel off, and fall back to refuel following the above strategy.

Using both these improvements, and taking the time to do a more careful numerical search, I can find a solution with 189 planes. All 189 planes launch together, and 117 of them carry the fleet to $d=0.615$ before returning to base. The remaining 72 planes fly, crashing as they run out of fuel, to $d=5.476$. The 117 planes that returned to base then escort the last plane from the original fleet home, over the course of 10 ever-smaller rendezvous flights; the sequence of fleet sizes at takeoff is [117, 72, 44, 27, 16, 10, 6, 4, 2, 1].

Original Answer: Following the previous answer in this thread, let's say that each plane has a fuel capacity of 1, which is enough for it to travel a distance of 1, meaning the trip around the world covers a distance of 10. Since each plane has the ability to share its fuel with any number of other planes mid-flight, we can keep track of the fuel capacity and consumption of an entire fleet of planes, without worrying about how much fuel any individual plane has in its tank.

A fleet of $N$ planes has a total fuel capacity of $N$, and uses $N$ fuel per unit distance traveled. To minimize fuel consumption, the size of the fleet should always be big enough to hold all the available fuel, but no bigger. One way to accomplish this is to have, at any given time, a single plane using its fuel-sharing magic to power the entire fleet; once that plane is out of fuel, it crash-lands and another takes its place. Using this strategy, an $N$-plane fully-fueled fleet (FFF) can cover a distance of $\frac{1}{N}$ before one plane crashes and it becomes an $(N-1)$-plane FFF. Generalizing to multiple steps, the minimum fleet size $N(d)$ that can cover a distance $d$ is $$N(d)=\textrm{minimum }N\textrm{ such that }\sum_{i=1}^N\frac{1}{i}\geq d$$

If all the planes had to circle the globe one-way, our best solution would be $N(10)=12367$. But we can do better by starting off with one fleet big enough to get most of the way around the world, then sending a second fleet to meet it from the other direction. If the fleets meet up at some distance $d_m$, we have two requirements: the initial fleet size must be big enough to cover $d_m$, and the second fleet size must be big enough to cover the remaining distance $10-d_m$ as a round trip. Summing these to get the total number of planes: $$N_{\textrm{total}}=N(d_m) + N\big(2(10-d_m)\big)$$

I don't know of a good way to solve these inequalities analytically, but with some numerical trial and error, I found a solution with 840 planes total. We send out 514 planes, which fly until one plane with a nearly empty fuel tank reaches the rendezvous point at $d\approx6.82$.Another fleet comes from the other direction with 326 planes, 13 of which reach the rendezvous point. The remaining 13 planes can barely make it the rest of the way to $d=10$.

$\endgroup$
11
  • $\begingroup$ Very nice! I had the same idea, but spent a lot of time writing a program to find the optimum (looping over the number of planes remaining at the rendezvous point). I get 12 planes at the rendezvous point, which means 555 planes going in one direction, 278 planes going in the other direction, meeting point at d = 6.896789, and a total of 833 planes. $\endgroup$
    – wimi
    Commented Aug 12, 2022 at 22:00
  • $\begingroup$ Nice idea. I think the formula should be $$N(d_m) + N(2(9-d_m))$$, since the lone plane can walk alone for distance 1 before meeting the other group (where they will fully refuel that lone plane upon rendezvous) $\endgroup$
    – justhalf
    Commented Aug 13, 2022 at 6:03
  • $\begingroup$ @justhalf I believe this scheme can still be improved upon. Does the stranded nomad riddle suggest a better strategy? $\endgroup$
    – Eric
    Commented Aug 13, 2022 at 6:08
  • $\begingroup$ One requirement in the nomad one is that all should be back at base safely, which is not the case here. And apparently this changes the best strategy, I believe. $\endgroup$
    – justhalf
    Commented Aug 13, 2022 at 6:10
  • $\begingroup$ As for this strategy itself, I currently can't think of any better strategy, since we want each flying plane to be out of commission as soon as possible (except the lead plane), and having one plane refueling the other planes would be the most optimal one to reduce the flying cost. $\endgroup$
    – justhalf
    Commented Aug 13, 2022 at 6:13
2
$\begingroup$

Let us assume that the distance is 10 and fuel capacity is to travel 1. In this scenario we all know that it should be refueled at 2,3 and so on up to 9.

But the problem here is we can't carry fuel to 1 if we carry the remaining fuel would be 0. SO the most optimal path here is to fill at 1/2.

Then the fuel on first plane would become 1 at 1/2 so first plane would be able to travel 3/2 but it should be refueled at 1 and next at 3/2 that means we should provide refuel at every 1/2 distance .

We can write a recursive equation to find number of fueled Aeroplanes required to travel from 0-->3/2.

  • f(1/2)=1 (One plane will send 1/2 of its fuel at 1/2 to another plane)

  • f(1) = 2f(1/2)+1 (One plane to send fuel at 1/2 and 2 planes to send fuel at 1 so total 3)

  • f(3/2)= 2f(1) + 1 ( 3 planes to send fuel at 1 and another 4 planes to send the fuel at 3/2)

and so on. When we solve this equation for simplicity let me assume that f(0)=1 (0-->1/2 first fuel drop). f(1)=2f(0)+1
f(2)=2f(1)+1.

so f(n)=2^n-1;

n=19 we need to refuel till 19/2

so the answer is 2^19-1 +1( The actual plane which is traveling) = 2^19.

This is the approach if the navigation is linear since the navigation is circular or cir-cum after the person crosses 5 it is better to supply fuel from opposite side .

That is up to n=10 we will supply from one side i.e no of planes required are 2^10-1 .

If we count from opposite side we should start supplying at 10 (because the fuel at n=10 is 1/2 tank we need to go to 10 to fill the other half tank )i.e n=20-10 =10 from other side . That means total planes needed = 2^10+2^10-2=2^11-2+1=2^11-1.

$\endgroup$
2
  • 1
    $\begingroup$ Almost. But note that since this is circumnavigation (travel around the globe), you can take a shorter route for refuel after travelling half way (5 distance in your answer), since your refuel planes can travel the other way, reducing the number of planes needed. $\endgroup$
    – justhalf
    Commented Aug 12, 2022 at 11:00
  • $\begingroup$ That is true I assumed linear navigation I will edit it $\endgroup$ Commented Aug 12, 2022 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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