Cammy the Camel

I was the only student at my podunk high school taking AP Calculus BC during my senior year. The other students were all in Calc AB. One day, my teacher was either curious about my mathematical abilities, or just didn't feel like coming up with a lesson plan for one student, so instead he gave me a handout with this problem printed on it:

Cammy the camel has 2,000 bananas that she would like to sell at market. She lives 1,000 miles from the market, and must eat one banana for every mile travelled. She can carry up to 1,000 bananas at one time; however, she can drop some of the bananas she's carrying on the ground at any time and pick them back up later, with no limit on quantity. How many bananas can Cammy sell at the market?

It's a cute problem; no idea where it originates from. This teacher had an occasional habit of assigning his students challenges that he didn't know the full answer to — to see what they'd come up with — but I don't know if he realized this is a discrete math problem not requiring any calculus. The only higher math I knew in high school was, in fact, calculus, so I do forgive myself for not figuring out the answer at the time. Years later I did find the solution easily after remembering about ol' Cammy, though I never tried to rigorously prove its correctness. Only last week did I finally have the idea to find a complete proof (being on a discrete math kick lately), which I share here. Also, at the end of the post, there are ASCII animations, if that's more your speed.

To solve a brainteaser

The first go around I had with this problem, I was quickly overwhelmed by its sheer openness, specifically the huge number of paths Cammy can possibly take. She can choose to leave home once, twice, or ten times, and do laps on the highway before finishing up at the market. This generality makes a rigorous proof a bit challenging. However, it turns out not to be much obstacle to merely computing the correct answer.

There is a simple ansatz that a high schooler could use to quite easily find the correct answer. That is to reframe the question as an optimization problem: given that Cammy makes one trip to drop a pile of bananas before heading to market, where should she place that pile to sell the most bananas? Equivalently, let $f(x)$ be the number of bananas Cammy sells if she lays one banana pile at position $x$. What is $\underset{x}{\mathrm{max}}\,f(x)$?

Cammy eats exactly 1,000 bananas on the way to the market, so the only bananas she sells are those that she picks up from the pile; the rest go in her belly. If Cammy lays her pile at position $x$, she must eat $x$ bananas on the way there and another $x$ bananas on the way back, leaving $b(x) = 1{,}000 - 2x$ bananas in the pile. (If $x > 500$, Cammy would be stranded without enough bananas to get back home.) When Cammy returns for the pile, she eats $x$ bananas on the way, leaving room for her to pick up $c(x) = x$ more bananas. Cammy can neither pick up more than $b(x)$ bananas, the size of the pile, nor $c(x)$ bananas, her free space, so she picks up $f(x) = \mathrm{min}(b(x), c(x))$ bananas, where $x < 500$.

In piecewise form, $$ f(x) = \begin{cases} x & x < 1{,}000 - 2x \\ 1{,}000 - 2x & x ≥ 1{,}000 - 2x \land x \le 500 \\ 0 & \text{otherwise} \end{cases} $$ Here is a plot of this function:

As you can see, the maximum of $f(x)$ occurs where the curves of $b(x)$ and $c(x)$ meet, or when $$
x = 1{,}000 - 2x = 333\tfrac{1}{3}. $$ Of course, in our problem, Cammy isn't allowed to place down a fraction of a banana. Punching in numbers shows that the peak for integer $x$ occurs at $x = 333$, so Cammy sells 333 bananas.

General approach

Arriving at the number 333 is a fun little brainteaser that you can share with your friends, but the numbers have to be tuned well to make the approach in the previous section work. When Cammy's banana hoard is much larger than her carrying capacity, she has to make many trips back and forth, and it takes some additional insight to single out the ideal itinerary.

If Cammy is to sell more than bananas than her carrying capacity, she has to take multiple trips between her home and the market. Thankfully, a simple observation trivializes the problem of breaking down a trip across larger distances. If Cammy needs $k$ trips to move a pile of bananas from one position to another, she can break that trip down into any number of shorter trips using intermediate piles, as diagrammed below.

Splitting a trip (left) into multiple sub-trips (right)

Notice, in the above figure, that every mile of road is traversed exactly three times in both scenarios, so, either way, Cammy moves two loads of bananas while eating 9 of them. At the same time, we also see that moving a pile of bananas can be done no more efficiently than by hauling the entire pile one mile at a time, in as few trips needed to move that mile. The proof of this fact follows.

Complete proof

Assume Cammy begins with a pile of $B$ bananas at position $x = 0$, the market is located at position $x = D$, and Cammy can carry $C$ bananas at one time. We can describe Cammy's path by a sequence of "moves" in the form of pairs $((x_i, \delta_i))_{i=0}^n$, where

• $x_i$ is Cammy's position, satisfying $0 \le x_i \le D$ and $\left|x_{i+1} - x_i\right| \le 1$;
• $\delta_i$ is the number of bananas Cammy picks up (positive) or drops (negative) after moving to $x_i$.

From this sequence, we derive further sequences

• $h_i$, the number of bananas Cammy is holding; and
• $p_{k,i}$, the number of bananas in the pile at position $k$

according to the recurrence relations $$h_i = h_{i-1} + \delta_i - \left|x_i - x_{i-1}\right|$$ and $$p_{k,i} = \begin{cases} p_{k,i-1} & x_i \ne k \\ p_{k,i-1} - \delta_i & x_i = k. \end{cases}$$ A valid solution must satisfy the conditions $0 \le h_i \le C$ and $p_{k,i} \ge 0$. We also set the initial condition $p_{0,0} = B$.

Given a path $P$ starting at $x_0 = 0$ and ending at $x_n > 0$ with $h_n$ bananas held, we want to find a new path with the same final $x$ and $h$ values but which follows the zig-zag pattern of the previous section — at least for the first mile. Without loss of generality, we can assume that $x_{i+1} \ne x_i$ for any $i$; there are no "stationary" moves in $P$.

Our first step is to construct a path $\tilde{P}$ in which $\tilde{p}_{0,i}$ is non-increasing. Define $$p'_i \equiv \mathrm{max}\{p_{0,j} | 0 \le j \le i\}.$$ Note that $p'_i \ge p_{0,i}$. See the figure below for a visualization of how this definition modifies the original sequence.

Examples of $p_{0,i}$ and $p'_i$

Now consider the set of moves $(x_i, \delta_i)$ where $i > 0$ and $x_i = 0$. If $p_{0,i} > p'_i$, make the replacement \begin{equation} \begin{aligned} &(1, \delta_{i-1}) \\ &(0, \delta_i) \\ &(1, \delta_{i+1}) \end{aligned} \,\rightarrow\, \begin{aligned} &(1, \delta_{i-1}) \\ &(1, \delta_i - 2) \\ &(1, \delta_{i+1}). \end{aligned} \label{rep1} \end{equation} Note that, although we assumed no stationary moves in $P$, we will happily make use of them in $\tilde{P}$ to simplify the bookkeeping. Next, if $p_{0,i} = p'_i$, make the replacement \begin{equation} \begin{aligned} &(1, \delta_{i-1}) \\ &(0, \delta_i) \\ &(1, \delta_{i+1}) \end{aligned} \,\rightarrow\, \begin{aligned} &(1, \delta_{i-1}) \\ &(0, p'_{i-1} - p_{0,i}) \\ &(1, \delta_{i+1} + p_{0,i-1} - p'_{i-1}). \end{aligned} \label{rep2} \end{equation} We can easily see that $\tilde{p}_{0,i} = p'_i$. Using our recurrence relations for $h_i$ and $p_{k,i}$, we calculate for the first case that $$ \tilde{h}_{i+1} = h_{i-1} + (\delta_i - 2) + \delta_{i+1} = h_{i+1} $$ and, in the second case, $$ \begin{align*} \tilde{h}_{i+1} &= h_{i-1} + (p'_{i-1} - p_{0,i} - 1) + (\delta_{i+1} + p_{0,i-1} - p'_{i-1} - 1) \\ &= h_{i-1} + (p_{0,i-1} - p_{0,i}) + \delta_{i+1} - 2 \\ &= h_{i-1} + \delta_i + \delta_{i+1} - 2 \\ &= h_{i+1}. \end{align*} $$ Therefore, $\tilde{h}_i = h_i$ except possibly when $x_i = 0$. This establishes that Cammy has the same number of bananas at the end of $\tilde{P}$ as at the end of $P$.

To verify that $\tilde{p}_{1,i} \ge 0$ for all $i$, we show that $\tilde{p}_{1,i} \ge p_{1,i} + (p_{0,i} - p'_i)$ (except possibly when $x_i = 0$). Assume that this holds for all $j < i$. For $i$ where $x_i > 0$ and $x_{i-1} > 0$, it is clear that the hypothesis holds. If $x_i = 0$, we first check the case that $p_{0,i} > p'_i$ using \eqref{rep1}. We have $$ \begin{align*} \tilde{p}_{1,i} &= \tilde{p}_{1,i-1} - \delta_i + 2 \\ &= \tilde{p}_{1,i-1} + p_{0,i} - p_{0,i-1} + 2 \\ &\ge p_{1,i-1} + (p_{0,i-1} - p'_{0,i-1}) + p_{0,i} - p_{0,i-1} + 2 \\ &= p_{1,i-1} + (p'_{i-1} - p_{0,i}) + 2 \\ &= p_{1,i} + (p'_i - p_{0,i}) + 2. \end{align*} $$ where the last step follows from $p_{1,i} = p_{1,i-1}$ and $p'_i = p'_{i-1}$. In the other case, $p_{0,i} = p'_i$, using \eqref{rep2}, we have $$ \begin{aligned} \tilde{p}_{1,i+1} &= \tilde{p}_{1,i} - \delta_{i+1} - p_{0,i-1} + p'_{i-1} \\ &= \tilde{p}_{i,i-1} - \delta_{i+1} - p_{0,i-1} + p'_{i-1} \\ &\ge p_{1,i-1} + (p_{0,i-1} - p'_{i-1}) - \delta_{i+1} - p_{0,i-1} + p'_{i-1} \\ &\ge p_{1,i-1} - \delta_{i+1} \\ &\ge p_{1,i} - \delta_{i+1} \\ &\ge p_{1,i+1}, \\ \end{aligned} $$ where I have used $p_{1,i-1} = p_{1,i}$. This accounts for all the bookkeeping needed to confirm our claim about $\tilde{P}$.

Now that we shown that we can make $p_{0,i}$ non-increasing, converting $P$ to the form described in the previous section is simple. If $x_i = 0$, make the replacement $$ \begin{aligned} & \\ & \\ &(0, \delta_0) \\ &\quad\vdots \\ &(1, \delta_{i-1}) \\ &(0, \delta_i) \\ &(1, \delta_{i+1}) \end{aligned} \,\rightarrow\, \begin{aligned} &(0, \delta_i) \\ &(1, -\delta_i + 2) \\ &(0, \delta_0) \\ &\quad\vdots \\ &(1, \delta_{i+1}) \\ &(1, \delta_i - 2)) \\ &(1, \delta_{i+1}). \end{aligned} $$ Thankfully, the induction argument here is far easier to work out. The numbering here is a bit of a nuisance, but it can be made consistent by inserting dummy $(0, 0)$ moves to the start of the original sequence, so that it looks like this: $$ \begin{aligned} &(0, 0) \\ &\quad\vdots \\ &(0, 0) \\ &(0, \delta_{2k}) \\ &\quad\vdots \end{aligned} $$ where $k$ is the number of replacements made. With this, it is easy to see that $\tilde{h}_i = h_i$, except possibly at some of the modified moves. You can also see that $$p_{1,2k} = \sum_{j > 2k,\,x_j = 0} (\delta_j - 2),$$ which ensures that $p_{1,i} \ge 0$ throughout. We additionally have that $\tilde{p}_{k,n} = p_{k,n}$ for $k > 1$, meaning that any extra loads Cammy drops off at the market are preserved as well. I encourage you to do the math on pencil and paper to confirm that this works.

So, now we've shown that we can rewrite any path into two phases: first, moving a number of bananas from the pile from $x = 0$ to $x = 1$, then continuing on in the original fashion but without revisiting $x = 0$. By repeated application of this process, we can replace any path with a path that arrives at the same endpoing, with the same number of bananas held, consisting entirely of moving bananas between $x$ and $x + 1$, then never returning to $x$ again. In particular, the optimal path to the market can be rewritten in this fashion, proving that this is the best possible strategy for Cammy to move her bananas.

Note that some bananas may be left behind by this process. In particular, if Cammy is at position $x$ and the pile at $x - 1$ has 2 or fewer bananas, there is no need to go back for them. This is the stopping condition for Cammy to quit moving bananas from $x - 1$ to $x$ and to start moving bananas from $x$ to $x + 1$.

Addendum: animations

Initially, I greatly underestimated how long it would take to formalize my napkin math and write up the above proof. Instead of diving into the slow and hard work, I spent some time screwing around writing code. When looking for my proof, I thought it would be insightful to use an algorithm to search for solutions to Cammy's problem and visualize the results. I ended up implementing parallelized BFS to search for optimal paths, which was a fun exercise. View the source code on GitHub.

Unfortunately, even for small inputs, the state space greatly exceeded the 64GB of RAM I had available. On the bright side, the ASCII visualizer I wrote using asciicast produced some fun-looking animations, which you can take a look at below.

The "standard" approach

The "leapfrog" approach

A solution found by BFS