mathematics - A camel transporting bananas

A somewhat well-known puzzle is described as such:

You have a pile of 3,000 bananas. You wish to transport them to a place 1,000 miles away on the back of a camel; however, the camel can only carry a maximum of 1,000 bananas, and will eat one banana every mile it travels (and will not go anywhere if it does not have any bananas). However, you can load and unload as many bananas as you want anywhere. What is the most bananas you can bring over to your destination?

Obviously you can't just load up 1,000 bananas and go, because the camel will have eaten them all by the time you get there.

I'd never figured out the answer by myself before. Does anybody have any insights into how to solve this problem and other problems like it?

Answer

Solution for $n$ bananas, where $n$ is the number of bananas you own, and $c$ is the number of bananas the camel can carry:

- For bananas $0 \rightarrow c$ the cost to move a banana is $1$ banana per mile.
- For bananas $c+1 \rightarrow 2c$, the cost to move a banana is $3$ bananas per mile.
- For bananas $2c+1 \rightarrow 3c$, the cost to move a banana is $5$ bananas per mile.
- etc.

This is because, if the camel moves the bananas 1 mile at a time, he needs to make two trips for each load beyond his current capacity.

Define $t = \lfloor\frac{n}{c}\rfloor$ Therefore, the total number of miles the camel can reach is:

$$\left(\sum_{k=1}^{t} \frac{c}{2k - 1}\right) + \frac{(n \bmod c)}{2t+1}$$

In particular, plugging in the given $n = 3000$ and $c = 1000$, we have that the camel can travel

$$1000 + 333 + 200 = 1533 \text{ miles}$$

To figure out how many bananas remain for a given distance,

Subtract the extra miles and multiply back at the rate given above.

For the first $1000$ miles, this number is just the distance beyond the total capacity:

$1533 - 1000 = 533$, or 533 bananas.