Classic Camel Banana Puzzle

Problem Statement

You are standing in desert with camel and 3000 bananas. You have to transport these bananas using camel from point A to point B. Distance between points is 1000 Kms. Camel can take 1000 bananas at a time and also you have to feed him one banana per km. Now you have to find the way to transport highest number of bananas from point A to point B. You can store bananas between point A and B anywhere.

If you want to try out solution your self read next lined after you tried to solve it.



Here is the approach toward the solution.

First thought

Lets try to transport all 1000 bananas from point A to point B. If camel travels from point A to point B you will be left with no banana as you have to feed camel 1000 bananas for travel of 1000 kms. Also there is no way you can take camel back to point A as there is no banana. :)

If camel travels half of distance ie 500 kms and return back to point A. In this case camel will eat 500 banana when he reached at the middle and you have to carry 500 bananas back to point A so that camel can be feed while he is returning back. So you will reach at point A with out any banana out of 10000.

Divide the route

Let divide the route between A to B in three parts of 333 Kms,333 Kms and 334 Kms. Now camel will start from point A with 1000 bananas and will unload after travelling 333 Kms (Say point C). In this case camel will reach to this point with (1000-333) 667 bananas. For travelling back he needs 333 bananas so only 334 (667-333) bananas can be stored at point C. Now let's repeat same step again after reaching point A till there is no banana at point A. In this case camel has to travel

A->C 333 Kms
C->A 333 Kms
Bananas at point A = 2000
Bananas at point C = 334
A->C 333 Kms
C->A 333 Kms
Bananas at point A = 1000
Bananas at point C = 668
A->C 333 Kms
Bananas at point A = 0
Bananas at point C = 668+(1000-333) = 1335

Ok We reach at point C (333 Kms from point A and 667 Kms from point B) with 1335 bananas. Let's move ahead from point C to 333 Kms (Say point D) with 1000 bananas. Now we have 1000-333 = 667 bananas when reached at point D. Now we have to decide to go back to C to get rest 335 bananas from point C or go ahead to point B.

Say let's move to point C from point D so we will unload 667-333 = 334 bananas at point D. After reaching point C we will pick 335 bananas and will reach at point D with 2 bananas so we have 336 bananas at point D. so if we move from point D to point B we will reach with only 2 bananas (336-334=2)

Here is travel plan between C to D
C->D 333 Kms
D->C 333 Kms
Bananas at point C = 335
Bananas at point D = 334
C->D 333 Kms
Bananas at point C = 0
Bananas at point D = 334 + (335-333) = 336

In case if we decide not to go back to point C then we will reach point B from point D with 333 bananas at hand.
C->D 333 Kms
D->B 334 Kms
Bananas at point C = 335
Bananas at point D = 0
Bananas at point B = 333

Did you notice
From point A to point C we have to travel 333*5 Kms (A->C, C->A, A->C, C->A, A->C)
From point C to pint D we have to travel 333*3 Kms (C->D, D->C, C->D)
From point D to pont B we have to travel 334*1 Kms (D->B)

Approach toward solution

To reach with maximum bananas to point B we should have to travel less because travel cost you one banana per km. We have to find point C and D such that distance between A to C is less and distanace between D to B is more.

Let's move step by step. One kms in one time. From point A to one km towards B and store 998 banans at this place and come back to point A to move next 1000 banans. This way we can move 998+998+999(3000-5) bananas. This process we have ro repeat till we have left with 2000 bananas. So we can travel 200 Kms from point A towards B by consuming 1000 bananas. so point C will be at 200 Kms from point A.

We reach point C with 2000 bananas.No we have to travel to point D. Our target to reach point D with 1000 bananas. We have to make 3 trips between point C and D to transport 2000 banans. So camel will consume 1000 bananas in 3 trips between C and D. D will be at distance 333.33 Kms from C. As we are not cutting any banana so let's put D at 333 Kms from C. Camel will consume 999 bananas between C and D and we will reach with 1001 bananas at point D.


Now we have to left one banana at point D. Sad but this we have to do to ensure that we do not make another trip. D is at 1000-200-333 = 467 Kms from B so camel will consume 467 bananas while travelling point D to B leaving us to transport 533(1000-467) bananas.


So the idea is find point C and D such that A to C camel will travel 5 times, C to D camel will travel 3 times and D to B camel will travel 1 time. We have to find C and D such that we can reduce the travel.


Solution
533 Bananas


Similar puzzle

What if distance from point A to point B is same 1000 kms but you have to transport 5000 banans. So in this case how much you can transport?

Classic 2 Egg Problem

Problem Statement

You are given 2 identical eggs. You are standing before 100 storey building. Eggs are so hard that they can be broken only above certain floor. You have to find the floor above which eggs break (Highest floor from which egg can be dropped without breaking) in minimal number of attempts.

Easy Approach

Binary Divide - Reduce Problem Space by 2

Easy way to think the solution is "Binary Division". Let's divide the problem space of 100 floors into two 50 floor problem spaces. Start dropping the first egg at the middle floor (50th floor). In case egg is broken you know that highest floor from which egg can be dropped without breaking it is one of bottom 50 floors (1st-50th floor) and if egg is not broken then higest floor from which egg can be dropped without breaking it is among the top 51 floors (50th-100th floor). This way we have reduced problem space to 50 after first attempt.

Lets take both cases. In first case when egg is broken you have left with one egg and no choice other than trying dropping the egg from each floor starting from first floor and going upward by one floor each time. This case you have to drop the egg max upto 50 times to find the solution (In this case egg can be broken only if it is dropped from 50th floor or above). In second case let's apply "Binary Division" approach again and drop the egg at 75th floor. If egg is broken the solution is between 51-75 otherwise 76-100. In both case number of attempts will be less than 50 so let's discard them.

Refined Approach

Trinary Divide - Reduce Problem Space by 3

Let's think some better way to reduce the number of attempts. Instead of "Binary Divide", let's use "Trinary Divide". Drop the egg from 33rd floor (100/3). If egg is broken then we have to start from first floor just like we did in "Binary Divide". In this case we have to try max upto 33 times (Worst case : Egg is broken from 33rd floor onward). In case of egg is not broken from 33rd floor then we are left with 67 floors (34th floor - 100th floor). In second attempt we will drop the egg from 66th floor which will divide our problem space from 67 floors to 33/34 floors based on egg is not broken or broken. After two attempts we have divided the problem space by 3. In this case maximum attempts are 2+33 = 35.

Let's improve over above approach and divide the problem space(100 floors) in four parts. In this case first egg will be dropped from 25th floor. In this case max attempts are 3+24 = 27 (When egg is broken from 75th floor onward).

We can keep refining approach by reducing the problem space further. If we divide the problem space in 10 parts then max attempts are 9+9 = 18 (when egg is broken from 90th floor onward)
These attempts and results are

1.Drop @ Floor 10 - Egg is not broken
2.Drop @ Floor 20 - Egg is not broken
3.Drop @ Floor 30 - Egg is not broken
4.Drop @ Floor 40 - Egg is not broken
5.Drop @ Floor 50 - Egg is not broken
6.Drop @ Floor 60 - Egg is not broken
7.Drop @ Floor 70 - Egg is not broken
8.Drop @ Floor 80 - Egg is not broken
9.Drop @ Floor 90 - Egg is broken
10.Drop @ Floor 81 - Egg is not broken
11.Drop @ Floor 82 - Egg is not broken
12.Drop @ Floor 83 - Egg is not broken
13.Drop @ Floor 84 - Egg is not broken
14.Drop @ Floor 85 - Egg is not broken
15.Drop @ Floor 86 - Egg is not broken
16.Drop @ Floor 87 - Egg is not broken
17.Drop @ Floor 88 - Egg is not broken
18.Drop @ Floor 89 - Egg is not broken

After 18 attempts we found that egg can be broken 90th floor onward.

Best Approach

Irregular Divide - Reduce Problem space with each attempt

In above approach we were dividing the problem space in equal parts. Problem space was not reducing with each attempts. Let's try to reduce the problem space with each attempt. Let's assume we have max n attempts. So if we drop our egg at nth floor and it is broken we have left with n floors so we can find the solution in n attempts. In case egg is not broken solution is in (100-n) floor. With second attempts we should reduce the problem space by 1 so let's drop the egg from n+(n-1) floor. In case egg is broken our problem space is reduced to n-1 floor (From n+1 To 2n-1). In this case we have to try max n times to find solution. If egg is not broken in third attempt we should drop egg from n+(n-1)+(n-2) floor so that problem space can be reduced to n-2 in case egg is broken.

We have to repeat this exercise till problem space is reduced to 1 floor and sum of all this must be 100. It means n+n-1+n-2+n-3....+3+2+1 >= 100 => Min value of n = 14

So One of Worst Case is


1.Drop @ Floor 14 - Egg is not broken
2.Drop @ Floor 27 - Egg is not broken
3.Drop @ Floor 39 - Egg is not broken
4.Drop @ Floor 50 - Egg is not broken
5.Drop @ Floor 60 - Egg is not broken
6.Drop @ Floor 69 - Egg is not broken
7.Drop @ Floor 77 - Egg is not broken
8.Drop @ Floor 84 - Egg is not broken
9.Drop @ Floor 90 - Egg is not broken
10.Drop @ Floor 95 - Egg is not broken
11.Drop @ Floor 99 - Egg is broken
12.Drop @ Floor 96 - Egg is not broken
13.Drop @ Floor 97 - Egg is not broken
14.Drop @ Floor 98 - Egg is not broken

Solution
14 Attempts