Brainteasers · Strategy and invariants · Hard
Dates across the desert
A trader has 2,700 dates at an oasis and one camel, and the market is 900 km away along a single road. The camel can carry at most 900 dates at a time. It eats one date for every kilometre it walks, in either direction and whether or not it is loaded, eating steadily from the dates it is carrying, so fractions of a date count, and it cannot move at all without dates to eat. Dates may be left in piles anywhere along the road and collected later, and the camel need not return from the market. What is the largest number of dates that can be delivered to the market?
Answer and solution
Answer
480
Solution
Move the whole pile forward in stages, dropping a trip each time the pile shrinks to a whole number of loads: the cost per kilometre falls from 5 dates to 3 to 1.
With three loads the pile loses 5 dates a kilometre, so after 900/5 = 180 km there are 1,800. With two loads it loses 3 a kilometre, so after another 900/3 = 300 km there are 900, at the 480 km mark. The last load walks the remaining 420 km and arrives with 900 − 420 = 480 dates. No plan does better, because a pile of more than 1,800 cannot advance on fewer than five crossings of each kilometre, nor one of more than 900 on fewer than three.
Strategy and invariants comes up in 3 firms' roundsMillennium · Point72 / Cubist · IMC
These 3 rounds ask this kind of problem live, with follow-ups. Every round on every track is in Premium.