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:

1. Pick up 1000 bananas.
2. Carry them one mile into the desert, eating one on the way.
3. Keep one of the bananas for the trip back.
4. Repeat steps (1-3).
5. 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:

1. Pick up 1000 bananas.
2. Carry them N miles into the desert, eating N on the way.
3. Keep N of the bananas for the trip back.
4. Repeat steps (1-3).
5. 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:

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

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

3. 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:

Crossing a Desert with 45 Watermelons
Crossing the Desert
Minimum Number of Trips
Monkeys in the Jungle