Camels and Bananas
Read the classic problem
This year’s harvest from a small, remote banana plantation consists of 3,000 bananas. The farmer’s camel can carry up to 1,000 bananas at a time. The marketplace where the bananas are sold is 1,000 miles away. Unfortunately, the camel eats one banana each and every mile she walks.
Of the 3,000 bananas harvested, what is the greatest number the farmer can get to market?
Recently recirculated by Thorne Wolf on X.
Parameters
It delivers 533 bananas after consuming 2,466 and leaving 1 banana behind.
Bananas remaining along the route
The graph shows how many bananas remain after all the loads have been consolidated at that distance.
The price of advancing one mile
The camel must walk forward once per load and return after every load except the last.
Phases of the optimal route
Phases are separated by when another full load is no longer needed.
| Phase | Route miles | Loads | Crossings per mile | Bananas per mile | Bananas remaining |
|---|
When is the extra load worth carrying?
Not always. Let r be the bananas in the partial load above the next capacity threshold. Keeping that load adds one forward crossing and one return crossing, so its marginal cost is 2c bananas per route mile—not the full cost of moving every load.
After 142 miles, 3,006 remain, so r = 6. Keeping the fourth load costs only 2 extra bananas compared with using three loads. Since 6 > 2, moving all four loads one more mile leaves 2,999 at mile 143 and ultimately delivers 676.
At mile 533, 1,001 remain, so r = 1. Keeping the second load would cost 2 extra bananas. Since 1 < 2, leaving that banana behind and continuing with one load ultimately delivers 533.
Rounding only the final answer is not always valid. With 2,002 bananas, capacity 1,000, consumption 1, and a market one mile away, the continuous model gives 1,998.2. But either whole-mile choice leaves 1,997: three loads consume 5, while discarding 2 bananas and using two loads consumes 3. The load count must therefore be re-evaluated at each mile.
General solution
Bₓ: bananas at mile x · C: carrying capacity · c: consumption per camel-mile · n: the number of loads chosen for the next mile
How this formula works
- Begin at mile x. Bₓ is the number of bananas currently available there.
- Consider every feasible load count. The camel may use anywhere from one load up to ⌈Bₓ/C⌉ loads.
- Choose how many bananas to keep moving. With n loads, the camel can move at most nC bananas. That is why the expression uses min(Bₓ, nC); any excess is left behind.
- Calculate the cost of one route mile. Moving n loads requires n forward crossings and n − 1 returns. The camel therefore walks 2n − 1 miles and eats c(2n − 1) bananas.
- Keep the best choice. Subtract that cost from the bananas being moved, then take the maximum across all feasible values of n. The outer max with zero handles cases where the camel cannot advance another complete mile.
- Repeat until mile D. The recurrence produces B₁, B₂, and so on. At the market, round down BD because only whole bananas can be delivered.
Why a one-mile choice gives the global optimum: every option ends at the same next mile. A state with more bananas can always reproduce any plan available to a state with fewer bananas, discarding extras if necessary. So maximizing the bananas after each mile cannot make a later result worse.
What about the camel?
At 20 miles per day, this plan requires roughly 123 days of walking—before rest, weather, loading, or maintaining roadside caches.
San Diego Zoo Wildlife Alliance says a loaded camel can walk about 20 miles per day in harsh desert conditions.
Assumptions and limitations
- The camel may leave and retrieve roadside caches anywhere along the route.
- It eats at the same rate on loaded forward trips and return trips.
- No return trip is required after the final load reaches the market.
- Loading time, rest, water, spoilage, theft, and the camel’s entirely reasonable objections are ignored.