A camel must travel 1000 miles across a desert to the
nearest city. She has 3000 bananas but can only carry 1000 at a
time. For every mile she walks, she needs to eat a banana. What is the
maximum number of bananas she can transport to the city?

Let's begin by imagining *how* the camel might get the bananas
across the desert. If she starts off with 1000 bananas and carries
them 1000 miles, she won't be able to return for the rest of them
because she won't have any bananas to fuel her trip back. She won't
have any bananas to give to her friends either, because she will have
eaten them all during the journey. This suggests that the camel needs
to cache piles of bananas at certain points in the desert so she can
actually move some of them instead of using them all for fuel.

Suppose the camel does this:

- Pick up 1000 bananas.
- Carry them one mile into the desert, eating one on the way.
- Keep one of the bananas for the trip back.
- Repeat steps (1-3).
- Repeat steps (1-2).

At the end of this, there will be 2995 bananas, which are 999 miles
from the city. The camel will also be 999 miles from the city.
So in effect, she now has a smaller version of the same problem. Of
course, it cost her 5 bananas to move the rest a mile. If she keeps this
up, she won't have any bananas left when she gets to the city.

However, at this point, she *can* pick up 1000 bananas,
eat 999 on the way to the city, and have 1 left over when she
gets there. It's not nothing, but it's hard not to think that
she could do better. And she still won't be able to go back
for the 1995 bananas that she left behind.

Can we generalize the strategy? Suppose she does this:

- Pick up 1000 bananas.
- Carry them N miles into the desert, eating N on the way.
- Keep N of the bananas for the trip back.
- Repeat steps (1-3).
- Repeat steps (1-2).

Again, she ends up with a smaller version of the problem. Now she has
(3000-5N) bananas, and is (1000-N) miles from the city.
At this
point, we might ask a few questions:

- If she simply repeats this strategy,
what value of N would allow her to get the most uneaten
bananas to the city?

- Would she have to repeat the strategy exactly? For example,
at some point, she might get down to 2000 bananas. Then
it would only cost her 3N bananas (rather than 5N) to move
the rest N miles.

- Should she always pick up 1000 bananas when she wants to
move some of them farther into the desert? Could there be
an advantage to making more trips with smaller loads?
Could there be an advantage to leaving some of the bananas
at the starting point, and ignoring them completely?

Subtleties like this are what make the problem so frustrating... and
so interesting.
Of course, there are other ways to approach the problem. You might
want to look at the hints given for other similar problems in our
archives: