Friday, October 7, 2011

Camel and Banana

Problem : 

The owner of a banana plantation has a camel. He wants to transport his 3000 bananas to the market, which is located after the desert. The distance between his banana plantation and the market is about 1000 kilometer. So he decided to take his camel to carry the bananas. The camel can carry at the maximum of 1000 bananas at a time, and it eats one banana for every kilometer it travels.

What is the largest number of bananas that can be delivered to the market?

Solution :

A camel cannot go  to market directly. This is because the camel can never travel more than 500 kilometres into the desert if it should return to the plantation (the camel eats a banana every kilometre it travels!). So there lies point A somewhere in the desert between the plantation and the market such that it returns back and pick up banannas:
<---p1---><--------p2-----><-----p3---->
P---------------------------------------->M




P (plantation)

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


A

 

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


B

 


===forth===>

 


M (market)

 

 Since there are 3000 bananas and camel can only carry 1000 bananas, Camel will have to make 3 trips to carry them all to any point in between.


When bananas are reduced to 2000 then Camel can shift them to another point in 2 trips and when the number of bananas left are <= 1000, then he should not return and only move forward.

In the first part, P1, to shift the bananas by 1Km Camel will have to

1. Move forward with 1000 bananas – Will eat up 1 banana in the way forward
2. Leave 998 banana after 1 km and return with 1 banana – will eat up 1 banana in the way back
3. Pick up the next 1000 bananas and move forward – Will eat up 1 banana in the way forward
4. Leave 998 banana after 1 km and return with 1 banana - will eat up 1 banana in the way back
5. Will carry the last 1000 bananas from point a and move forward – will eat up 1 banana

Note: After point 5 the camel does not need to return to point A again.

At KM#0, we have 3000 bananas. The maximum bananas the camel can carry is 1000 so the camel must at least make 3 trips from the start point. (Leave #0, Return to #0, Leave #0, Return to #0, Leave #0).
If we move just 1km, we need 1 banana for each step mentioned above thus making a total of 5 bananas for each km.
So to shift 3000 bananas by 1km Camel will eat up 5 bananas.

After moving to 200 km the camel would have eaten up 1000 bananas and is now left with 2000 bananas.

Hence the length of part P1 is 200 Km.

Now in the Part P2, the Camel need to do the following to shift the Bananas by 1km.

1. Move forward with 1000 bananas - Will eat up 1 banana in the way forward
2. Leave 998 banana after 1 km and return with 1 banana - will eat up this 1 banana in the way back
3. Pick up the next 1000 bananas and move forward - Will eat up 1 banana in the way forward

Note: After point 3 the camel does not need to return to the starting point of P2.
At #200km, we will have 2000 bananas
At this point, we only need to make 2 trips (Leave #200, Return to #200, Leave #200). This will cost 1 banana for each step thus making a total of 3 bananas for each km.

So to shift 2000 bananas by 1km Camel will eat up 3 bananas.

After moving to 333 km the camel would have eaten up 1000 bananas and is now left with the last 1000 bananas.

The camel will actually be able to cover 333.33 km, I have ignored the decimal part because it will not make a difference in this example.

Hence the length of part P2 is 333 Km.

Now, for the last part, P3, the Camel only has to move forward. He has already covered 533 (200+333) out of 1000 km in Parts P1 & P2. Now he has to cover only 467 km and he has 1000 bananas.

He will eat up 467 bananas on the way forward, and at point B the Camel will be left with only 533 Bananas. 

0 comments:

Post a Comment