Camel and Bananas

A camel is sitting by a stack of 3000 bananas at the edge of a 1000-mile-wide desert. He is going to travel across the desert, carrying as many bananas as he can to the other side. He can carry up to 1000 bananas at any given time, but he eats one banana every mile. What is the maximum number of bananas the camel can get across the desert? How does the camel do it? Be prepared to present your solution to the class.

Hint: The camel doesn't have to go all the way across the desert in one trip.

Answer: Since camel can carry at most 1000 bananas at a time, if it carries all 1000 bananas and travels it will reach the market with zero bananas and cannot came back to fetch the remaining 2000 bananas, so this problem has to be solved by "divide and conquer" technique.

To take 3000 bananas it has to go three times in the direction of market and 2 times towards the stack. That is it has to make 5 trips to carry all bananas from starting point.

P (Stacked Point)

===forth===> <===back==== ===forth===> <===back==== ===forth===>

A

===forth===> <===back==== ===forth===>

B

===forth===>

M (market)

Note that section PA must be in the solution (as explained above), but section AB or section BM might have a length of 0. Let us now look at the costs of each part of the route. One kilometre on section PA costs 5 bananas. One kilometre on section AB costs 3 bananas. One kilometre on section BM costs 1 banana. To save bananas, we should make sure that the length of PA is less than the length of AB and that the length of AB is less than the length of BM. Since PA is greater than 0, we conclude that AB is greater than 0 and that BM is greater than 0.

The camel can carry away at most 2000 bananas from point A. This means the distance between P and A must be chosen such that exactly 2000 bananas arrive in point A. When PA would be chosen smaller, more than 2000 bananas would arrive in A, but the surplus can't be transported further. When PA would be chosen larger, we are losing more bananas to the camel than necessary. Now we can calculate the length of PA: 3000-5*PA=2000, so PA=200 kilometres. Note that this distance is less than 500 kilometres, so the camel can travel back from A to P.

The situation in point B is similar to that in point A. The camel can't transport more than 1000 bananas from point B to the market M. Therefore, the distance between A and B must be chosen such that exactly 1000 bananas arrive in point B. Now we can calculate the length of AB: 2000-3*AB=1000, so AB=333 1/3. Note that this distance is less than 500 kilometres, so the camel can travel back from B to A. It follows that BM=1000-200-333 1/3=466 2/3 kilometres. As a result, the camel arrives at the market with 1000-466 2/3=533 1/3 bananas.