An Algorithmic Camel

At KM # 0, we have 3000 bananas. The maximum bananas the camel can carry is 1000 so the camel must make at least 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.

We continue making 3 trips until we reach a banana count of 2000.

3000 – 5*d = 2000 => d = 200

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.

We continue making 2 trips until we reach a banana count of 1000.

2000 – 3*d = 1000 => d = 333.333 km

At (200+333.333) = 533.333 km, we will have 1000 bananas.

At this point, we need to make one trip so the camel just carries everything and marches toward the market.

Remaining km = 1000 – 533.333 = 466.666 km. Bananas needed = 466.666

Therefore, the bananas remaining once the camel reaches the market is 1000– 466.666 = 533.333 bananas

Rounded off to 533 bananas.

Best way: Carry 1000 of them from 0 to 1. Keep 998 there and return to 0.(Net -2 bananas) Do this once more. (-2). Now carry the 1000 remaining from 0 to 1 (-1). Hence we have transported 2995 bananas from 0 to 1.

Note that whenever ceil(no.of banana/max capacity) = n, we will end up losing 2*n-1 banana when transporting by 1 km fwd.

Hence, we will reach 200 with 2000 bananas remaining. Hence, we will reach 200+333 with 1001 bananas remaining. Now just carry all the 1000 bananas from 533 to 1000, thus transporting 533 bananas

The point in this problem is that we have to maximize every load the camel is carrying. Till the camel can carry a maximum of 1000 bananas, at each stopping spot we have to get a number of bananas that is a multiple of 1000. In our case 2000 and 1000. To get 2000 at the first stop we have to consume 1000 bananas, and since five trips are needed, we fix the stop at 200 km. Next, for having 1000 bananas at the second stop, again we need to spend another 1000 bananas, this time in three trips. So we reach the point 200+1000/3=533+1/3, from which with a single leap we reach the finish line, delivering 1000-(1000-533-1/3)= 533+1/3 bananas. This is a general solution which can be applied to any set of the three initial data. Surprisingly and mathematically speaking, there is another solution which gives however the same result: a number of infinite trips of infinitesimal length...

follow the strategy: carrying 1000 bananas, move 1km, drop bananas, go back 1km, carrying other 1000 bananas until no bananas left. we have the map of bananas as follow.

km 0: 2999

km 1: 2994

km 2: 2989

1 km cost 5 banana => 200km cost 1000 banana

km 200: 1999

km 201: 1996

km 202: 1993

1km cost 3 banana => 333km cost 999banana

km 533: 1000

1km cost 1 banana => 467km cost 467banana

km 1000: 533

I solved it using simple excel sheet.

Column A: KM/step

Column B: Number of Bananas carried on first trip to this KM/step

Column C: Number of Bananas left at previous step after first step

Column D: Number of Bananas carried on second trip to this KM/step

Column E: Number of Bananas left at previous step after second step

Column F: Number of Bananas carried on third trip to this KM/step

Column G: Total number of Bananas remained uneaten

It should look something like this:

0 0 0 0 0 0 3000

1 999 1999 999 998 997 2995

2 999 1994 999 993 992 2990

3 999 1989 999 988 987 2985

....

With this approach you can visualize how each step is executed. Interestingly. I can save 534 bananas! Here is how: At step 533 I will be left with 1002 bananas. At 534, camel eats one banana and brings 1000 bananas to 534 milestone. I don't need to go back to milestone 533 which is left with 1 banana. This will save me 1 banana to go back. So I will be left with one additional banana! 534!

First of all, it never hurts to make general observations before diving in straight into whatever the first way of solving the problem comes to you and doing all kinds of computations. The first thing to note here is 1 km travelled = 1 consumed banana whatever the natural obstacles are (those don't concern us), so the consumption is constant across any travelled distance . Secondly , it makes intuitive sense that the camel should somehow consume the least amount of bananas as possible while carrying most of them as possible . So, to achieve that, since it's 1 banana/1km, the camel should travel to the shortest distance possible (1 km) with maximum amount of bananas as possible, thereafter leaving the bananas at the end of the travelled distance. So continuing with the thoughts of the "second observation", we make the following route: 1) travel one kilometer with 1000 bananas, leave 998 bananas, consume 2 bananas in total on the way forward and on the way back; 2) repeat the same process (which cost us 4 bananas, taking into account the 1-st step); 3) now all we have to do is to just travel 1 km with 1000 bananas (having consumed 5 bananas in total). Thus, we have travelled 1 km (with 5 trips to and fro) and carried over 2995 bananas with 5 bananas consumed along the way. So we continue doing that till we consumed 1000 bananas and travelled 200 km (it is because we have bananas > 2000, which necessarily means we have to make 5 trips). The procedure that follows will be quite similar, but now we need to carry over only 2000 bananas over 1 km, which requires only 3 trips to do this (which costs us 3 bananas). We continue doing that till we are left with 1000 bananas (again the line of reasoning is very similar: we have bananas > 1000, which necessarily means we have to make 3 trips to complete 1 km). Thus, we travelled 333.33... km. Now we 200 km + 333.33... km = 533.33... km, which means we have 466.66 km left to travel, which costs 466.66 bananas, in the end leaving us with 533 bananas (because we were left with 1000 bananas). To express this idea a little bit more differently: Let m be the maximum amount of bananas the camel can carry at a time (which is 1000 bananas); we have 3m in total. So we carry over m to the shortest distance travelled, return, carry over m to the shortest distance again, return, carry over m to the shortest distance, thus traveling 5 km in total (consuming 5 bananas). We continue doing this till we consumed m bananas, leaving us with 2 m. So we carry over m to the shortest distance, return, carry over m to the shortest distance once again, thus traveling 3 km in total (consuming 3 bananas). We continue doing this till we consumed m, leaving us with m. Let us travel s distance till we consumed 2 m bananas, till we left with m bananas: s = m/5 + m/3 Also after being left with m bananas we have to travel 1000 km - s distance more. So bananas remaining after the "journey" are m - (1000 - s). So we just find s, because we know what m is (1000): s = 1000/5 + 1000/3 = 533.33... and bananas remaining after the "journey" are 1000 - (1000 - 533.33) = 533.33...

I used Dynamic Prg, Below is the matrix and logic:

e.g: Distance=4, TotalFruit=10, MaxCanCarry=6

                             Hops/ Distance: -->      1    2    3    4


          Ferry( One side KM journey i.e 1KM) :       0    7    4    3


                                         2KM  :       0    0    4    3

int pointA2B = (maxCarry/2)-1; // Max distance can be taken [(1000/2)-1) = 499]

    for(int hops=0; hops<pointA2B; hops++)
    { 
        int score = totalFruit;
        int lastFerry;
        scoreMatrix[hops][0]=0;
        for(int distIterate=(hops+1); distIterate<dist; distIterate++)
        {
            lastFerry = (score%maxCarry);        // Remainder of last round for respective KM 
            if(lastFerry!=0)                        
            {
                score = ((score/maxCarry)*(maxCarry-((hops+1)*2)));  
                                                                       // (n-1) rounds * Max-To&FroDistace camel will consume 
                score += (lastFerry-(hops+1));     // Last round so Remaining fruits-distance
            }
            else
            {
                score = (((score/maxCarry)-1)*(maxCarry-((hops+1)*2)));
                score += (maxCarry-(hops+1));
            }
            scoreMatrix[hops][distIterate]=score;
            distIterate+=hops;
        }
    }
}

You need to make small trips back and forth. Since there are 3000 bananas first we will need 3 trips. After we consume 1000 bananas we will only need 2 trips to move all the bananas so we will move more optimal. Again, after we consume another 1000 bananas we don't have to come back since we can carry all the remaining bananas.

We need to calculate the length of the trips carefully so we end up with 2000 bananas in one place and not less. For example a bad way would be to make 300km in a trip. This way first trip saves 400 bananas, second trip 400 bananas and last trip saves 700 bananas. In the end we would have 1500 bananas and that's bad because we want to make only 2 trips once we get 2000 bananas or less.

Optimum is to make trips of 1km, or 2km, or anything that divides 200(because you need 5 bananas for each km, and you want to consume 1000 bananas). So if you make trips of 200km then first trip you save 600, second trip you save 600 and last trip another 800 bananas, leaving you at one place with 2000 bananas.

Now you start making series of 2 trips in such a way you remain with only 1000 bananas in one place. Same logic as above, but you need only 3 bananas for each km so you can walk another 333 km until you end up with 1000 bananas in one place.

Total so far you walked 533km and you have 1000 bananas left. From this point you just walk forward and end up with 533 bananas.

1st 200km with 1000 bananas(5 bananas for each km), 333 km with 999 bananas( 3 bananas for each km) and remaining 1001 we should cover 467 kms .for 1km require 2 bananas, then remaining 999 bananas-466kms=533

first, the camel takes 1000 bananas to point A. There it drops 600 bananas and returns with 200 bananas. Then the camel takes again 1000 bananas to point A. Again, it drops 600 bananas and returns with 200 bananas. After this, the camel takes the last 1000 bananas from the plantation to point A. From point A, it leaves with 1000 bananas to point B. In point B, it drops 333 1/3 bananas and returns with 333 1/3 bananas. Then it takes the second load of 1000 bananas from point A to point B. Finally, it carries the 1000 bananas from point B to the market, where it arrives with 533 1/3 bananas.

Here's a proof that 533 bananas is optimal.

We move right from A to B, with 1000 km between A and B. The key idea is to look at the total number of different bananas that reach various points between A and B from the left (without being taken back left).

1) Notice first that in any strategy, the total number of different bananas reaching a point between A and B from the left is strictly decreasing with the distance from A. If y is to the right of x, all bananas at y must have reached x too, and in order to arrive at y, the camel must have eaten some of the bananas that reached x, and hence there are less bananas reaching y.

2) From this follows that in any given strategy, there is a unique point where exactly 3000 different bananas arrived (of course this is the start), and another unique point where exactly 2000 different bananas arrived from the left. We call them $x_3$ and $x_2$ . (Similarly, the point where exactly 1000 different bananas arrived is called $x_1$ and so on for $x_n$ .)

3) We make an upper bound for the distance between $x_3$ and $x_2$ . Looking at any point between $x_3$ and $x_2$ , we know from 1) that the camel brings strictly between 2000 and 3000 bananas to that point from the left. This means that the camel must arrive at the point from the left at least 3 times (since the camel can only carry at most 1000 bananas). For every time the camel arrives except the last, the camel must go back left in order to arrive again. This means that the camel traverses at least $3+2=5$ "paths" to the immediate left of the point. Since this is true for all points between $x_3$ and $x_2$ , the camel eats at least 5 bananas pr. kilometer between $x_3$ and $x_2$ . The camel eats exactly 1000 bananas between $x_3$ and $x_2$ , and thus the maximal distance between $x_3$ and $x_2$ is $1000/5=200$ in any strategy.

4) Similarly, the maximal distance between point $x_2$ and point $x_1$ in any strategy is $1000/3$ . Generally, the maximal distance between point $x_{n}$ and $x_{n-1}$ is $\frac{1000}{2n-1}$ .

5) When we reach $x_1$ in any strategy, the maximal number of bananas we can bring to B is the distance travelled so far. The maximal distance between $x_3$ and $x_1$ is the sum of the maximal distances between $x_3$ and $x_2$ , and $x_2$ and $x_1$ . This is $1000/5 + 1000/3=200+333=533$ .

6) Generally, if we start with $n$ kilo bananas, we can travel at most

$1+1/3+1/5+1/7+...+1/(2n-1)$

thousand kilometers.

7) We notice that the upper bound we have established can indeed be reached by travelling $2n-1$ number of times between $x_{n}$ and $x_{n-1}$ with full loads from the left.

Let 3x+y=1000 for the first trip.x=max distance reach by the camel in 1st trip. 2x bananas for forth and back journey.And 1 banana is kept at each kilometer(optimal strategy-so that in the last trip, he will have exactly 1000 bananas upto certain distance(x+z)), so required bananas are x.Total=3x.. y bananas are kept at xth kilometer(for second trip purpose)

Let 3z=1000-2x+y for second trip.z=max distance reach by the camel in 2nd trip prior to x. 3z bananas using the same method as used for the 1st trip.Here from 1000-x-(x-y) -x because the bananas at each kilometer are for the 3rd trip, so not to consume in the 2nd trip, and -(x-y) for the return trip bananas considering the y bananas that are already placed at xth kilometer.

2nd trip equation becomes 3z=2000-5x(by equating 1st and 2nd trip equation) so z=(2000-5x)/3

Now for 3rd trip. The bananas that can be transported to other side are x+z(by consuming the bananas left at each kilometer) x+z=x+(2000-5x)/3=(2000-2x)/3=f(x)

Now here as the camel has limitation , it can only carry 1000 bananas so 200<=x<=400(for this strategy)

Now from the equation f(x)=(2000-2x)/3..f(x) is max. when x is min. i.e x=200. so f(x)=1600/3=533.33333...which means 533 whole bananas are transported leaving .33333.. of the bananas

Using javascript to simulate the moves the camel like this code below (can run directly in your browser console):

var camel={
    setUp: function()
    {
        this.pos=0;
        this.length=1000;
        this.maxNum=1000;
        this.remain=3000;       
    },
    move: function(step)
    {
        if(this.remain<=step||this.pos>=this.length)
            return false;

        this.pos++;
        var r=step;

        while(true)
        {
            r-=step;
            this.remain;

            var t=Math.min(this.remain, this.maxNum)-step;

            r+=t;
            this.remain-=t+step;

            if(this.remain<=2*step)
                break;
        }

        this.remain=r;
        return true;        
    },
    makeMoves:function(step)
    {
        while(true)
        {
            var result=this.move(step);

            if(!result)
                return;
        }
    }
}
camel.setUp();
camel.makeMoves(1);

We move the the camel 1 step and try to carry all the bananas remained for each turn until it reaches the final position