Around the world solution:
(I sort-of understand this, but it's best that I just paste in
a solution straight from the horse's mouth. Looks long and
complicated, though the drawing he gave me is clear enough.)
A little trial and error shows that you need to launch an increasingly large number of planes with the initial takeoff to support the mission as you push the one world-traveling plane out farther and farther. For example, if you divide the trip into five legs, and each leg into thirds, then you can launch 2 planes, let them travel 1/3 of a leg, burning 1/3 tank each, and then transfer 1/3 of one tank to the mission plane. You have delivered the mission plane, with a full tank, 1/15 of the total distance. Launching 4 planes, you can get 2 fully fueled planes to the 1/15 point, and 1 fully fueled plane to the 2/15
point. Its companion turns around and makes it back to the 1/15 point where it would have to be met by resupply planes launched in a second wave -- you can reuse one of the first two, since they have time to make it back to the carrier, refuel, and fly back to meet the returning plane.
So, larger and larger numbers of planes will be needed to provide a support structure for pushing the mission plane out farther and farther. Since, in the example given, the number of planes is doubling with each 1/15 distance flown, a key thing to recognize is that you can minimize the size of the supporting structure by meeting the mission plane as it returns around the other side of the world. The basic approach to the problem then devolves to planning a launch schedule that delivers the mission plane to the 2/5 point, allowing it to fly the far 1/5 alone, and planning a launch schedule to meet the mission plane coming from the other direction with sufficient fuel for return, which, as it turns out, is almost the mirror image of the outbound mission plan.
Now the chief difficulty, and the reason for the inability to conclusively prove that one's solution is minimal, is coping with the continuous nature of the fuel/time/distance aspects of the problem with a discrete number of planes. One way to at least come up with a viable solution is to divide the continuous quantities into discreet units and base the plan around them. For example, we might divide the distance into 25 equal legs, define the fuel required to fly a leg as one unit, equal to 1/5 of a tank, and the time required to fly a leg as one unit.
It's easiest to transform the problem into a two-dimensional network optimization problem, with time as one dimension and distance as the other. Each node of the network represents a point in space/time where planes and fuel may be located. Planes and fuel flow in to and out of these nodes. The network for each half of the mission will appear as a triangle bounded on one side by a diagonal series of nodes that represent the progress of the mission plane and any companions along the flight path. The outbound triangle thus has a diagonal line of nodes that runs from the initial launch time at the carrier out to the point at which it does the solo traversal. Likewise, the inbound triangle has an opposite line that runs from the end of solo traversal to the final landing. A little thought shows that it is never necessary for any planes to be in the air outside of these triangles.
Now we can plan each side of the mission starting from some initial constraint and working backwards to be sure the flows of fuel and planes in to and out of each node are in balance. Taking the outbound side first, start with the mission plane at the tip of the triangle, fully fueled. Now work backwards in both time and space -- what initial conditions would have to be true at the previous node for the final state to be achieved? Clearly the plane could not have reached the tip fully fueled while burning 1/5 of a tank of fuel, so it would have to have a companion plane for that leg. Therefore, there must be at least 2 planes at the tip of the triangle at the time the solo legs are begun. Since the companion cannot be allowed to crash, it must have enough fuel to at least fly back along the other diagonal of the outbound triangle, at least one unit of fuel, or 1/5 of a tank. Thus, at least 2 planes and 6/5 fuel are required to be at that point in space/time. Now we can attempt to work backwards again in time and space; what initial conditions must be true at the previous node? Since 2 planes arrive with 6/5 fuel, we need at least 2 planes with 8/5 fuel at the previous node. And we need 2 planes with 10/5 fuel at the node before that. You can see where this is going now. At the next node back, we need 2 planes with 12/5, an impossible condition, and so we must introduce a third plane, which as always needs to carry off at least 1/5 of a tank to turn back. So you have 3 planes and 11/5 instead of 2 with 10/5, and the previous node would have 3 planes with 14/5 fuel, which, as it turns out, has to be bumped to 4 with 15/5. So it goes, working backward one node at a time, adding planes and fuel as necessary, to the initial launch point. It turns out that something like 22 planes are needed for the initial launch if you've divided space into 25ths. For those who care, 22 planes fly the first leg, then 17, 12, 9, 7, 5, 4, 3, 2, and 2. Indeed, this is another key to the problem -- the finer you subdivide the space, the better your solution gets. You could see that dividing into 15ths was at least doubling the number of planes with each additional leg. 20ths is better, 25ths better still, and 30ths not much better.
Once you've bracketed the outbound and recapture missions with plane/fuel flows, you can work out the rest of the network such that all planes eventually are returned to the carrier. Additional planes need to be continually refueled and relaunched to meet planes that have turned back. And of course you need to plan the recapture mission after the mission plane has flown solo the 5 farthest legs, a rough mirror image of the outbound mission. The number of planes needed to support the mission is then found by counting the number of planes in the air at each moment in time, which is a sum of the planes at all nodes along a given time slice, and then the maximum of these sums is the number of planes needed for the overall mission. |
