# How many bananas can a camel deliver without eating them all?

This is a fun puzzle I was assigned on the first day of highschool (over a decade ago). I just dug it up randomly from under my bed and thought I'd share it with the SE community. At the time, I found a better solution than even the Puzzle book had, and nobody was able to come up with a better answer...

A farmer has 3000 bananas that will be sold at a supermarket located 1000 kilometers away. To get them there, he has a camel that is strong enough to carry 1000 bananas at a time, but will eat 1 banana for each kilometer it walks. Will the camel successfully deliver any bananas to the supermarket? If yes, how many, and how?

Have fun! :D (I will reveal my personal 9th grader solution if no-one finds it)

-
Does the camel starve if it isn't carrying any bananas and walks a kilometer? –  Qiaochu Yuan Jul 24 '11 at 20:40
@Qiaochu The camel will die without his bananas! And he must eat 1 banana during each km of travel, he cannot eat them pre-emptively, his belly only fits 1 banana. –  Anson Kao Jul 24 '11 at 20:59
This puzzle is highly unrealistic. a) Camels' ability to go without food and water is legendary. b) As Dominguez rightly pointed out, success would include getting back to the farm. c) A camel goes 15 km/h, some say only 50 km/day. Even at 10*15=150 km/day, it would take 2 weeks to complete the trip, which is too long for the bananas to go unrefrigerated. –  joriki Jul 25 '11 at 4:18
However, since a typical banana weighs 118 g, a typical farmer weighs 100kg and a camel can carry up to 450 kg, if he's lucky and has a strong camel and isn't too heavy himself, he just might be able to cram the 124 liters of banana into a refrigerator weighing 100 kg and take a huge solar pack along to power it. Good luck. –  joriki Jul 25 '11 at 4:20
The exact (532, 533 or 533 1/3) seems to rely on some specifics of camel-feeding: Do you need to feed it exactly one banana at a time or can you feed it 1/3 of a banana to go 1/3 km? Is it already fed (does it walk 1 km and then is fed 1 banana or do you feed it one banana and then it walks 1 km)? –  Rasmus Faber Jul 25 '11 at 5:15

Ok - it is an answer, that I think is optimal. When I first made this comment, I was unsure. But 533 seems to be the answer.

First go 200 kilometers, drop off 600, and turn around. Repeat. So now we have 2000 bananas, 200 kilometers away from where we began.

Now travel 333 and a third of a kilometer, drop off 333 and a third, and return to the 'wait station' 200 kilometers away from where we began. There are 1000 bananas left, and so we go in one run to the end. We do, of course, pick up the 333 and a third bananas that we left (conveniently exactly 333 and a third kilometers away).

So we end with 1000 - 800 + 333 and a third, or 533 and a third bananas. And I think this is optimal.

-
So I guess I shouldn't be surprised that the collective hive-mind of the internet would be able to find my 9th grade solution - mixedmath, you nailed it. The shocking thing is that the solution in the puzzle book had the stops at 250 km and 500 km, yielding 500 km as the answer, and nobody else including the teacher knew any better! –  Anson Kao Jul 26 '11 at 4:09
@SampleJACK: Did you have a good method for coming across this answer? Mine was somewhat obscure. –  mixedmath Jul 26 '11 at 4:15
the most important observation in solving this problem is that the stopping points should be optimized to a multiple of 1000 bananas, since that is the upper capacity of the camel and optimal. From that, I just fiddled with numbers I guess. –  Anson Kao Jul 28 '11 at 16:28
@SampleJACK: yeah, I did that too. Lots of fiddling. –  mixedmath Jul 28 '11 at 16:47

Here is the optimal solution for an arbitrary capacity $c$, amount $n$ and distance $x$:

First note that the path of the camel can be divided into segments determined by all the turning points. Then the number of times each same segment is crossed is even except for the first and last segment. Also the camel never needs to cross a former segment once it has crossed a later segment because otherwise it could have traversed the former segment first as there would have been a sufficient supply already brought to that point earlier. Thus there is one optimal solution such that the camel brings a certain amount in one or more trips from one point to the next and never returns to an earlier point. Also, there should not be any amount left at any point because otherwise that amount $r$ can be used to move the amount that is transported $t$ in $2 \lceil \frac{t}{c} \rceil - 1$ trips by the distance $\frac{r}{ 2 \lceil \frac{t}{c} \rceil - 1 }$, and it would also be optimal.

Now, let $f(c,n,x)$ be the maximum amount that can be brought a distance of $x$ where an amount $n$ and the camel with capacity $c$ are at the starting point. Then we have:
$f(c,n,x) = 0$ for all $n < x$
$f(c,n,0) = n$ for all $n \geq 0$
$f(c,n,x) = \max( \{ f( n - ( 2 \lceil \frac{n}{c} \rceil - 1 ) y , x - y ) : 0 < y \leq x \} )$ for all $x > 0$
The value of $f(c,n,x)$ is clear from the equivalent geometric interpretation:
Given point $(n,x)$, $f(c,n,x) \geq f(c,n',x')$ for every point $(n',x')$ where the line segment has gradient $\frac{ 1 }{ 2 \lceil \frac{n}{c} \rceil - 1 }$ and $0 \leq x' \leq x$
Since any solution corresponds to a series of such segments connected end to end, ending at $(m,0)$, and $f(m,0)$ is strictly increasing in $m$, and the gradient of the segments are strictly increasing, an optimal solution clearly must start a new segment when it is at each line $n=i$ where $i \in \mathbb{Z}^+$
Thus $f(c,n,x) = \begin{cases} 0 & if & n < x \\\ n & if & n \geq x = 0 \\\ n - x ( 2 \lceil \frac{n}{c} \rceil - 1 ) & if & 2 \lceil \frac{n}{c} \rceil - 1 \leq r \\\ f( c , n - r , x - \frac{ r }{ 2 \lceil \frac{n}{c} \rceil - 1 } ) & if & otherwise \end{cases}$ where $r = n + c - c \lceil \frac{n}{c} \rceil$

For this example,
$f(1000,3000,1000)$
$= f(1000,2000,\frac{4}{5}(1000))$
$= f(1000,1000,\frac{7}{15}(1000))$
$= \frac{8}{15}(1000) = 533\frac{1}{3}$

Interestingly, the maximum distance that the camel can go with a starting heap of $cn$ bananas is $c ( \frac{1}{2} ln(n) + O(1) )$, which means that an exponential number of bananas is needed with respect to the distance from the starting point!

-
+1 this needs more upvotes –  Sreenath S Jul 20 '13 at 7:02
-
Why throw away a banana when you could eat it? :-) –  joriki Jul 25 '11 at 3:32

-
I think you can do better by one banana. The idea is correct, but in step two it goes to 534 km instead of 533. By leaving one banana on the ground at 533km we can get to the end with 533 bananas instead of 532. –  Eric Naslund Jul 24 '11 at 21:13

No, the camel can not successfully deliver any bananas to the supermarket. If you do micro-trips to get 532 or 533 then the camel can't get back.

-
Perhaps the farmer has many camels... –  Qiaochu Yuan Jul 25 '11 at 1:28
@Dominguez, returning to the factory is not a requirement –  Anson Kao Jul 25 '11 at 1:53
There's a banana shortage. The farmer uses part of his or her enormous profit to buy high-nutrient-density camel food for the trip back. –  senderle Jul 25 '11 at 2:03
@ Qiaochu Yuan, lol –  Dominguez Jul 25 '11 at 2:05
@sampleJACK, then those your answer differ then 533? –  Dominguez Jul 25 '11 at 2:06

## protected by Qiaochu YuanJul 25 '11 at 1:28

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.