The Elephant and the Bananas
This is a level 3 question which should take approx. 8 minute in the interview
A banana merchant has a stock of 3,000 bananas that he would like to sell at the market of an oasis situated 1,000 kilometers away. To carry the merchandise he has an elephant that consumes one banana per kilometer and cannot carry more than 1,000 bananas at once.
At most, how many bananas can he transport to the oasis?
(First off, we notice that if the merchant does the trip without stopping, loading up his elephant as much as possible, he will arrive at the oasis with no bananas. It is thus necessary to make stops: the idea is to drop off some merchandise on the way, come back to pick up more bananas, and then pick up the bananas left on the way. Note, we ask not only for an optimal strategy, but also the proof of its optimality)
Try to solve this problem yourself before moving on to the solution below. Use hint if needed
.
.
.
.
.
Hint
The answer is 533 bananas. The hardest part is proving one can’t do better.
.
.
.
.
Solution
The elephant can carry at most 533 bananas to the oasis. There are several possible strategies.
The elephant carries as many bananas as possible, kilometer by kilometer. It starts from kilometer 0 with 1,000 bananas on its back, and arrives at the first kilometer with 999, drops 998 off, and then returns to the start with the last banana. It does this again and drops off 998 at the first kilometer once more. Finally, it returns to pick up the last 1,000 bananas and drops 999 off at the first kilometer mark. All in all, the elephant ate five bananas to carry 998 2 + 999 = 2,995 bananas the first kilometer. It starts over now and carries 2,990 bananas to the second kilometer mark. For each kilometer, the elephant consumes five bananas to carry all the others. The elephant continues in this way until the 200th kilometer, to which it brings 2,000 bananas. It leaves the 200th kilometer with 1,000 bananas on its back, drops 998 off at the 201st kilometer, keeping one for the trip back. It takes the last 1,000 bananas and drops 999 off at the 201st kilometer. All in all, the elephant ate three bananas to carry 998 + 999 = 1,997 bananas from the 200th kilometer to the 201st kilometer. It continues and carries 1,994 bananas to the 202nd kilometer. It consumes three bananas for each kilometer to carry the rest and continues in this way until it reaches the 503rd kilometer with 1,001 bananas. It then leaves behind one banana and leaves directly for the oasis with the 1,000 bananas remaining. It arrives 467 kilometers later with 533 bananas.
.
.
😃 Your turn: Managed to crack this one?
👉 If you enjoyed this post, please consider leaving a like ❤️. Your support boosts visibility on Substack, helping more readers find this newsletter. Just hit the button at the bottom of this email.
👉 If you're loving this newsletter, why not share it with your friends? They might enjoy it too!