3000 bananas, one camel, 1000 kilometres.
The camel and bananas puzzle: a camel carries at most 1000 bananas, eats one per kilometre, and must move 3000 bananas across 1000 kilometres of desert. How many arrive? Naive plans deliver zero. The right plan delivers 533, and finding it teaches staged transport.
You own 3000 bananas and one camel, and the market is 1000 kilometres away across desert. The camel can carry at most 1000 bananas at a time, and it eats exactly one banana for every kilometre it walks, loaded or unloaded, in either direction. Bananas can be left in piles anywhere along the route and picked up later; nothing else eats them.
What is the largest number of bananas you can deliver to the market?
Two plans fail instructively. Carry 1000 bananas straight there: the camel eats all 1000 on the way and arrives with nothing. Make three round trips from the start: each trip covers 2000 kilometres of walking on a 1000-banana load, which is impossible. So the answer involves moving the whole stock forward in stages, and the interesting question is how far each stage should go.
Two things to work out before the hints. First, when the camel is shuttling three loads forward across a short stretch, how many kilometres does it actually walk per kilometre of progress? Second, at what point along the route does that number change?
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
To move 3000 bananas one kilometre forward with a 1000 capacity takes three forward trips and two return trips: five kilometres of walking, so five bananas eaten per kilometre of progress.
Hint 2 the key move
Once the stock drops to 2000, only two forward trips and one return are needed: three bananas per kilometre. Once it drops to 1000, a single trip: one banana per kilometre. Work out where each transition happens.
Hint 3 nearly the answer
Stage one ends when 1000 bananas have been eaten at five per kilometre: 200 kilometres in. Stage two ends when another 1000 have gone at three per kilometre. How far is that, and how much desert is left for the final single trip?
The solution
Reveal the full solution
533 bananas.
Move the stock forward in three stages, each with a different shuttle pattern:
- Stage one, 3000 bananas. Shuttling three loads costs five bananas per kilometre. Continue until exactly 1000 have been eaten, which is 200 kilometres in. Stock: 2000.
- Stage two, 2000 bananas. Two loads cost three bananas per kilometre. Continue until another 1000 are gone: 333 and a third kilometres further, at the 533 and a third kilometre mark. Stock: 1000.
- Stage three, 1000 bananas. One trip, one banana per kilometre, over the remaining 466 and two thirds kilometres. Arrive with 533 and a third.
Since a banana cannot be split at the market, 533 is the deliverable answer. The fractional distances are real, not a rounding artefact: the optimal depot positions are at 200 and 533.3 kilometres, and stopping stage one early or late costs bananas, because you would be paying the five-per-kilometre rate on ground where the cheaper three-per-kilometre rate was available, or vice versa.
Why is this optimal? At any point, the cost per kilometre of progress is determined by how many loads are in play, and that number can only be reduced by consuming bananas. So the total cost is fixed by the sequence of stock thresholds: 1000 bananas to bring the stock from 3000 to 2000, 1000 more from 2000 to 1000, and then the remaining distance at unit cost. Any plan pays those same amounts in some order; the staged plan pays them at the cheapest available rate throughout. An exchange argument, moving a kilometre of shuttling from a high-rate stretch to a lower-rate one, shows any deviation loses.
What this puzzle is really testing
Marginal cost reasoning. The question "how far should the first depot be" has a clean answer only once you see that cost per kilometre is piecewise constant and drops at fixed stock levels. That is a rate argument, the same style used to reason about amortised cost in hash table resizing, where an expensive operation is paid for gradually by cheap ones. The "why can't we do better" half is an exchange argument, the tool that also justifies correct greedy algorithms and appears in the bridge and torch puzzle.
Follow-ups to expect
The general formula for any stock, capacity, and distance, which iterates the same stage logic and is a pleasant exercise to code. What if the camel eats only when loaded? Then returns are free and the answer changes substantially. And the rocket-equation cousin: fuel that must carry its own fuel obeys the same staging logic, which is why real rockets drop empty tanks.