18

Consider three identical airplanes starting at the same airport. Each plane has a fuel tank that holds just enough fuel to allow the plane to travel half the distance around the world. These airplanes possess the special ability to transfer fuel between their tanks in mid-flight. What are the maximum around the world trips that airplane1 can make?

I found this question on interviewbit and this really blows me off. I frankly have no idea how to proceed. I thought answer would be 0 since it apparently seems impossible but answer is 1.

EDIT: This is not the same as the original question, but it is properly sourced. OP can decide what to keep.

A group of aeroplanes is based on a small island. The tank of each plane holds just enough fuel to take it halfway around the world. Any desired amount of fuel can be transferred from the tank of one plane to the tank of another while the planes are in flight.

The only source of fuel is on the island, and for the purposes of the problem it is assumed that there is no time lost in refuelling either in the air or on the ground.

What is the smallest number of planes that will ensure the flight of one plane around the world on a great circle, assuming the planes have the same constant ground speed and rate of fuel consumption and that all planes return safely to their island base?

Source: http://xn--webducation-dbb.com/wp-content/uploads/2019/01/Martin-Gardner-More-mathematical-puzzles-and-diversions-Pelican-books-1961.pdf [Original text page number 39]

Chris Cudmore
  • 7,779
  • 1
  • 23
  • 50
Charlie
  • 635
  • 4
  • 10
  • 1
    What exactly counts as a circumnavigation? Can a plane fly in tight circles around the North Pole and count them as laps "around the world", since every meridian of longitude is crossed? – dan04 Aug 09 '22 at 21:37
  • 5
    @dan04 Doesn't matter. They have half enough fuel no matter how you define it. – Chris Cudmore Aug 09 '22 at 22:06
  • 4
    If you are interested in mathematical puzzles, the original version of this puzzle was published in one of Martin Gardners books (don't remember which one, most likely one of "The Xth Scientific American Book of Puzzles and Games"). – Revolver_Ocelot Aug 10 '22 at 08:40
  • 1
  • If it is ok for plane 2 and 3 to not come back it gives plane 1 longer range. – Thorbjørn Ravn Andersen Aug 10 '22 at 11:04
  • 1
  • 5
    Per the InterviewBit TOS, "You are prohibited from... copying or duplicating in any manner any of the Scaler Content or other information available from the Platform", thus I'm voting to close this under our policy against sharing puzzles without the creators' consent – bobble Aug 11 '22 at 04:28
  • If it is a copyright violation, it should be deleted, not "closed." – WGroleau Aug 11 '22 at 05:56
  • 2
    @WGroleau, It can't be copyright violation: this is an old trivial task, I've seen its variations elsewhere long ago. – Zeus Aug 11 '22 at 07:43
  • 1
    @bobble it is not a paid question or anything. Anyone can look it up with a random link or by searching via keywords. https://www.interviewbit.com/puzzles/#problems here's the link to all the puzzles if you are interested. Plus Scaler content is paid so we are not allowed to share anything from there while this is from the common site – Charlie Aug 11 '22 at 09:29
  • 4
    @Charlie content can be provided for free but with terms that it can't be shared. Elsewhere the Terms define "Scaler" to mean "InterviewBit" and "Content" to be things including any text on the site. The copyright is not the general idea of the problem but rather the specific formulation/word choice/presentation. – bobble Aug 11 '22 at 13:50
  • 1
    @bobble Rewording an old text of five sentences does not create something sufficiently original to gain a copyright. Of course they can claim they hold a copyright, just like I can say I'm the king of, say, Bavaria. It's however laughable, not only because Bavaria hasn't been a kingdom for a hundred years. :) – Karl Aug 12 '22 at 23:23
  • 1
    @Karl it is immaterial whether they have the right to force someone to take down a copy, when the fact of the matter is they would rather no-one copy. The policy is not based on copyright but politeness and following clearly-proclaimed wishes – bobble Aug 13 '22 at 02:33

6 Answers6

32

My first attempt resulted in crashes. Thanks Ross for pointing it out.

Crashes are bad. We must land all planes.

Problems like this require you thinking in the right units. Here's a revised solution:

Assumptions: A tank holds 180 units of fuel.
Each degree of travel consumes 1 unit of fuel.
Planes always travel 1 degree a minute,
Fuel transfer is instantaneous.
Denote a plane as A(position in degrees, Fuel)

1: A( 0, 180), B( 0, 180), C( 0, 180). (t = 0 m)
    A, B, C all take off at the same time, and
2: A( 45, 135), B( 45, 135), C( 45, 135). (t = 45 m)
    fly 45 degrees.
3: A( 45, 180), B( 45, 180), C( 45, 45). (t = 45 m)
    C transfers 45 units of fuel to each of A and B.
4: C( 0, 180). (t = 90 m)
    C returns and refuels
5: A( 90, 135), B( 90, 135) (t = 90 m)
    A and B carry on to 90.
6: A( 90, 180), B( 90, 90) (t = 90 m)
    B transfers 45 fuel to A
7: B( 0, 180) (t = 180 m)
    B returns and refuels
8: A(270, 0) (t = 270 m)
    A carries on to 270.
9: A(270, 0) C(270, 90) (t = 270 m)
    C takes off in the other direction at t = 180 to meet A at 270.
10: A(270, 45) C(270, 45) (t = 270 m)
    C transfers 45 units of fuel to A.
11: A(315, 0) C(315, 0) (t = 315 m)
    C and A carry on to 315.
12: A(315, 0) B(315, 135) C(315, 0) (t = 315 m)
    B takes off at t=270, and travels to 315.
13: A(315, 45) B(315, 45) C(315, 45) (t = 315 m)
    B transfers 45 units to each of A and C,
14: A(360, 0) B(360, 0) C(360, 0) (t = 360 m)
    They all have just enough fuel to get home.
      
The main trick is that the question specifies tank size, not fuel amount. So refueling is allowed.

candied_orange
  • 276
  • 1
  • 9
Chris Cudmore
  • 7,779
  • 1
  • 23
  • 50
  • 3
    This is what I imagine when reading the question. Nice one saving all planes! – justhalf Aug 10 '22 at 02:57
  • 6
    Knowing the intended answer is 1 I think this is not the intended solution. Because this solution has actually as answer infinite because the procedure can be repeated as much as you like. So refuelling is probably not allowed – Ivo Aug 10 '22 at 06:27
  • 1
    You could probably do it with two planes if plane B can land at other airports along the way and refuel while plane A circles overhead. I think the question needs rewording. – user3153372 Aug 10 '22 at 07:44
  • The "you can refuel plane 3" is a good insight. – Thorbjørn Ravn Andersen Aug 10 '22 at 11:06
  • 2
    @Ivo Yes, It is infinitely repeatable. If you can do it once, and land all planes, then we can simply do it again, as many times as we want. However, I actually think the question is ambiguous. I went with an implicit assumption that we need to land all planes, and without that restriction being explicit, it's all open for debate. – Chris Cudmore Aug 10 '22 at 13:57
  • @ChrisCudmore Right, definitely ambiguous as it doesn't explicitly state that all planes have to land or if planes are able to refuel outside of the specified transfer ability. Based on the fact that it only cares about plane 1 being able to circumnavigate and the OP saying the intended answer is 1, I made the implicit assumption that only Plane 1 needed to land, and they were unable to refuel beyond the original 3 full tanks. But as written those assumptions are not mandated by the question – Anthony Ingram-Westover Aug 10 '22 at 16:45
  • I don't think the fuel transfer is required to be instantaneous. It just has to completed simultaneously, in transit, and on time. Stated another way: refueling causes no delay. – candied_orange Aug 10 '22 at 22:15
  • This problem and this solution were published in one of Martin Gardner's Mathematical Games articles in Scientific American, and reprinted as no.2 in chapter 5, Nine Problems, of More Mathematical Puzzles and Diversions, the second collection of such articles. – Rosie F Aug 11 '22 at 18:42
28

Plane 1 can make 1 trip around the world by following the below process:

Plane 1 and Plane 2 take off in the same direction at the same time. Once they reach 1/4 of the way around the globe, plane 2 transfers all remaining fuel to plane 1. At this point Plane 1 has a full tank of fuel (half globe), Plane 2 flames out, and Plane 3 is still at the airport.

Once that step is met, then:

Plane 1 continues to fly until going half way around the world. With the extra half tank of fuel from plane 2, Plane 1 has a half tank of fuel left. Plane 3 departs the airport at this time, flying in the opposite direction.

Step 3:

Plane 3 and Plane 1 meet up a quarter of the way further around the globe (so plane 1 is 75% of the way around and flying on fumes). At this point Plane 3 transfers all remaining fuel (half a tank, enough for a quarter of the way around the world) to Plane 1.

At this point:

Plane 1 can use the transferred fuel from Plane 3 to complete it's circumnavigation. Plane 2 is flamed out (glided to safety or crashed) to one direction of the airport, Plane 3 is flamed out 25% in the opposite direction.

Dmitry Kamenetsky
  • 35,897
  • 5
  • 66
  • 276
  • 1
    Now the trick is to find 3 spots on the surface of the earth that are each 90 degrees apart from the next on a great circle - and all on land, preferably near an airport. (Hard enough to find a pair of points on land 180 degrees apart, as most land has water at its antipodes. To then find a starting point 90 degrees from both would be another challenge...) – Darrel Hoffman Aug 10 '22 at 13:49
  • 3
    @DarrelHoffman The planes transfer fuel mid-air, and there's no requirement to actually land any of the planes, rather than simply ejecting when the fuel tank is empty. You don't need any land at all except the starting airport. An interesting geography question, though. – Nuclear Hoagie Aug 10 '22 at 15:52
  • 7
    Of course this only works if you make the unrealistic assumption that fuel burn is independent of current fuel load. – Peter Green Aug 10 '22 at 17:13
  • 8
    @PeterGreen Yeah, definitely don't suggest asking this question in Aviation.SE. Not only because of stuff like that, but also I think they'd be somewhat horrified that we're just ejecting and crashing 2 of the planes to make this happen... – Darrel Hoffman Aug 10 '22 at 17:19
  • 1
    @DarrelHoffman If you plan the transfer locations right, it should be possible for planes 2 and 3 to glide to safe landings. Frankly, I'd be more worried about transferring fuel between planes flying in opposite directions. – Gordon Davisson Aug 10 '22 at 23:17
  • 2
    @DarrelHoffman Meanwhile, the RAF wants you to hold their beer. see Operation Black Buck. – Aron Aug 11 '22 at 03:15
  • 1
    @DarrelHoffman "To then find a starting point 90 degrees from both would be another challenge." No, that's almost trivial. All points that match this criterion form a full circle around the globe. And AFAIK there is no great circle not touching land at any point. – asdfex Aug 11 '22 at 11:29
  • @asdfex Granted. Finding 3 points on land with airports however, that might be harder. – Darrel Hoffman Aug 11 '22 at 13:18
  • Psh, you guys are forgetting that some planes can land in water. Or that aircraft carriers exist! – robbie crockett Aug 11 '22 at 14:57
  • @robbiecrockett The planes that can land on carriers are generally short-range flyers - they certainly can't go halfway around the world on a single tank (if they could, we maybe wouldn't need carriers). Pretty sure pontoon planes can't do that either, they tend to be short-range as well. – Darrel Hoffman Aug 11 '22 at 18:01
  • @DarrelHoffman I think this can be constructed as an overpass query.... :) – crasic Aug 11 '22 at 21:26
  • @Aron I was going to mention that one! :) – ProgrammingLlama Aug 12 '22 at 08:05
  • @DarrelHoffman: Yeah, I checked, and the current longest range listed for carrier-based aircraft (https://en.wikipedia.org/wiki/Carrier-based_aircraft) is only about 2000 nmi "ferry range" (3,745 km, less than a tenth of Earth's 40 000 km circumference) for the https://en.wikipedia.org/wiki/Grumman_C-2_Greyhound "carrier onboard delivery" cargo transport with "internal fuel package" which I assume means using the cargo space for fuel. So yeah, pretty short range. – Peter Cordes Aug 12 '22 at 22:40
  • Carrier-based tankers seem to have been replaced by Super Hornets tanking to each other (pending unmanned refueling craft), but the retired KS-3B lists a ferry range of 3,368 nmi (6,238 km) for the plain 3A variant; IDK if the tanker could go further. The largest plane to land and take off from a carrier was a C130 (google it) at takeoff weights up to 121000 pounds (below the normal max of 155k lb). https://en.wikipedia.org/wiki/Lockheed_C-130_Hercules says ferry range of ~4000 nmi / 7400 km, still under 1/5th of the way around the world. – Peter Cordes Aug 12 '22 at 22:44
  • @DarrelHoffman: A plane with most of the internals stripped for weight to carry more fuel, no military radar etc, and with modern efficient turbofans or turboprops, could probably go pretty far even if it had to launch from a carrier. Maybe using JATO (rocket boosters you attach to the side of a plane like a C-130 to give extra takeoff thrust.) Anyway yeah, the scenario is a big stretch for a planet the size of earth, with current commercial / military aircraft, because they're not optimized for extreme range and midair refueling. – Peter Cordes Aug 12 '22 at 22:49
9

For funsies, let's see how far they could go using asparagus staging.

That is, plane 3 is continuously topping up plane 2, who is continuously topping up plane 1.

This means that plane 3 is burning fuel 3x as fast while the other two are topped up, so if we say that C is the circumference of the earth, plane 2 and plane 1 make it C/6 before losing plane 3

now plane 1 and plane 2 have a full tank, and plane 2 is topping up plane 1 continuously. That means we can go C/4 distance before plane 2 runs out, for a total of 5C/12. Almost halfway! Unfortunately, with a full tank, plane 1 can only travel up to C/2 further, so will be 11C/12, just one twelfth away from a full navigation.

In fact, you would need 4 planes to complete the circumnavigation. With this method, you have the series $$ \frac{1}{2} \sum_{i=1}^{n}\frac{1}{a}$$ for n planes. The fourth term here gives 25/24, which is just over 1 circumnavigation! Whoo!

And as n goes to infinity, because the series diverges you can make infinitely many circumnavigations!

robbie crockett
  • 321
  • 1
  • 4
1

I think my solution uses the least total fuel and pilot/aircraft time, plus the task is completed and

everybody gets home safely, meaning its maximum repeatability count is primarily limited by fuel supply, but still higher than any alternative answers.

First, we need to clarify the question:

What, exactly, does flying around the world mean?
Does it mean that you have to pass through all 360 degrees of longitude?

Assuming that suggested clarification is accepted, here's the solution:

Plane 1 flies to the nearest pole, does a tight circle (thus, flying around the world), and returns.

Why does this work?

Assume for a moment the plane is on the equator, as far away from the poles as possible.
Because the Earth bulges out a bit at the equator, having enough fuel to go halfway around the world there is more than enough to get to the pole and back, enough for that circle at the pole.
If the airport is not on the equator, even less fuel is required to reach the nearest pole.

If the suggested clarification is accepted, but the only fuel available is what's in full aircraft tanks,

then the maximum number of times this can be repeated is 3.

If the suggested clarification is not accepted:

If the challenger adds that you have to travel through all degrees of latitude too, ask if the airport is on the equator. If so, follow the above procedure, refuel, and do the same with the other pole. If the challenger clarifies that the challenge requires completing a "great circle," see other answers.

WBT
  • 756
  • 1
  • 9
  • 16
  • The clarification doesn't actually change anything at all, since the amount of fuel is 1/2 of the distance around the world. If you assume you can fly around a pole, then the plane has 1/2 of the polar circle in fuel. If it's a great circle around the equator, the plane has 1/2 that amount of fuel. The amount of fuel is a percentage of the distance needed to be flown, no matter what that distance is – Anthony Ingram-Westover Aug 12 '22 at 00:26
  • @AnthonyIngram-Westover If you're on the equator with 1/2 the distance around the equator in fuel, you can make it up around a pole and back. – WBT Aug 12 '22 at 00:29
  • Right, but the goal is to travel x miles where x is the distance around the world (however you choose to define that) and there is enough fuel to travel x/2 miles. However you define x (distance to travel around the world) the amount of fuel is half that. – Anthony Ingram-Westover Aug 12 '22 at 16:43
  • @AnthonyIngram-Westover Where are you reading that in the question as originally stated? You appear to be assuming a constraint which isn't actually there: what you assume to be a constant x is actually x and y and the assumption x=y. Clarification questions allow the puzzle-presenter the opportunity to add constraints; they may or may not. Challenging those assumptions is key to the kind of out-of-the-box thinking this answer represents. – WBT Aug 12 '22 at 20:39
  • 1
    By your definition, a plane going from North pole to south pole and then continuing to north pole did not went around the world. This feels strange... For me a more formal definition of "around" is that if you project the object you go around (here the earth) on the 2D space of your loop (the path taken by your plane), then all points of the projection are inside the loop. With this definition, your solution doesn't work sadly. – Alois Christen Aug 12 '22 at 21:19
  • @WBT "Each plane has a fuel tank that holds just enough fuel to allow the plane to travel half the distance around the world" "What are the maximum around the world trips" Same exact verbiage. You can't define "distance around the world" one way to determine fuel capacity and in a different way to determine actual flights that meet the criteria – Anthony Ingram-Westover Aug 14 '22 at 22:52
0

I'm late to the party, but I think the accepted answer is wrong

all planes fly west
at 1/8 of the trip: plane 3 fills the other planes, and just make it back with the remaining 1/4 tank - it refuels at the airport and flies west again
at 1/4 of the trip: plane 2 fills plane 1 and returns; When plane 3 and plane 2 meet, they redistribute their fuel and fly back At exactly half the trip they refuel at the airport and fly east
at 5/8 of the trip: plane 3 fills plane 2, heads back, and refuels
at 3/4 of the trip: plane 2 shares fuel with plane 1, and both fly west
at the same time plane 3 flies east again, and at 7/8 is in time to share enough fuel with both other planes.
al planes land safely and can repeat the process indefinitely (as long as there is fuel at the airport.

So the answer is, an infinite number of times. (as long as there is fuel at the airport. )

Retudin
  • 8,511
  • 1
  • 13
  • 46
0

General Solution Where All Airplanes Survive

If we don't want to destroy any planes, this problem leads to a nifty insight - not surprising since it was shared by Martin Gardner. I will answer his variant asking for the number of planes needed so the treatment is more general.

The general template for the strategy is similar to Chris Cudmore's answer ( https://puzzling.stackexchange.com/a/117441/81255 ) : there is some send-off help where the leading airplane receives fuel, followed by a solo leg for the leader, finished by a last-stretch help where the leading airplane receives some fuel again.

A Note on Fuel-Transfer

Say there are $n$ planes flying: a chosen leader, $L$, to make the full journey around the world, and $(n-1)$ helpers. Since fuel-transfer takes $0$ time between any 2 airplanes, one can make infinitesimal transfers between any two airplanes in quick succession. Quick succession with $0$ time in between is effectively simultaneous fuel-transfer. So we can assume that many airplanes can send/receive fuel simultaneously and continuously from any number of airplanes.

Units of Measurement

Let's measure distance in fraction of great-circle length, and fuel in fraction of tank-capacity. Since time and velocity aren't specified in the problem, we can simply measure time as distance. So we can say "a plane loses fuel at a rate of $2x$" to mean "if the plane travels a distance $x$ (fraction of great-circle), its fuel reduces by $2x$ (fraction of tank-capacity)"

Burn Factor

When an airplane is helping, it loses fuel at a rate of $2bx$ for some $b>1$, since it is spending fuel for itself and at least one other airplane. Let's call $b$ the burn factor. For example, if a single helper is helping $(n-1)$ other airplanes, then $n$ airplanes are flying on effectively 1 tank and the burn factor, $b$, is $n$. The burn factor here is essentially the number of planes the helper's tank is fueling.

Strategy

  1. On the send-off stretch, the first helper plane fuels all other planes for a distance $r_1$ and then returns to refuel, while the the second helper plane takes over and fuels the remaining for a distance $r_2$ and returns, and so on, with airplane $i$ fueling the remaining pack for a distance $r_i$ before returning to refuel, till only the leader, $L$, is left.

  2. $L$ flies solo for a distance.

  3. The refueled helpers fly in the opposite direction, rewinding the send-off pattern: the first refueled helper rewinds the tape of the last returned helper. Clearly they can help $L$ the same distance on the last-stretch as in the send-off stretch and all planes land.

Analysis

We just need to consider the total send-off helping distance since the last-stretch helping distance is the same.

The first helper will lose fuel at the rate of $2b_1 x$ when helping, with a burn factor $b_1 = n$. Helper plane $i$ will lose fuel at the rate of $2 b_i x$ when it is helping, with $b_i = b_{i-1} - 1$ since it is fueling one less plane than the previous helper. Every helper plane loses fuel at the rate of $2x$ when returning to refuel.

Helper plane $i$ will have a full tank when it starts helping, when helper $(i-1)$ turns back to refuel. It has one less plane to help compared to $(i-1)$, but it will have to travel a longer distance back to the island to refuel.

If every helper helps maximally, it will have just enough fuel to reach the island when it turns back. The first helper will have $1 - 2 b_1 r_1$ fuel left in the tank when it turns, which should be exactly $2r_1$ to make it back.The second helper will need to have $2(r_1 + r_2)$ fuel to make it back, and so on:

$$ \begin{array}{ll} 1 - 2 b_1 r_1 = 2 r_1, \\ 1 - 2b_2 r_2 = 2 (r_1 + r_2) = (1 - 2b_1 r_1) + 2r_2, \\ \vdots \\ 1 - 2b_{n-1} r_{n-1} = 2(r_1 + r_2 + \cdots + r_{n-1}) = (1 - 2b_{n-2}r_{n-2}) + 2r_{n-1}, \end{array} $$ or, more succinctly, $$ 1 - 2b_i r_i = 1 - 2b_{i-1} r_{i-1} + 2 r_i, \quad 2 \leq i \leq n-1. $$ Since $b_i = b_{i-1} - 1$ and $b_1 = n$, it is straightforward to see that

$$ r_i = \frac{1}{2(b_1 + 1)} = \frac{1}{2(n+1)} \forall i < n. $$ So every helper plane pushes itself and the remaining pack the same distance forward. Since there are $n-1$ helpers, the total send-off helping distance is $$ \sum_{i=1} ^{n-1} r_i = \frac{n-1}{2(n+1)}. $$

The last-stretch helping distance is identical since it is just a tape-rewind of the send-off, resulting in a total helping distance of $$ \frac{n-1}{n+1}. $$ Clearly this has to be at least $1/2$ for $L$ to be able to fly the rest by itself. So $$ \frac{n-1}{n+1} \geq \frac{1}{2} \implies n \geq 3. $$

Addendum 1

Interestingly, when $n=3$, all planes will be empty upon reaching the finish-line: on the last stretch, $L$ will be met just in time by one helper exactly when it is empty, and the first helper will be met by the second exactly when it is empty. So the total fuel used in this case will be 5 tanks.

Addendum 2

A seemingly viable alternative, where all helpers simultaneously help $L$ (but not each other), is actually never viable for any $n$, since the ratio of how much a helper's fuel goes into flying itself versus flying another plane is worse (larger).

Hope this amuses/helps!