Riddle
Trans-Kaua'i Flight
Mr. Doofus is on vacation in Hawaii, enjoying the island of Kaua'i. He wishes to fly from one end of the island to the other.
- The island is approximately 100 miles long, but he can only manufacture planes that carry enough fuel to fly for 75 miles.
- Any plane can refuel another plane midair, instanteously.
- No airports on Kaua'i, other than those at the starting and end points, will allow Mr. Doofus's custom aircraft to land.
- No plane is allowed to run out of fuel midair and thus crash.
He is willing to construct airplanes for any friend willing to help him.
a. How many friends, at minimum, does he need to complete his trans-Kaua'i flight? How will his friends help him survive the flight across Kaua'i?
b. Say Mr. Doofus has made gross miscalculations, and he realizes all of his planes have only enough fuel to fly 50 miles; how many friends does he need now? How will they help? Hint: Consider the farthest 2 airplanes together can go. Then, consider 3 airplanes, then 4 etc.
Credits: This was inspired in part by Judd A. Schorr's puzzle on TED-Ed.
Solution
a. How many friends?
1
a. How will they help?
For simplicity, say each plane uses 1 gallon of fuel per mile. Since each plane can fly 75 miles, each plane can hold 75 liters of fuel. Here is the plan:
-
Both planes, P1 and P2, takeoff together and will fly 25 miles. At this point, P1 and P2 have both used 25 liters and have 50 liters left. P1 transfers 25 liters to P2--P1 has 25 liters remaining, enough for a trip back to the starting point. P2 now has a full tank, at 75 liters.
-
P1 flies back to the starting point. P2 completes the trip, flying the remaining 75 miles to the other end of Kaua'i.
The below responses were suggested by Zijin Cui on August 12, 2019. I have left my original answer below that.
b. How many friends?
Exponentially many. If we allow planes to take off from the destination, 5.
b. How will they help?
We can mimic an airport that's 50/3 miles away from another airport (A) using however many planes that take off(X) plus the number of planes that return(Y) to the mimic airport(A'). First, 2X planes will take off from A and at the 50/3 mile point, X planes each dump 50/3 of fuel to the other X planes, thus the other X planes would continue from the 50/3 point(A') as if they took from there with full fuel. As for Y of the X planes that return to A', we schedule Y planes from A just in time to catch Y planes that return to A' out of fuel and refill them with 50/3 of fuel and return together.
Since all finite distances are within finite multiples of 50/3, we could always make a finite amount of mimick airports to boost you to the other end.
Do notice that if the mimick airports are all clumped at one end, the amount of friend planes we need grows exponentially. But we can optimize by creating a mimick airport on the other end to "catch" us we run out of fuel.
This is my strategy for the 100-mile trip:
Create three mimick ports, stack two on starting end and one on ending end. You and three friends take off together, friends 1 and 2 dump to you and 3 at port one and returns, friend 3 dumps and returns at port two leaving you with 50 miles of fuel from 100/3 point. Schedule the fourth friend plane on starting port to catch friend 3 at 50/3 mile point. Schedule friend 5 to dump 50/3 of fuel to you when you reach mimick port on the other end after 50 miles of solo flight and return with friend 5 to the end port.
The below were my original answers. They're embarassing, but I will leave them here so you can learn from my mistakes. Oops!
b. (Old) How many friends?
Infinity
b. (Old) How will they help?
Say there are 2 airplanes. How do we maximize the distance that both airplanes together can travel? We know that at some point the first airplane will need to transfer fuel to the second airplane. Say both airplanes travel just a small amount, before the first airplane transfers fuel and turns back. The first plane will land at the starting point with tons of excess fuel. So, let the first airplane fly a bit farther. This time, both airplanes travel farther, before the first airplane transfers fuel and turns back. The first airplane will land at the starting point with a bit less excess fuel, and the second airplane will be able to fly farther. Again, let the first airplane fly a bit farther, and repeat the process. Continue iteratively, so that the first airplane flies farther, and farther, and farther... We continue this process until the first airplane has just enough fuel to return to the starting point, after it transfers fuel to the second airplane. In other words, the first airplane's goal should be to maximize the distance it can travel, before refueling the second airplane fully. In English, let us rephrase our constraint: the amount of fuel the first airplane can spare, must be equal to the amount of fuel that the other airplane has used.
Let us call this distance $x$. For simplicity, consider a fuel tank of 1 to be "full". Also, consider the distance that one airplane can fly to be 1. The amount of fuel the first airplane can spare is its total fuel ($1$) minus the amount it has used ($x$) and minus the amount it needs to return to the starting point ($x$).
$$1-x-x$$
The amount of the fuel the other airplane has used is simply $x$. Thus,
$$1-x-x = x$$ $$1 = 3x$$ $$x = \frac{1}{3}$$
Let's double check this makes sense: At $x=\frac{1}{3}$, the first airplane has $\frac{2}{3}$ fuel left. It transfers $\frac{1}{3}$ fuel to the second airplane, leaving itself $\frac{1}{3}$ fuel, enough to return home; at this point, the second airplane has a full fuel tank. As a result, the second airplane can travel an additional distance of 1, after the first plane turns back at $x=\frac{1}{3}$. Thus, the two airplanes together can fly $\frac{4}{3}$ the distance that one airplane alone could have. Note we subconsciously (or consciously) applied this to solving part a: in part a, each airplane could fly up to 75 miles, so the total distance needed of 100 miles was the very farthest that two airplanes together could fly!
Let's now consider 3 airplanes. We know the setup for the first airplane turning back: the amount the first airplane can spare stays the same ($1-x-x$), but there are now 2 airplanes to refuel, each of which has used $x$ fuel, for a total of $2x$ fuel needed. So,
$$1-x-x = 2x$$ $$1=4x$$ $$x=\frac{1}{4}$$
The first airplane contributes a distance of $\frac{1}{4}$. At $x=\frac{1}{4}$, it's as though the remaining 2 planes have just taken off with full fuel tanks. As a result, we can pose almost the same formulation, where $x$ is the distance that both airplanes will need to travel together. Although, it comes with a caveat: the second airplane will need $x + \frac{1}{4}$ of fuel to return to the starting point. As a result, the amount that the second airplane can spare is the full fuel tank ($1$) minus the amount its used ($x$) minus the amount it needs to return to the start point ($x + \frac{1}{4}$).
$$1-x-x-\frac{1}{4}$$
There is only one plane left to refuel, so we have
$$1-x-x-\frac{1}{4} = x$$ $$\frac{3}{4} = 3x$$ $$x = \frac{1}{4}$$
The second airplane contributes a distance of $\frac{1}{4}$, just like the first airplane. Coincidence?
Theorem: With $n$ airplanes, each airplane can contribute another $\frac{1}{n+1}$ to the total distance.
Let us denote the distance the $i$th plane contributes as $d(i)$.
- Base Case: $d(0) = \frac{1}{n+1}$ Given $n$ total airplanes, we know the first airplane to turn back can spare $1-x-x$ and needs to refuel $n-1$ other airplanes. Thus, $1-x-x = (n-1)x \implies x = \frac{1}{n+1}$
- Inductive Hypothesis: Assume $d(i) = \frac{1}{n+1}$.
- Inductive Step: Since the $i$th plane contributes $\frac{1}{n+1}$, the $i+1$th plane needs to travel $\frac{i}{n+1}$ to return back to the starting point and must refuel $n-i-1$ other airplanes, each of which has traveled $x$ distance. Thus,
$$1-x-x-\frac{i}{n+1} = (n-i-1)x$$ $$1-\frac{i}{n+1} = (n-i+1)x$$ $$\frac{n-i+1}{n+1} = (n-i+1)x$$ $$x = \frac{1}{n+1}$$
Thus, each airplane contributes $\frac{1}{n+1}$. ($\forall i, d(i) = \frac{1}{n+1}$) In light of this theorem, we know that the other $n-1$ planes contribute a total of $\frac{n-1}{n+1}$ distance. Thus, the total distance the $n$ airplanes can travel is $1+\frac{n-1}{n+1}$. Note that the limit as $n$ tends to infinity is 2.
Back to the original riddle, recall that each airplane can only travel 50 miles. The total needed distance is 100 miles, which is double the length that a single airplane can travel. Noting the limiting behavior above, Mr. Doofus thus needs an infinite number of friends.