# Difference between revisions of "Around the world"

(10 intermediate revisions by 5 users not shown) | |||

Line 1: | Line 1: | ||

+ | [[File:Airplane Silhouette R.svg|right|150px]] | ||

+ | |||

+ | ==Puzzle== | ||

+ | |||

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. | + | {{Solution | [Update: I (User:Zerrakhi) have since learned that the following solution is wrong. There is a better and simpler solution that uses only three aircraft and relies on a step that I missed. But I don't have the heart to delete all my hard work.] |

+ | |||

+ | 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. | 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. | ||

Line 55: | Line 61: | ||

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. | 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, | + | *At T<nowiki>=</nowiki>0, main flight, western primary assisting flight, and 1st western secondary assisting flight begin westward journey. |

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

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

− | *At T<nowiki>=</nowiki>100, | + | *At T<nowiki>=</nowiki>100, western 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 | + | *At T<nowiki>=</nowiki>120, 1st western secondary assisting flight returns to base. |

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

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

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

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

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

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

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

+ | |||

+ | This involves a total of six flights: one main, five returning. But by the time the eastern assisting flights have to depart, the western assisting flights have returned to the island. So the same aeroplanes can be re-used for the eastern 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. | ||

− | + | --- | |

− | + | Here is a solution involving only three planes, including the one around the world (call this one the "main plane"). Two planes (Plane 1 and Plane 2) escort the main plane, all fully fueled. At 1/8 of the way around the world, Plane 1 fills up Plane 2 and the main plane, then returns to the island. At 1/4 of the way, Plane 2 fills up the main plane and returns to the island. At half way around, Plane 1, fully fueled, takes off again, now in the opposite direction as previously. When it meets the main plane, which is now 3/4 of the way around the world, Plane 1 gives the main plane 1/4 of a tank. They both fly toward the island, and a fully fueled Plane 2 leaves the island, flying toward them. Halfway through their return (so the main plane is now 7/8 the way around the world), Plane 2 meets them and gives each 1/4 of a tank. All three planes can now safely return to the island.}} | |

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

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

## Current revision as of 15:40, 24 January 2021

## Puzzle

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

This involves a total of six flights: one main, five returning. But by the time the eastern assisting flights have to depart, the western assisting flights have returned to the island. So the same aeroplanes can be re-used for the eastern 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.

---

Here is a solution involving only three planes, including the one around the world (call this one the "main plane"). Two planes (Plane 1 and Plane 2) escort the main plane, all fully fueled. At 1/8 of the way around the world, Plane 1 fills up Plane 2 and the main plane, then returns to the island. At 1/4 of the way, Plane 2 fills up the main plane and returns to the island. At half way around, Plane 1, fully fueled, takes off again, now in the opposite direction as previously. When it meets the main plane, which is now 3/4 of the way around the world, Plane 1 gives the main plane 1/4 of a tank. They both fly toward the island, and a fully fueled Plane 2 leaves the island, flying toward them. Halfway through their return (so the main plane is now 7/8 the way around the world), Plane 2 meets them and gives each 1/4 of a tank. All three planes can now safely return to the island.