[Guest]

I've got this puzzle today but haven't solved it myself yet...

A farmer has 3000 apples, he wants to deliver them to a market that is 1000km away through the desert, he has a camel which can carry only 1000 apples at a time and also has to eat 1 apple for each kilometer of walking.

What is the maximum amount of apples that can be delivered and how? (no out-of-the-box solutions)

[araver]

He can get 500 across for sure. Here's how:

Assume points A are start (3000 apples) and B finish (0 apples initially).

Distance between A and B is 1000 km.

Two camps needed:

Camp 1 - 250 km from A, 750 km from B.

Camp 2 - 500 km from A, 500 km from B.

Trip 1 A-Camp 1 and back

Take 1000 apples, go to camp 1. 250 are eaten along, drop 500 at camp 1, eat 250 while going back to A.

Stores: A(2000), Camp1(500), Camp2(0), B(0)

Trip 2 A-Camp 1 and back

Take 1000 apples, go to camp 1. 250 are eaten along, drop 500 at camp 1, eat 250 while going back to A.

Stores: A(1000), Camp1(1000), Camp2(0), B(0)

Trip 3 A-Camp 1

Take 1000 apples, go to camp 1. 250 are eaten along,

Stores: A(0), Camp1(1750), Camp2(0), B(0)

Trip 4 Camp 1-Camp 2 and back

Take 1000 apples from Camp1, go to camp 2. 250 are eaten along, drop 500 at destination, eat 250 on the way back to camp 1.

Stores: A(0), Camp1(750), Camp2(500), B(0)

Trip 5 Camp 1-Camp 2

Take 750 apples from Camp1, go to camp 2. 250 are eaten along, drop 500 at destination.

Stores: A(0), Camp1(0), Camp2(1000), B(0)

Trip 6 Camp 2-B

Take 100 apples from Camp2, go to B. 500 are eaten along, drop 500 at destination.

Stores: A(0), Camp1(0), Camp2(0), B(500)

I don't think a different arrangement of camps will give you better results.

And without camps you cannot cross the desert without eating the whole pack.

[Guest]

^ That's the answer I got to (though there are other ways but it's the same result)

I wanna know if anyone can get more, or come up with proof that this is the max...

[araver]

^ That's the answer I got to (though there are other ways but it's the same result)

I wanna know if anyone can get more, or come up with proof that this is the max...

Yup, there can be more than what I said

just found a slightly bigger number by changing the distances between the camps.

I believe an maximum proof will also be a constructive proof. I'll come back with it once I figure it out.

[wolfgang]

We can make two camps:

350 Km and 700Km

in this case we can reach to the end with 550 apples

[araver]

Assuming same strategy as before. Assume points A are start (3000 apples) and B finish (0 apples initially).

Distance between A and B is 1000 km.

Two camps needed:

Camp 1 - x km from A, 1000-x km from B.

Camp 2 - x+y km from A, y from Camp 1, 1000-x-y km from B.

x and y are clearly less than 500 km in order to survive a return trip.

First 2 trips: A-Camp 1 and back

Take 1000 apples, go to camp 1. x are eaten along, drop 1000-2x at camp 1, eat x while going back to A.

Stores: A(2000), Camp1(1000-2x), Camp2(0), B(0)

Stores: A(1000), Camp1(2000-4x), Camp2(0), B(0)

Trip 3 A-Camp 1

Take 1000 apples, go to camp 1. x are eaten along.

Stores: A(0), Camp1(3000-5x), Camp2(0), B(0)

Trip 4 Camp 1-Camp 2 and back

Take 1000 apples from Camp1, go to camp 2. y are eaten along, drop 1000-2y at destination, eat y on the way back to camp 1.

Stores: A(0), Camp1(2000-5x), Camp2(1000-2y), B(0)

Assuming x is less or equal to 200, there's still enough apples in Camp 1 for another trip.

Trip 5 Camp 1-Camp 2

Take rest of apples from Camp 1, go to Camp 2. y are eaten along, drop the rest at destination.

Stores: A(0), Camp1(0), Camp2(1000-3y+2000-5x), B(0)

Now the remaining apples are 3000-3y-5x. Since x<=250, we have at least 2000-3y apples. For a full 1000 apples load, we need y<=333.

Trip 6 Camp 2-B

Take as much apples as possible from Camp2, go to B. 1000-x-y are eaten along, drop the rest at destination.

Stores: A(0), Camp1(0), Camp2(2000-3y-5x), B(z)

where z=1000-(1000-x-y)=x+y if x<=200 and y<=333.

A maximum is reached for (x,y) = (200,333) z=533.

It is a maximum for this type of strategy, but it doesn't prove other strategies aren't possible.

EDIT: Later thought

Assuming the camel actually eats continuously and does not refuse bitten apples, we can get y=333.(3) so z=533.(3) Not sure what one would do with a third of an apple

Second EDIT:

This just made me realize that if a camel starts eating as soon as it moves it's actually possible to give her an apple to go and carry 1000 at the same time ... which makes z=534 possible since after trip 5 you get 1001 apples in Camp 2 for the final trip.

Edited November 21, 2010 by araver

[wolfgang]

We can make two camps:

350 Km and 700Km

in this case we can reach to the end with 550 apples

No ,, sorry....I am wrong!!

Edited November 21, 2010 by wolfgang

[araver]

EDIT: Nevermind.

Edited November 21, 2010 by araver

[superprismatic]

If we make 999 interim camps and move all the apples from one camp to the next camp each time, we get the same best answer

that araver got. Like so:

Let S(A,B,C) be the statement "During the move to camp #A, we lose B apples to the camel, ending up with C apples at camp #A"

Here's the progressive moves:

S(1,5,2995)

S(2,5,2990)

S(3,5,2985)

.

.

.

S(197,5,2015)

S(198,5,2010)

S(199,5,2005)

S(200,5,2000)

S(201,3,1997)

S(202,3,1994)

S(203,3,1991)

.

.

.

S(530,3,1010)

S(531,3,1007)

S(532,3,1004)

S(533,3,1001)

S(534,1,999) <- only moving 1000 (of the 1001) from the previous step (leaving 1 at camp #533 and losing 1 to the camel)

S(535,1,998)

S(536,1,997)

.

.

.

S(997,1,536)

S(998,1,535)

S(999,1,534)

S(1000,1,533)

Here, 1000 is the destination B. Notice that the number of back and forth moves changes after camp #200 and camp #533.

These are the key camps in araver's construction. I suspect one can use the above construction as the basis of a proof

for the optimality of araver's answer of 533.

[Quantum.Mechanic]

Math Factor, starting with last part of

this podcast. This goes on to consider other variants.

Also, Camels and Bananas.

[Guest]

I might be able to proove it's gonna be 533 in any case no matter how many camps you make:

Imagine you tie a paint brush to the tail of the camel and draw a line behind you wherever you go, you first need to move 3,000 apples to point A, you take the first thousand and come back, then the second thousand and come back, then the third (you don't come back) so that's five lines, you drag these five lines until you reach the 200th kilometer, 5x200=1000 so you've spent a thousand apples on the road so now you no longer need five tracks you only need three, you continue with three lines for 1000/3 kilometers until you reach the 533rd kilometer, so then you have only 1000 apples for which you only need one straight line until the end of the desert...

EDIT: It seems that it's all explained in the link Quantum.Mechanic posted: http://www.puzzle.dse.nl/math/bananas_us.html

Edited November 26, 2010 by Anza Power