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)

$\endgroup$
  • 5
    $\begingroup$ Does the camel starve if it isn't carrying any bananas and walks a kilometer? $\endgroup$ – Qiaochu Yuan Jul 24 '11 at 20:40
  • 5
    $\begingroup$ @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. $\endgroup$ – Anson Kao Jul 24 '11 at 20:59
  • 4
    $\begingroup$ 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. $\endgroup$ – joriki Jul 25 '11 at 4:18
  • 4
    $\begingroup$ 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. $\endgroup$ – joriki Jul 25 '11 at 4:20
  • 4
    $\begingroup$ 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)? $\endgroup$ – Rasmus Faber Jul 25 '11 at 5:15
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Anson Kao Jul 26 '11 at 4:09
  • 1
    $\begingroup$ @SampleJACK: Did you have a good method for coming across this answer? Mine was somewhat obscure. $\endgroup$ – davidlowryduda Jul 26 '11 at 4:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Anson Kao Jul 28 '11 at 16:28
  • $\begingroup$ @SampleJACK: yeah, I did that too. Lots of fiddling. $\endgroup$ – davidlowryduda Jul 28 '11 at 16:47
19
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What if he travels to an earlier point and the following possibility arises: 1) the total of the supply at that point and the amount he's carrying when he reaches that point, is enough to allow him to traverse the segment but 2) the supply at that point itself is not enough to allow him to traverse that segment. Then your argument that "he could have traversed the former segment first" would not apply. $\endgroup$ – Siddharth Joshi Jun 14 at 8:27
  • 1
    $\begingroup$ @SiddharthJoshi: No. Given 3 adjacent stopping points A,B,C, the claim is that if you go A→B→C then you never need to go back to A. It is not a trivial argument, but it is not hard. Suppose there is a path that goes backwards twice C→B→A. Then we can assume C→B→A is the last two steps in the first backward chain of length at least 2. So the path must have A→B→C→...→B→A→B. Now we simply need to check that we can change it to A→B→A→B→C→...→B, since prior to this subpath we could not have reached C (otherwise there would be an earlier backward chain of length at least 2). $\endgroup$ – user21820 Jun 14 at 9:07
  • $\begingroup$ Is there a rigorous proof you have for this. I think you would also need to prove that the amount finally remaining at each of those positions in that sequence after the exchange operation, is greater than or equal to their amounts for the previous sequence. Can't really extend your argument to a rigorous proof - I will have to construct a more formal proof for myself on my own. $\endgroup$ – Siddharth Joshi Jul 3 at 19:16
  • $\begingroup$ @SiddharthJoshi: Yes I commented because I believed I could write a rigorous proof but was lazy to. The change to that subpath preserves the total distance travelled and hence we just have to ensure that we can leave behind the same amount at each point at the end of the modified subpath. By my definition, the "..." stays at C or later, and then the "B→A→B" uses 2·dist(A,B) bananas that we had carried from before C (since prior to that subpath there are no bananas at C or later. Label those bananas and retrace our steps in the original subpath and instead leave them behind at B. [cont] $\endgroup$ – user21820 Jul 4 at 9:33
  • 1
    $\begingroup$ @SiddharthJoshi: Your attempt seems to fail. Your "earlier point" is no different from my "backwards twice". But if the path is A→B→C→D→C→B→A, your first earlier point is B, and so your claim that it must go B→C from that point is false. That is precisely why I said "we can assume C→B→A is the last two steps in the first backward chain of length at least 2". It's not as simple as you think. I suggest you try to work carefully through the sketch I gave. If you have trouble, we can continue in chat. $\endgroup$ – user21820 Jul 4 at 10:21
1
$\begingroup$

Solution available at this link:

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Eric Naslund Jul 24 '11 at 21:13
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Perhaps the farmer has many camels... $\endgroup$ – Qiaochu Yuan Jul 25 '11 at 1:28
  • 2
    $\begingroup$ @Dominguez, returning to the factory is not a requirement $\endgroup$ – Anson Kao Jul 25 '11 at 1:53
  • 3
    $\begingroup$ 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. $\endgroup$ – senderle Jul 25 '11 at 2:03
  • $\begingroup$ @ Qiaochu Yuan, lol $\endgroup$ – Dominguez Jul 25 '11 at 2:05
  • $\begingroup$ @sampleJACK, then those your answer differ then 533? $\endgroup$ – Dominguez Jul 25 '11 at 2:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.