Katkat
Back

Camel and Bananas: Maximize Bananas Delivered Across the Desert

StackAdaptMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteStatistics & Math

Last updated

Classic camel-and-bananas brainteaser: a camel that carries at most 1,000 bananas and eats one per kilometer must move 3,000 bananas to a market 1,000 km away. Find the maximum number that can arrive, testing piecewise cost reasoning, depot planning, and a proof of optimality.

A camel has to move bananas from a starting point across a desert to a market. Assume the standard parameters of this classic brainteaser:

  • 3,000 bananas are at the start, and the market is 1,000 km away.
  • The camel can carry at most 1,000 bananas at a time.
  • The camel eats one banana for every kilometer it walks, in either direction, whether or not it is carrying anything.
  • The camel may drop bananas anywhere along the way and pick them up later.

What is the maximum number of bananas that can reach the market? Describe the strategy and argue why no other strategy does better.

Constraints and Clarifications

  • The camel starts at the pile and does not need to come back after reaching the market.
  • Bananas that the camel eats come out of the bananas it is carrying or picks up along the way.

Clarifying Questions

  • May the camel stop, and drop bananas, at fractional kilometers, or only at whole kilometers? The two readings give slightly different answers.
  • Does the camel really eat on the walk back when it carries nothing?
  • Is the goal to maximize the bananas delivered, or also to minimize the number of trips?

Hints

Hint 1

Count the passes: While the pile holds more than one load, moving all of it forward by one kilometer means walking that kilometer several times. How many times, and how does that number change as the pile shrinks?

Follow-up questions

  • Generalize to N bananas, capacity C, and distance D. How far can the camel get before the pile fits in a single load?
  • What is the farthest distance at which the camel can deliver at least one banana?
  • How does the answer change if the camel eats only while carrying bananas?