This Riddler puzzle is a simple twist on a classic.
You have a camel and 3,000 bananas. You would like to sell your bananas at the bazaar 1,000 miles away. Your loyal camel can carry at most 1,000 bananas at a time. However, it has an insatiable appetite and quite the nose for bananas — if you have bananas with you, it will demand one banana per mile traveled. In the absence of bananas on his back, it will happily walk as far as needed to get more bananas, loyal beast that it is. What should you do to get the largest number of bananas to the bazaar? What is that number?
Here is my solution.
[Show Solution]
This classic puzzle has appeared in various forms. Camels carrying bananas, monkeys carrying bananas, and even a boy carrying watermelons! In these instances, it costs bananas (or watermelons) for all movement. The twist in the present incarnation of the puzzle is that movement is free if no bananas are being carried.
Suppose we have $1000q+r$ bananas, where $0 \le r < 1000$. For example, with $6548$ bananas, $q=6$ and $r=548$. The key is to realize that moving those bananas will cost at least $q+1$ bananas per mile since the camel can carry at most $1000$ bananas at once, and so must make at least $q+1$ trips. We want to minimize the number of trips required because that will also serve to minimize the number of bananas lost in transit.
The optimal way to transport the bananas is to split the journey into segments. Using the example above, transportation initially costs us $7$ bananas per mile, until we drop to $6000$ bananas. Then, it will cost us $6$ bananas per mile until we drop to $5000$ bananas, and so on. Let’s illustrate how this works for version asked about in the problem: $3000$ bananas that must be carried $1000$ miles.
- our 3000 bananas can be moved at a cost of 3 bananas per mile. Moving them 333.33 miles, we are left with 2000 bananas and 666.66 miles to go.
- our remaining 2000 bananas can be moved at a cost of 2 bananas per mile. We move them 500 miles, so we are left with 1000 bananas and 166.66 miles to go.
- our remaining 1000 bananas can be moved at a cost of 1 banana per mile. We move them the remaining 166.66 miles, which leaves us with 833.33 bananas.
This is the most efficient way to move the bananas. Using this procedure, we also observe that the maximum distance we can travel before losing all our bananas is $333.33+500+1000=1833.33$ miles.
The general case
The above recipe can be extended to the case with $n$ bananas that must be carried a distance $d$. For each $(n,d)$, the plot below shows the maximum number of bananas can be carried to the destination.
The contours are piecewise-linear and approximate logarithmic curves. To understand why this is the case, we can consider $n = 1000q+r$ bananas and ask how far they can be carried. The total distance is:
\[
d_\text{max} = \tfrac{r}{q+1} + \tfrac{1000}{q} + \tfrac{1000}{q-1} + \dots + \tfrac{1000}{2} + \tfrac{1000}{1}
\]The sums of reciprocals $H_m = 1+\frac{1}{2}+\dots+\frac{1}{m}$ are called harmonic numbers. A useful bound involving harmonic numbers is that
\[
\log(m+1) \le H_m \le 1+\log(m)
\]So we can bound:
\[
\log(q+1) \le H_q \le \frac{d_\text{max}}{1000} \le H_{q+1} \le 1+\log(q+1)
\]this explains the logarithmic shape of the top contour. We can also ask about efficiency by dividing the number of bananas carried to the destination by the total number of bananas at the start. This results in the following picture:
If you’re interested in how I produced these images, I used IJulia and you can view the notebook here.
Infinite bananas
One might ask: what happens in the case where we have infinitely many bananas? how efficient can we be then? Based on the plot above, it appears that efficiency is eventually constant. To find the limit, let’s assume we have $n = 1000 k$ bananas. Taking successive steps using our algorithm above until we reach the desired distance $d$, we must:
- go $\tfrac{1000}{k}$ miles (at $k$ bananas/mile); $1000(k-1)$ bananas remaining.
- go $\tfrac{1000}{k-1}$ miles (at $k-1$ bananas/mile); $1000(k-2)$ bananas remaining.
- … and so on, until we have gone $d$ miles.
If it takes us $j$ steps to reach our goal, this means that $j-1$ steps wasn’t enough, but that the $j^\text{th}$ step possibly put us over. An inequality representing this fact is:
\[
H_k-H_{k-j}-\tfrac{1}{k-j}=\sum_{i=1}^{j-1} \tfrac{1}{k-i+1} < \tfrac{d}{1000} \le \sum_{i=1}^{j} \tfrac{1}{k-i+1} = H_k-H_{k-j}
\]where the $H_m$ are the harmonic numbers we discussed earlier. Another useful property of harmonic series is that they grow logarithmically. More precisely,
\[
\lim_{k\to\infty} \left( H_k-\log(k)\right) = \gamma \approx 0.5772
\]where $\gamma$ is known as the Euler-Mascheroni constant. Using properties of limits, this fact implies that for any fixed $j$, we have:
\[
\lim_{k\to\infty} \left[ \left(H_{k-j}-H_{k}\right)-\log\left(\tfrac{k-j}{k}\right) \right] = 0
\]Rearranging our bound on $d$, we can write:
\[
-\tfrac{d}{1000} \le H_{k-j}-H_k \le -\tfrac{d}{1000}+\tfrac{1}{k-j}
\]In the limit, we therefore have:
\[
\lim_{k\to\infty} \left( H_{k-j}-H_k \right) \,=\, \lim_{k\to\infty}\log\left(\tfrac{k-j}{k}\right) \,=\, -\tfrac{d}{1000}
\]Notice that we will have $1000(k-j)$ bananas remaining when we arrive at our destination, and we started with $1000k$. Therefore, $\frac{k-j}{k}$ is precisely the efficiency we are trying to find; the fraction of bananas remaining once we reach our goal. As $k\to\infty$ (infinite banana limit), we obtain
\[
(\text{infinite-banana efficiency}) = \lim_{k\to\infty}\tfrac{k-j}{k} = e^{-d/1000}
\] So, for example, if we must travel a distance $d=1000$, we can expect to keep roughly $1/e \approx 36.79\%$ of our bananas. It turns out that for the case of $3000$ bananas, our efficiency is only about $833.33/3000 \approx 27.78\%$, so there would be plenty of room for improvement if we had more bananas!