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

Question

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)

Answer 1

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.

Answer 2

Here is the optimal solution for an arbitrary capacity $c$, amount $n$ and distance $x$: $ \def\lfrac#1#2{{\large\frac{#1}{#2}}} $

First note that the path of the camel can be divided into segments determined by all the turning points. Then each segment is traversed an odd number of times. We can assume that there is none left at any point because otherwise we can simply consume any leftover amount $r$ by moving forward and backwards a number of times over appropriate distances to consume it (the appropriate distance is $\frac12r$ if $r≤c$, otherwise it is $\frac12c$). Also the camel never needs to traverse a former segment once it has traversed a later segment, because otherwise it could have traversed the former segment first since there would have been a sufficient supply already brought to that point earlier. (See below for proper proof.) Thus we need only consider solutions in which that the camel brings everything from the current point to the next point in one or more trips (and never returns to an earlier point).

Now consider the state of the camel between such phases of a given solution as captured by a point in the $(n,x)$-plane. That is, each segment in the path corresponds to moving from a point $(n,x)$ to another point $(n',x')$ where there are initially $n$ bananas at a single turning point and the camel was initially at that point with remaining distance $x$, and after that segment there are $n'$ bananas at the next turning point and the camel has reached that point with remaining distance $x'$.

Observe that the line segment from $(n,x)$ to $(n',x')$ has gradient $\lfrac{ 1 }{ 2 \lceil \lfrac{n}{c} \rceil - 1 }$, since the camel must traverse that segment $( 2 \lceil \lfrac{n}{c} \rceil - 1 )$ times so as to leave no bananas behind, which would consume $( 2 \lceil \lfrac{n}{c} \rceil - 1 ) · (x-x')$ bananas. Notice that this gradient is bigger when $\lceil \lfrac{n}{c} \rceil$ is smaller, and that a bigger gradient is better because the camel covers more distance per banana. So it is clearly best if we start a new line segment whenever $\lceil \lfrac{n}{c} \rceil$ decreases, which is precisely whenever $n$ is a multiple of $c$. This yields a unique solution, which must hence be optimal. (I shall leave it as an exercise to rigorously prove that any other solution is no better than this; one of the easiest ways is to use induction on $\lceil \lfrac{n}{c} \rceil$.)

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) = \cases{ 0 & if $n < x$ \\ n & if $x = 0$ \\ n - ( 2 \lceil \lfrac{n}{c} \rceil - 1 ) · x & if $( 2 \lceil \lfrac{n}{c} \rceil - 1 ) · x ≤ r$ \\ f( c , n - r , x - \lfrac{ r }{ 2 \lceil \lfrac{n}{c} \rceil - 1 } ) & otherwise }$
  where $r = n + c - c \lceil \frac{n}{c} \rceil$ (i.e. $r$ is the least positive real such that $n-r$ is a multiple of $c$).

The first case excludes impossible situations. The second case is when the camel has reached the destination. The third case is when using one phase (i.e. one line segment) to reach the destination is optimal, in contrast with the fourth case where attempting to reach the destination in a single phase would cause the bananas at the destination to be less than the nearest multiple of $c$ below $n$, which by the earlier reasoning is not optimal. So the fourth case is recursive because we want the camel to consume only $r$ bananas to shift the rest in one phase and then begin another phase after that.

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) )$, so an exponential number of bananas is needed with respect to the distance from the starting point!

−−−−−−−

From the comments it has become clear that it is difficult for some people to find a proof of the above claim that the camel never needs to traverse a former segment after it has traversed a later segment. Indeed, this is a rather tricky exercise; most naive proof attempts will fail completely. Here is a proper proof:

Take any path $P$ that performs finitely many turnings. Divide $P$ into segments according to all the turning points (i.e. each segment is from some turning point to some adjacent turning point). Then according to $P$, whenever the camel is at the starting point or a turning point and has not finished, it must go to an adjacent turning point. For convenience, for any turning points $A,B$ we shall say that $A < B$ iff $A$ is closer than $B$ to the starting point. I claim that there is some path $Q$ that reaches the same final point with the same number of bananas there as $P$ that does not go backwards twice, meaning that for every consecutive turning points $A<B<C$ in $Q$, once the camel reaches $C$ it never goes back to $A$. (Note that turning points only include points where the camel actually turned.)

To construct $Q$, we shall iteratively modify $P$ over a finite sequence of steps until it is as desired. Until then, at each step the current $P$ has some backward chain of length at least two, meaning that it has a chain of at least two consecutive backward moves. Let $C→B→A$ be the last two moves of the first backward chain of length at least two. (This "last" and "first" are crucial; removing them makes the proof totally fall apart.) Then $P$ has a subpath $A→B→C→$ $\cdots$ $→\underline{C→B→A}→B$ where the marked (underlined) part is the last two moves of the first backward chain of length at least two. It must be "$A→B$" after that part because otherwise the marked part would not be "the last two moves" in that backward chain. And every turning point in the "$\cdots$" is further than $A$ from the starting point, because otherwise the marked part would not be the "first backward chain of length at least two". Now modify that subpath to $A→B→A→B→C→$ $\cdots$ $→C→B$ (keeping the "$\cdots$" the same). The new subpath consumes the same bananas, so we just need to modify the way the camel carries the bananas in that subpath in such a way that the number of bananas left at each of the points involved is the same at the end of the subpath. All the bananas consumed in the shifted moves $B→A→B$ were carried through the first $B$ in the original subpath, because before that subpath the camel did not reach $C$ (otherwise the marked path would not be the "first backward chain of length at least two"), and so there were no bananas at $C$ or further. Thus in the original $P$ we could have more efficiently left those bananas at that first $B$ instead of carrying them around. In the new subpath, follow that more efficient carrying procedure, so we can clearly consume those bananas in the shifted moves $B→A→B$ since we do not need them later.

We need to prove that this iterative process terminates! One way is to count the number of inversions in the current path $P$, namely the number of pairs of positions $i<j$ such that the $i$-th point in $P$ is further than the $j$-th point in $P$ from the starting point. At each step, every point in the "$\cdots$" is at $B$ or further (as proven above), so the shift of the points $A,B$ across that does not change the number of inversions that involve positions inside the "$\cdots$". But the number of inversions involving the $A,B$ and positions in the subpath outside the "$\cdots$" does decrease by at least four due to shifting across the two $C$s. Therefore the total number of inversions decreases at each step. Since the initial path $P$ had a finite number of inversions, and the number of inversions clearly cannot go below zero, the iterative process must stop after finitely many steps.

Thus we have proven the claim, which implies that when restricted to paths with finitely many turnings, it suffices to find an optimal path among only the paths that do not go backwards twice. And then the rest of the argument in the original post proceeds.

Finally, I shall leave here an even harder exercise for the more advanced reader: The above proof only constructs a path that is optimal with respect to paths that perform finitely many turnings. Prove that this path is in fact optimal with respect to all continuous paths (on the line) with constant speed, even for those with infinitely many turnings! The reason I did not consider this issue in my original post was that in reality you cannot make infinitely many turnings.