# Difference between revisions of "Around the world"

m (Get rid of aviation jargon ("ground speed")) |
|||

Line 1: | Line 1: | ||

A group of airplanes 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 it is assumed that there is no time lost in refueling 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 that the planes have the same constant speed (relative to the ground) and rate of fuel consumption, and that all planes return safely to their island base? | A group of airplanes 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 it is assumed that there is no time lost in refueling 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 that the planes have the same constant speed (relative to the ground) and rate of fuel consumption, and that all planes return safely to their island base? | ||

+ | |||

+ | {{Solution | First, let's agree on conventions. The main journey will be westward, and all units will be in degrees. So 360 degrees is a full circle around the earth, 1 unit of fuel is enough fuel to travel one degree, and 1 unit of time is the time taken to travel one degree. | ||

+ | |||

+ | One unassisted aeroplane can travel 180 degrees non-returning, or 90 degrees returning. Let's see how far we can get with two aeroplanes: a main flight and an assisting flight. | ||

+ | |||

+ | :The assisting flight requires fuel for the journey out, fuel for the transfer, and fuel for the return. The best place to transfer fuel to the main flight would be when the amount of fuel available (not needed for return) is exactly the amount of empty space in the main flight's fuel tanks. That way no fuel is wasted. | ||

+ | |||

+ | :Space in tank <nowiki>=</nowiki> D (distance from base, since fuel used equals distance travelled) | ||

+ | :Transferrable fuel <nowiki>=</nowiki> 180 - 2D (starting amount minus what's used for flight out and return) | ||

+ | |||

+ | :Equating these: | ||

+ | :D <nowiki>=</nowiki> 180 - 2D | ||

+ | :D <nowiki>=</nowiki> 60 | ||

+ | |||

+ | :So the main flight is refueled at D <nowiki>=</nowiki> 60, enabling it to reach 240 degrees non-returning (the 60 degrees already travelled plus a further 180 on a full tank), or 120 degrees returning (reserve 60 units of fuel for returning the 60 degrees already travelled, which leaves 120 units of fuel for travelling a further 60 units and back). | ||

+ | |||

+ | With three aeroplanes, several scenarios are possible: | ||

+ | *Two assisting flights both transfer fuel to the main flight at different locations on the latter's outward journey, the first at D <nowiki>=</nowiki> 60, the second later. | ||

+ | *One flight transfers fuel to the primary assisting flight at D <nowiki>=</nowiki> 60, which in turn transfers fuel to the main flight. | ||

+ | *Two assisting flights both transfer fuel to a main returning flight at D <nowiki>=</nowiki> 60, one on its flight out, one on its return. | ||

+ | |||

+ | The first two scenarios are equivalent with respect to the optimal distance for the second transfer and the total distance that the main flight can travel. I will skip the first scenario and do the maths for the second. | ||

+ | |||

+ | :Secondary assisting flight transfers fuel to primary assisting flight at D <nowiki>=</nowiki> 60. | ||

+ | |||

+ | :We use the same logic as before to determine the optimal time to transfer fuel from the primary assisting flight to the main flight. | ||

+ | |||

+ | :Space in main flight's tank <nowiki>=</nowiki> D | ||

+ | :Transferrable fuel from primary assisting flight <nowiki>=</nowiki> 180 - 2(D - 60) - 60 (because tank full at D <nowiki>=</nowiki> 60 but need to travel that distance again on return) | ||

+ | :This simplifies to 240 - 2D | ||

+ | |||

+ | :D <nowiki>=</nowiki> 240 - 2D | ||

+ | :D <nowiki>=</nowiki> 80 | ||

+ | |||

+ | :So the main flight is refueled at D <nowiki>=</nowiki> 80, enabling it to reach 260 degrees non-returning or 130 degrees returning. | ||

+ | |||

+ | As for the third scenario, the main flight is refueled at D <nowiki>=</nowiki> 60, enabling it to reach 150 degrees returning (90 degrees further than the 60 degrees already travelled), to be refueled again at D <nowiki>=</nowiki> 60 on its return. So this scenario achieves a longer return flight than the others at the cost of necessarily being a return flight. | ||

+ | |||

+ | With four aeroplanes, we can combine the second and third scenarios above. One flight refuels the primary assisting flight at D <nowiki>=</nowiki> 60, which in turn refuels the main flight. The primary assisting flight is then refuelled by a fourth flight at D <nowiki>=</nowiki> 60 on its return. | ||

+ | |||

+ | :Space in main flight's tank <nowiki>=</nowiki> D | ||

+ | :Transferrable fuel from primary assisting flight <nowiki>=</nowiki> 180 - 2(D - 60) (this time we don't have to reserve the 60 units of fuel) | ||

+ | :This simplifies to 300 - 2D | ||

+ | |||

+ | :D <nowiki>=</nowiki> 300 - 2D | ||

+ | :D <nowiki>=</nowiki> 100 | ||

+ | |||

+ | :So the main flight is refueled at D <nowiki>=</nowiki> 100, enabling it to reach 280 degrees non-returning or 140 degrees returning. | ||

+ | |||

+ | Now, 280 is only 80 short of 360 (a complete circumnavigation). Using two aeroplanes, one refueling the other, we can transport 80 units of transferable fuel 80 degrees from base. The second aeroplane, having been refueled at D <nowiki>=</nowiki> 60, travels a further 20 degrees out and must reserve enough fuel for 80 degrees return, leaving 80 units of fuel for the transfer. | ||

+ | |||

+ | We can now piece together a solution. Three assisting flights travel west to enable the main flight to reach D <nowiki>=</nowiki> 280, and two more assisting flights travel east to enable the main flight to get from D <nowiki>=</nowiki> 280 to home. | ||

+ | |||

+ | A more detailed itinery follows. The times (T) are easy to calculate given that the time is always equal to the location of the main flight, and that all flights travel at the same speed. | ||

+ | |||

+ | *At T<nowiki>=</nowiki>0, main flight, westbound primary assisting flight, and 1st westbound secondary assisting flight begin westward journey. | ||

+ | *At T<nowiki>=</nowiki>60, 1st westbound secondary assisting flight refills westbound primary assisting flight at D <nowiki>=</nowiki> 60. | ||

+ | *At T<nowiki>=</nowiki>80, 2nd westbound secondary assisting flight begins westward journey. | ||

+ | *At T<nowiki>=</nowiki>100, westbound primary assisting flight refills main flight at D <nowiki>=</nowiki> 100, giving it enough fuel to reach D <nowiki>=</nowiki> 280. | ||

+ | *At T<nowiki>=</nowiki>120, 1st westbound secondary assisting flight returns to base. | ||

+ | *At T<nowiki>=</nowiki>140, 2nd westbound secondary assisting flight refills returning westbound primary assisting flight at D <nowiki>=</nowiki> 60. | ||

+ | *At T<nowiki>=</nowiki>200, westbound primary assisting flight and 2nd westbound secondary assisting flight return to base. | ||

+ | *At T<nowiki>=</nowiki>200, eastbound primary assisting flight and eastbound secondary assisting flight begin eastward journey. | ||

+ | *At T<nowiki>=</nowiki>260, eastbound secondary assisting flight refills eastbound primary assisting flight at D <nowiki>=</nowiki> 300 (60 from 360). | ||

+ | *At T<nowiki>=</nowiki>280, eastbound primary assisting flight partially refills main flight at D <nowiki>=</nowiki> 280 (80 from 360). | ||

+ | *At T<nowiki>=</nowiki>320, eastbound secondary assisting flight returns to base. | ||

+ | *At T<nowiki>=</nowiki>360, main flight and eastbound primary assisting flight return to base. | ||

+ | |||

+ | This involves a total of six flights: one main, five returning. But by the time the eastbound assisting flights have to depart, the westbound assisting flights have returned to the island. So the same aeroplanes can be re-used for the eastbound assisting flights, reducing the number of aeroplanes needed by two. | ||

+ | |||

+ | Therefore the puzzle can be solved with a total of four aeroplanes, including the main one. But certainly no fewer. Nothing is wasted in the above scenario, which confirms that it is the optimal solution. }} | ||

[[Category: Optimization puzzles]] | [[Category: Optimization puzzles]] | ||

[[Category: Geometry]] | [[Category: Geometry]] |

## Revision as of 06:36, 20 October 2010

A group of airplanes 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 it is assumed that there is no time lost in refueling 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 that the planes have the same constant speed (relative to the ground) and rate of fuel consumption, and that all planes return safely to their island base?

**Solution**

One unassisted aeroplane can travel 180 degrees non-returning, or 90 degrees returning. Let's see how far we can get with two aeroplanes: a main flight and an assisting flight.

- The assisting flight requires fuel for the journey out, fuel for the transfer, and fuel for the return. The best place to transfer fuel to the main flight would be when the amount of fuel available (not needed for return) is exactly the amount of empty space in the main flight's fuel tanks. That way no fuel is wasted.

- Space in tank = D (distance from base, since fuel used equals distance travelled)
- Transferrable fuel = 180 - 2D (starting amount minus what's used for flight out and return)

- Equating these:
- D = 180 - 2D
- D = 60

- So the main flight is refueled at D = 60, enabling it to reach 240 degrees non-returning (the 60 degrees already travelled plus a further 180 on a full tank), or 120 degrees returning (reserve 60 units of fuel for returning the 60 degrees already travelled, which leaves 120 units of fuel for travelling a further 60 units and back).

With three aeroplanes, several scenarios are possible:

- Two assisting flights both transfer fuel to the main flight at different locations on the latter's outward journey, the first at D = 60, the second later.
- One flight transfers fuel to the primary assisting flight at D = 60, which in turn transfers fuel to the main flight.
- Two assisting flights both transfer fuel to a main returning flight at D = 60, one on its flight out, one on its return.

The first two scenarios are equivalent with respect to the optimal distance for the second transfer and the total distance that the main flight can travel. I will skip the first scenario and do the maths for the second.

- Secondary assisting flight transfers fuel to primary assisting flight at D = 60.

- We use the same logic as before to determine the optimal time to transfer fuel from the primary assisting flight to the main flight.

- Space in main flight's tank = D
- Transferrable fuel from primary assisting flight = 180 - 2(D - 60) - 60 (because tank full at D = 60 but need to travel that distance again on return)
- This simplifies to 240 - 2D

- D = 240 - 2D
- D = 80

- So the main flight is refueled at D = 80, enabling it to reach 260 degrees non-returning or 130 degrees returning.

As for the third scenario, the main flight is refueled at D = 60, enabling it to reach 150 degrees returning (90 degrees further than the 60 degrees already travelled), to be refueled again at D = 60 on its return. So this scenario achieves a longer return flight than the others at the cost of necessarily being a return flight.

With four aeroplanes, we can combine the second and third scenarios above. One flight refuels the primary assisting flight at D = 60, which in turn refuels the main flight. The primary assisting flight is then refuelled by a fourth flight at D = 60 on its return.

- Space in main flight's tank = D
- Transferrable fuel from primary assisting flight = 180 - 2(D - 60) (this time we don't have to reserve the 60 units of fuel)
- This simplifies to 300 - 2D

- D = 300 - 2D
- D = 100

- So the main flight is refueled at D = 100, enabling it to reach 280 degrees non-returning or 140 degrees returning.

Now, 280 is only 80 short of 360 (a complete circumnavigation). Using two aeroplanes, one refueling the other, we can transport 80 units of transferable fuel 80 degrees from base. The second aeroplane, having been refueled at D = 60, travels a further 20 degrees out and must reserve enough fuel for 80 degrees return, leaving 80 units of fuel for the transfer.

We can now piece together a solution. Three assisting flights travel west to enable the main flight to reach D = 280, and two more assisting flights travel east to enable the main flight to get from D = 280 to home.

A more detailed itinery follows. The times (T) are easy to calculate given that the time is always equal to the location of the main flight, and that all flights travel at the same speed.

- At T=0, main flight, westbound primary assisting flight, and 1st westbound secondary assisting flight begin westward journey.
- At T=60, 1st westbound secondary assisting flight refills westbound primary assisting flight at D = 60.
- At T=80, 2nd westbound secondary assisting flight begins westward journey.
- At T=100, westbound primary assisting flight refills main flight at D = 100, giving it enough fuel to reach D = 280.
- At T=120, 1st westbound secondary assisting flight returns to base.
- At T=140, 2nd westbound secondary assisting flight refills returning westbound primary assisting flight at D = 60.
- At T=200, westbound primary assisting flight and 2nd westbound secondary assisting flight return to base.
- At T=200, eastbound primary assisting flight and eastbound secondary assisting flight begin eastward journey.
- At T=260, eastbound secondary assisting flight refills eastbound primary assisting flight at D = 300 (60 from 360).
- At T=280, eastbound primary assisting flight partially refills main flight at D = 280 (80 from 360).
- At T=320, eastbound secondary assisting flight returns to base.
- At T=360, main flight and eastbound primary assisting flight return to base.

This involves a total of six flights: one main, five returning. But by the time the eastbound assisting flights have to depart, the westbound assisting flights have returned to the island. So the same aeroplanes can be re-used for the eastbound assisting flights, reducing the number of aeroplanes needed by two.

Therefore the puzzle can be solved with a total of four aeroplanes, including the main one. But certainly no fewer. Nothing is wasted in the above scenario, which confirms that it is the optimal solution.