Medium

Logic

Alvin Wan

May 23, 2018

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:

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

  2. P1 flies back to the starting point. P2 completes the trip, flying the remaining 75 miles to the other end of Kaua'i.

b. How many friends?

Infinity

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

Back to all Riddles