Planes around the world puzzle
There is an airport on a small island, where all planes are identical. The tank of each plane holds enough fuel to take it exactly halfway around the world. Planes can refuel at the airport, and any desired amount of fuel can be transferred instantaneously from the tank of one plane to the tank of another midflight. These planes can also turn around instantly, without any loss of fuel. What is the smallest number of planes that will ensure the flight of one plane around the world on a great circle, assuming all planes return safely to their island base?
Here's the solution.
Here's one way of extending this problem: Suppose that instead of thinking about the plane as going halfway around, we think about distances in terms of full tanks. So our original problem could be considered as asking how many planes it would take for one to travel 2 full tanks long. Now we can instead ask how far p planes could travel.
If we have just 1 plane, then the answer is obvious. 1 plane can travel a distance of 1 full tank.
Given 2 planes, the problem becomes much harder. After considering this problem for a bit, you'll find the difficulty is determining the distance that both planes must travel before one transfers a fraction of its fuel before returning to the airport. But it doesn't take long to see that the distance it would travel forward is equal to the amount of fuel that it could transfer, which is again equal to the distance it would travel back. Thus, the distance it would travel before transferring its fuel must be 1/3. After the first plane has returned to the airport, it should refuel instantly. It can then meet the other plane, at a distance of 1 1/3. This allows the plane which ran out of fuel to get another 1/3 of a tank in distance, after which, both planes return to the airport. Thus, the furthest 2 planes can travel is 1 2/3.
What about 3 planes? Again, after a bit of play, you'll see that it's best to send all 3 planes out initially. But now we have a choice on which planes will transfer fuel, and how much. Let's consider the easiest choice first: Using the same strategy as we used when we had only 2 planes, we'll send 2 of our 3 planes 2/5 of the way. The third plane will travel 1 2/5 before needing fuel again. What if we instead used 1 plane to refuel the other two? This plane would travel 1/4 of the way before transferring and returning to the airport. This situation is more complicated, because the second plane to transfer fuel has already travelled 1/4, but now has a full tank. We can represent the distance it should travel as 1/4 + 3d = 1, and thus, d = 1/4. Following this strategy, the last plane can travel 1 1/2 before refueling.
What about the way back? We can do the same thing as before, but in reverse order. That is, start by sending out one of the planes. This will meet the plane which has travelled the furthest, give it some fuel, then meet the other plane which has just departed, then all three planes will return to the airport simultaneously, just as they left simultaneously. We know the last plane will go 1/4 of a tank before refueling the other two. Following the typical pattern we've established, that means the other plane will travel 1/2 of a tank to meet the plane that has just travelled 1 1/2 tanks in distance. Thus, the maximum distance that can be travelled by 3 planes is 2 tanks. Now that you understand the reasoning, extend this pattern to p planes. In all the examples we've seen so far, the strategy was to transfer fuel in a sort of cascading pattern. In our last example, we had 3 planes moving forward, then 2, then 1. Can you prove this strategy is always optimal?