14
$\begingroup$

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)

  • 0
    @Rasmus good question, this is up to interpretation, but I'm inclined to say you can treat 1 banana/km the same way you treat mileage in a vehicle (consumed at a steady rate)2011-07-26

5 Answers 5

1

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.

  • 0
    @sampleJACK, then those your answer differ then 533?2011-07-25
17

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!

6

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.

  • 0
    @SampleJACK: yeah, I did that too. Lots of fiddling.2011-07-28
5

http://groups.google.com/group/sci.math/msg/5da8025c33f3300f?hl=en

  • 3
    Why throw away a banana when you could eat it? :-)2011-07-25
1

Solution available at this link:

  • 0
    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.2011-07-24