The Banana Caravan

Question

You have 3000 bananas to deliver to a market 1000 km away. Your camel carries at most 1000 bananas and eats 1 banana per km walked, loaded or empty. You may cache bananas anywhere along the route. What is the maximum number of bananas you can get to market?

Accepted Answer

533 bananas. Moving a stockpile of n bananas forward 1 km costs 2lceil n/1000rceil - 1 bananas: each camel-load goes forward, and all but the last trip walks back. - Phase 1 (3 loads, 5 crossings/km): burn rate 5/km until the pile hits 2000, that takes frac10005 = 200 km. At km 200: 2000 bananas. - Phase 2 (2 loads, 3 crossings/km): burn 3/km until the pile hits 1000, frac10003 = 333.3 km. After 333 km (km 533): 2000 - 999 = 1001 bananas; abandon the orphan banana. - Phase 3 (single load): carry 1000 the remaining 467 km, eating 1/km: 1000 - 467 = mathbf533. A full dynamic program over every integer cache point and abandonment choice confirms 533 is optimal, the phase strategy isn't just intuitive, it's exact. Why phase-switching at 2000/1000 is right: the marginal cost per km is a step function of the stockpile size; you want to shed trips as early as possible but no earlier than a full load boundary, dropping below 2000 before km 200 would mean having paid 5/km where 3/km sufficed. The continuous-math answer is 533tfrac13 (phase 2 ends at km 533tfrac13); integer caching loses the fraction. Same structure as transport/jeep problems: harmonic-looking phase lengths frac10005, frac10

The Banana Caravan

Problem

Your answer

Hints

More Brainteasers & Logic to train on