Around the world

[DanishDynamite]

On a small island there is an airbase. The airbase only has planes of a single type. These planes can all travel exactly half-way around the world on a full tank before they run dry. They do, however, have the ability to refuel similar planes with any part of their own fuel from their tanks.

The base commander has just been asked to send one of his planes completely around the world, taking off and landing at his base.

Is this even possible? If so, what is the minimum number of planes required to do this? And what is the minimum amount of fuel required?

(Any plane taking off must return and land safely at the base. Assume that any change of direction or refueling activity happens in an instant.)

[KaiYeves]

Two can't meet in the middle as each would be out of fuel. Then we have a crash.

[3dknight]

I think you might have a better time researching it yourself? Its jst an opinion

[DanishDynamite]

Two can't meet in the middle as each would be out of fuel. Then we have a crash.
Correct. But imagine two planes taking off at the same time. When they've both traveled 1/8 around the world, they have both used 1/4 of their fuel. One plane could then transfer 1/4 a tank of fuel to the other, leaving it with 1/2 tank, more than enough to return safely to the base. The other plane would now have a full tank, despite having already flown 1/8 around the world.

[DanishDynamite]

I think you might have a better time researching it yourself? Its jst an opinion
Uhh, I already know the answer.

[KaiYeves]

I thought they had to directly meet to transfer fuel.

[DanishDynamite]

I thought they had to directly meet to transfer fuel.
Correct.

[DanishDynamite]

Come now, guys! Flex your mathematical and creative muscles a bit here!

As a small morsel to get you going, let me tell you that the answer, in regard to minimum planes and miminum fuel expended, is quite beautiful mathematics-wise. :)

[Roy Batty]

Are these African or European planes?

...Oops sorry, wrong thread. I'll get me coat :D

[KaiYeves]

I keep thinking of the island as being near Iceland for some wierd reason. Does the answer in any way involve cutting across the polar regions?

[DanishDynamite]

The island is just some imaginary tiny island somewhere. For the purposes of this puzzle the rest of the planet could consist of ocean and nothing more.

I've already given a hint earlier on how the base commander must go about complying with the order he has been given.

This is not rocket science, just a bit of playing around with planes transferring fuel to other planes.

As a further clue I'll tell you that the number of planes needed is less than 10. Quite a bit less.

[DanishDynamite]

Even partial answers are welcome. Answers such as "I managed to get a plane this far using this strategy" are very acceptable.

When I first encountered this question I was seriously stumped. Using more and more planes to help refuel my one special plane, it seemed to me I needed more than infinitely many planes to get the job done. Until I saw the light.

[KaiYeves]

Oh. I meant that over the poles is shorter than around the equator, so one could head east or west and be met by a plane comming up or down from the poles with a bit more fuel than if it had gone around.
And, let me guess... I'm wrong.
I'm used to that.

[DanishDynamite]

Oh. I meant that over the poles is shorter than around the equator, so one could head east or west and be met by a plane comming up or down from the poles with a bit more fuel than if it had gone around.
And, let me guess... I'm wrong.
I'm used to that.
Over the Poles is not shorter than any other greater circle around the Earth or any other planet.

So yes, you are wrong. Don't worry, we have all been wrong.

[ABR.]

Are these African or European planes?

...Oops sorry, wrong thread. I'll get me coat :D

I think we are ignoring whether the planes are fully laden or empty. However, I think there is some advice from the Book of Armaments which someone might find useful in solving this problem...

[Mellow]

I think you can do it with just two planes if you launch them initially in the same direction.......

[Mellow]

I might ammend my thinking to three aircraft

[JMV]

I agree with three airplanes and the amount of fuel would be five full tanks.

[EDIT: No, wait! I thought I got it with three, but now it seems I need four planes and six full tanks.]

[DanishDynamite]

Mellow and JMV: Please post a descriptive solution, i.e. explain which planes takeoff when, exchange what amount of fuel with what other planes, land when, etc.

You have both posted the right number of planes. My congratulations! :)

But how is it done?

[JMV]

Actually when I first said I got it with three I was wrong, I hadn't solved it correctly.

Anyways it is possible with three planes. I imagined the world as face of a clock, the island base being at the bottom at six o'clock or 30 minutes position. First three fully fueled planes take off and head towards right. When they reach 18 minutes position two of the planes transfer all the fuel they don't need for return journey to that one special plane, which continues halfway around the world from that point. The two other planes return to base and refuel. Then they take off fully fueled and head towards left. At 40 minutes position one of the planes transfers all the fuel it doesn't need for return journey to the other plane, which continues to meet that special circumnavigating plane at 48 minutes position. There the meeting plane tranfers half of its remaining fuel to the circumnavigating plane which was running/ran out of fuel. They head back towards the base. Now the third plane refueled with 14/ 15 of a full tank is coming back to meet the other two planes at 37 minutes position, where the other two planes run out of fuel. There the third plane transfers all the fuel it doesn't need for return journey evenly to the other two planes. Now they can all return to base.

That scenario requires three planes and five full tanks and 14/15 of a full tank of fuel to complete the mission.

[DanishDynamite]

Actually when I first said I got it with three I was wrong, I hadn't solved it correctly.

Anyways it is possible with three planes. I imagined the world as face of a clock, the island base being at the bottom at six o'clock or 30 minutes position. First three fully fueled planes take off and head towards right. When they reach 18 minutes position two of the planes transfer all the fuel they don't need for return journey to that one special plane, which continues halfway around the world from that point. The two other planes return to base and refuel. Then they take off fully fueled and head towards left. At 40 minutes position one of the planes transfers all the fuel it doesn't need for return journey to the other plane, which continues to meet that special circumnavigating plane at 48 minutes position. There the meeting plane tranfers half of its remaining fuel to the circumnavigating plane which was running/ran out of fuel. They head back towards the base. Now the third plane refueled with 14/ 15 of a full tank is coming back to meet the other two planes at 37 minutes position, where the other two planes run out of fuel. There the third plane transfers all the fuel it doesn't need for return journey evenly to the other two planes. Now they can all return to base.

That scenario requires three planes and five full tanks and 14/15 of a full tank of fuel to complete the mission.
Thank you for a very good solution. As I said before, it does in fact only require 3 planes as your scenario bares out beautifully. :)

However, your solution is not optimal in regard to fuel spent. It can be done using the amount of fuel you originally posted, i.e. exactly 5 full tanks.

How?

[ASEI]

Ah. For a minute there, I thought it was analogous to a rocket staging problem. Guess not, as the planes can go back and get more fuel and meet up again.

[mr obvious]

Ok, I'll bite. You can all laugh at me if I'm wrong (or what sometimes happens, I take all this time to type out the solution but in the meantime, someone else posts it and my post becomes chaff).

base----t1--h1----------midpoint----------------h2---t2-----base
t1=1/3 of the way from base to midpoint (closer to base),
h1=1/2 of the way from base to midpoint.
t2 and h2 same thing, only mirror imaged.

Planes A, B, and C take off from base heading towards t1 (the short way around). At t1, plane C, having completed its in-flight movie, transfers 1/6 of its fuel to each of planes A and B. This leaves C with 1/3 of a tank, so it can return, refuel and take off again, which it does. Planes A and B at t1 have 5/6 tanks. They continue until h1, where both have 4/6 tanks. Plane B, having run out of pretzels, transfers 1/3 of its tank to plane A, so plane A now has a full tank.

Plane B only has 1/3 of a tank, but on its way back to base (via t1) it is met by plane C, which had a full tank on liftoff, and since they paid their ground personnel quite well, this took no time. Planes B and C meet at the quarter-way point (not shown in diagram) where plane C gives plane B 1/3 tank and both land with excess fuel, which is used to find a vaccine against contagious yawning.

Plane A thus has enough fuel to get to the halfway-point on the 'other side' of the world, at h2, where the process is repeated, only somewhat in reverse. This had the effect of confusing the passengers, who did not expect that they had give the flight attendants pretzels and show a movie. (Briefly, planes B and C, at full, take off from the base heading towards h2, the shorter way. At t2 plane C gives B 1/3 fuel and returns to base; B is now full; B meets A at the halfway point h2 where A is out of fuel. B has 5/6 tank, gives A 1/3 tank; B now has 1/2 tank; enough to land on its own; A has enough to get to a point between t2 and base; plane C takes off with full tank, meets A at the point between t2 and base, transfers 1/6 tank, and all land happily ever after, except for the lost luggage, which managed to fly out during all the fuel transfer).

Do I get a biscuit?

[DanishDynamite]

Ok, I'll bite. You can all laugh at me if I'm wrong (or what sometimes happens, I take all this time to type out the solution but in the meantime, someone else posts it and my post becomes chaff).
No one is laughing and thanks for joining us. :)

base----t1--h1----------midpoint----------------h2---t2-----base
t1=1/3 of the way from base to midpoint (closer to base),
h1=1/2 of the way from base to midpoint.
t2 and h2 same thing, only mirror imaged.

Planes A, B, and C take off from base heading towards t1 (the short way around). At t1, plane C, having completed its in-flight movie, transfers 1/6 of its fuel to each of planes A and B. This leaves C with 1/3 of a tank, so it can return, refuel and take off again, which it does. Planes A and B at t1 have 5/6 tanks. They continue until h1, where both have 4/6 tanks.
Until this point, everything was fine.

Plane B, having run out of pretzels, transfers 1/3 of its tank to plane A, so plane A now has a full tank.
A problem. At h1, planes A and B both have 4/6 tanks. If B transfers 1/3 of its tank (= 1/2 its fuel) it would be left with 1/3 of a tank, which is not enough to get back home.

Or perhaps you meant it transfers 1/3 times 4/6 = 4/18 =2/9?

Do I get a biscuit?
Not until I understand the above bit. :)

[mr obvious]

No one is laughing and thanks for joining us. :)

Until this point, everything was fine.

A problem. At h1, planes A and B both have 4/6 tanks. If B transfers 1/3 of its tank (= 1/2 its fuel) it would be left with 1/3 of a tank, which is not enough to get back home.

Or perhaps you meant it transfers 1/3 times 4/6 = 4/18 =2/9?

Not until I understand the above bit. :)

I tried explaining it in my first post thus:
"Plane B only has 1/3 of a tank, but on its way back to base (via t1) it is met by plane C, which had a full tank on liftoff, and since they paid their ground personnel quite well, this took no time. Planes B and C meet at the quarter-way point (not shown in diagram) where plane C gives plane B 1/3 tank and both land with excess fuel, which is used to find a vaccine against contagious yawning."

So, yes, B, by itself, wouldn't be able to get back. But C can fuel up, fly out and meet B at the 1/6 point (between t1 and base) and give B the 1/6 tank needed to get home. I haven't calculated the fuel used for this. Let's see, C would need to carry 1/2 tank, so it uses 1/6 to get out, 1/6 to get back, and transfer 1/6 to B. So, C didn't need to take off with a full tank, but I really wanted a vaccine for contagious yawning.

Better?

By the way, I would be satisfied knowing this solution worked. As I guessed would happen in the original post, someone else posted a solution during my type-up. I didn't plan this strategy for fuel minimization.

[JMV]

I tried explaining it in my first post thus:
"Plane B only has 1/3 of a tank, but on its way back to base (via t1) it is met by plane C, which had a full tank on liftoff, and since they paid their ground personnel quite well, this took no time. Planes B and C meet at the quarter-way point (not shown in diagram) where plane C gives plane B 1/3 tank and both land with excess fuel, which is used to find a vaccine against contagious yawning."

So, yes, B, by itself, wouldn't be able to get back. But C can fuel up, fly out and meet B at the 1/6 point (between t1 and base) and give B the 1/6 tank needed to get home. I haven't calculated the fuel used for this. Let's see, C would need to carry 1/2 tank, so it uses 1/6 to get out, 1/6 to get back, and transfer 1/6 to B. So, C didn't need to take off with a full tank, but I really wanted a vaccine for contagious yawning.

Better?

By the way, I would be satisfied knowing this solution worked. As I guessed would happen in the original post, someone else posted a solution during my type-up. I didn't plan this strategy for fuel minimization.
I checked and your scenario is indeed sound but it requires 6 full tanks and two thirds of a tank of fuel which is quite a bit more than the minimum of five.

[DanishDynamite]

I tried explaining it in my first post thus:
"Plane B only has 1/3 of a tank, but on its way back to base (via t1) it is met by plane C, which had a full tank on liftoff, and since they paid their ground personnel quite well, this took no time. Planes B and C meet at the quarter-way point (not shown in diagram) where plane C gives plane B 1/3 tank and both land with excess fuel, which is used to find a vaccine against contagious yawning."
Indeed you did. Sorry, I just stopped reading after hitting the problem above. :)

When you say "meet at the quarter-way point", do you mean in terms of distance or in terms of fuel?

[DanishDynamite]

I checked and your scenario is indeed sound but it requires 6 full tanks and two thirds of a tank of fuel which is quite a bit more than the minimum of five.
Thanks for doing the calculations. :)

Keep working at it, gentlemen. The reward when it all falls into place is wonderful.

[mr obvious]

Indeed you did. Sorry, I just stopped reading after hitting the problem above. :)

When you say "meet at the quarter-way point", do you mean in terms of distance or in terms of fuel?

Again, I wasn't trying for fuel minimization. At the time I started writing my post, no other solution had been posted yet. So I was vague where I could be with my terminology, except where it was vital. When I said 'quarter way point' I meant halfway between base and h1. But to minimize fuel, it can be at the 'sixth' point, which is 1/6 of the way from base to the midpoint. Of course, seeing as I've guzzled way too much fuel, this distinction isn't much worth pursuing from my perspective - but the important thing (for me) is that the solution works.

[Sarawak]

Assumptions - all planes travel at the same speed, planes cannot circle or otherwise wait anywhere with reduced fuel consumption rate.

All amounts of fuel are expressed as fractions of a full tank.

1. Three planes take off, each with a full load of fuel.
2. They fly 1/8 of the way around the world, so each plane has consumed 1/4 of its fuel.
3. One plane transfers 1/4 of its fuel to each of the other two. This plane returns to base, and has just enough to reach it, since it now has 1/4 of its fuel left.
4. The other two planes are full now. They fly an additional 1/8 of the way around the world, each one consuming 1/4 of its fuel.
5. One plane transfers 1/4 of its fuel to the other. This plane returns to base, and has just enough fuel (1/2) to make it.
6. The other plane is now full, and is 1/4 of the way around the world. It continues the journey alone.
7. When the plane that is circumnavigating the world is 1/2 of the way around, another plane takes off from base with a full load (this is the fourth load) of fuel, in the opposite direction.
8. These planes meet when the circumnavigating plane is 3/4 of the way around the world, and out of fuel. The plane that meets it has 1/2 its fuel, and transfers 1/4 to the circumnavigating plane.
9. Both planes now have 1/4 of a tank, and head back to base. Simultaneously, a third plane takes off from base with a full load of fuel (the fifth full load), and heads to meet the other two planes.
10. The three planes meet when the circumnavigating plane is 7/8 of the way around the world. The circumnavigating plane and the plane that has already refueled it are now both out of fuel. The plane coming to meet them has 3/4 of a tank. It transfers 1/4 to each of the other two planes, so each plane now has 1/4 of a tank.
11. All three planes return to base, running out of fuel as they touch down on the runway.

No additional planes are needed, because the planes return from the outbound leg early enough to leave in the opposite direction when they are needed.

[Sarawak]

If my solution is correct, then generalize. Suppose each plane can fly:

(n+1)/(3n-1)

of the way around the world. Show that feat is possible with n planes and 2n-1 loads of fuel. Prove optimality of number of planes and loads of fuel of this solution, or show by counter-example that it is possible to use fewer planes or less fuel (or both).

[Sarawak]

With the original problem, I thought I had a solution with 3 planes and 7 loads of fuel, even if the planes could only fly 5/11 of the way around the world. But the problem with my 'solution' to this alternate problem is that the two of the planes that do not circumnavigate the world have to take off from base to meet the returning plane before they have returned to base after escorting it off. If the circumnavigating plane can fly more slowly (but with the same fuel consumption per distance), then it is possible to use 3 planes and 7 loads of fuel if they can only go 5/11 around the world.

[Mellow]

By the way, I'm not that smart but, my original supposition of 2 planes, then ammended to three planes was based upon nothing more than the following observation.

Many people would start this problem with a clock face withthe starting airbase being at 6:00. You'd then send aircraft out in both clockwise and anti-clockwise directions, trying to refuell enough to reach the 12:00 position, thus you end up with many many flights and lots and lots of refuelling.

So, I only arrived at 3 planes by assuming you send two or more out in the same direction first.

I think he problem is elegant in that the way it is phrased leads the reader into thinking about the globe as two halves that have to be negotiated separately.

Nice...

[Sarawak]

Where is DanishDynamite? I hope he did not miscalculate his fuel requirements.

[DanishDynamite]

Assumptions - all planes travel at the same speed, planes cannot circle or otherwise wait anywhere with reduced fuel consumption rate.

All amounts of fuel are expressed as fractions of a full tank.

1. Three planes take off, each with a full load of fuel.
2. They fly 1/8 of the way around the world, so each plane has consumed 1/4 of its fuel.
3. One plane transfers 1/4 of its fuel to each of the other two. This plane returns to base, and has just enough to reach it, since it now has 1/4 of its fuel left.
4. The other two planes are full now. They fly an additional 1/8 of the way around the world, each one consuming 1/4 of its fuel.
5. One plane transfers 1/4 of its fuel to the other. This plane returns to base, and has just enough fuel (1/2) to make it.
6. The other plane is now full, and is 1/4 of the way around the world. It continues the journey alone.
7. When the plane that is circumnavigating the world is 1/2 of the way around, another plane takes off from base with a full load (this is the fourth load) of fuel, in the opposite direction.
8. These planes meet when the circumnavigating plane is 3/4 of the way around the world, and out of fuel. The plane that meets it has 1/2 its fuel, and transfers 1/4 to the circumnavigating plane.
9. Both planes now have 1/4 of a tank, and head back to base. Simultaneously, a third plane takes off from base with a full load of fuel (the fifth full load), and heads to meet the other two planes.
10. The three planes meet when the circumnavigating plane is 7/8 of the way around the world. The circumnavigating plane and the plane that has already refueled it are now both out of fuel. The plane coming to meet them has 3/4 of a tank. It transfers 1/4 to each of the other two planes, so each plane now has 1/4 of a tank.
11. All three planes return to base, running out of fuel as they touch down on the runway.

No additional planes are needed, because the planes return from the outbound leg early enough to leave in the opposite direction when they are needed.
Yoooohoooo!!! :lol::lol:

Well done, Homo Bibiens.

This is exactly the solution I found as well. I don't have any mathematical proof that it is the best possible, but aside from my intuition (and attempts at better ones) there is a lot of mathematical (or at least symmetry) beauty going on with this solution, namely:

1. Any plane taking off does so fully loaded.
2. Any plane landing does so entirely empty.
3. At the start, the 3 planes needed take off together. At the end, they all land together in triumf!

Once again, congratulations, Homo Bibiens.

[DanishDynamite]

Where is DanishDynamite? I hope he did not miscalculate his fuel requirements.
Here I am. Sorry for not being back sooner. :)

BTW, I found your question on generalizing and proving the generalization very interesting. As I said in my reply above, I don't actually have a proof that the solution I (and you) found is the best possible.

(I leave the proof as an exercise for the reader.) :)

[Sarawak]

Welcome back, DanishDynamite. I do not have a proof of optimality even in the case of three. But I can solve the generalized problem, I just am not sure if the solutions are optimal. I think they are, but maybe this is a wrong idea.

The general solution is similar, it is for all planes to take off at the same time, then when one plane can refuel all the others completely and only just return to base, then it does so. The others continue until another plane can refuel the others completely and only just return. This is repeated until there is only one plane, and then it continues alone, and the mirror image of the process is repeated when it returns.

The number n=7 works to nice round numbers. If each plane can fly 2/5 around the world, then 7 planes and 13 loads of fuel are sufficient. All 7 planes fly together to 0.05 of the way around the world. At this point, they all have 7/8 fuel, so one plane refuels the other six. These planes are full, and the refueling plane has 1/8, so it can return to base. Then the others continue to 0.1 of the way around the world. At this point, they have 7/8 fuel, so one plane refuels the other five. It has 2/8 remaining, so it can return to base. The others continue to 0.15 of the way around the world, and so on in this way. When they are 0.3 of the way around the world, there are two planes remaining, and one is full and the other has 3/4 remaining, which is just enough to return. The full plane continues to 0.5 of the way around the world, and it is then half full. Then everything plays in exactly the reverse on the other side.

There is a limit to this procedure, since:

(n+1)/(3n-1)=1/3+4/(9n-3)

So it is never possible by this method to accomplish this mission if the planes can go only 1/3 or less distance around the world. But it is possible to do better with more planes by a different method, I think. I do not know if there is a limit, if the planes can fly one millimeter then is it possible with 10 billion planes, or something like this? I will have to think about it.

[DanishDynamite]

Welcome back, DanishDynamite. I do not have a proof of optimality even in the case of three. But I can solve the generalized problem, I just am not sure if the solutions are optimal. I think they are, but maybe this is a wrong idea.

The general solution is similar, it is for all planes to take off at the same time, then when one plane can refuel all the others completely and only just return to base, then it does so. The others continue until another plane can refuel the others completely and only just return. This is repeated until there is only one plane, and then it continues alone, and the mirror image of the process is repeated when it returns.

The number n=7 works to nice round numbers. If each plane can fly 2/5 around the world, then 7 planes and 13 loads of fuel are sufficient. All 7 planes fly together to 0.05 of the way around the world. At this point, they all have 7/8 fuel, so one plane refuels the other six. These planes are full, and the refueling plane has 1/8, so it can return to base. Then the others continue to 0.1 of the way around the world. At this point, they have 7/8 fuel, so one plane refuels the other five. It has 2/8 remaining, so it can return to base. The others continue to 0.15 of the way around the world, and so on in this way. When they are 0.3 of the way around the world, there are two planes remaining, and one is full and the other has 3/4 remaining, which is just enough to return. The full plane continues to 0.5 of the way around the world, and it is then half full. Then everything plays in exactly the reverse on the other side.

There is a limit to this procedure, since:

(n+1)/(3n-1)=1/3+4/(9n-3)

So it is never possible by this method to accomplish this mission if the planes can go only 1/3 or less distance around the world. But it is possible to do better with more planes by a different method, I think. I do not know if there is a limit, if the planes can fly one millimeter then is it possible with 10 billion planes, or something like this? I will have to think about it.
Very nice!!

I especially like how you found a lower limit on how far a plane must be able to fly for there to be a solution at all (using this method, that is). Nice! :)