833 Apples, and the Surplus Apple That Rides for Free

Three thousand apples sit in town $A$. A truck holds at most a thousand at a time. The driver eats one apple for every mile he drives while carrying anything, and the empty return legs cost nothing. Town $B$ is a thousand miles away. What is the largest number of apples he can get there?

The answer is $833$. The continuous version of the problem, where apples may be fractional, gives $2500/3 = 833\tfrac13$, and the integer answer is its floor. The route to it is short once you find the right quantity to think about, and the route is surrounded by traps sharp enough that this problem is usually presented with an arithmetic error in it.

One load driven straight through

The reflex plan is to fill the truck and drive. A thousand apples, a thousand miles, one apple a mile, and the truck rolls into town $B$ with

apples. That plan is not a miscalculation. The arithmetic in (1) is exact, and it is the correct answer to the question "how many arrive if you make one trip?" It fails because the driver is allowed to do something the plan never considers: he can drop apples partway along the road, drive back empty, and come again.

Once that is on the table, a second reflex says the remaining two thousand apples are simply stranded in town $A$ and the answer is zero. That is also wrong, and the reason it is wrong is the whole problem.

Price a mile, not a trip

Stop tracking trips. Ask instead what it costs to move the entire stock forward by one mile. If $s$ apples are sitting at some point on the road and the truck holds $C = 1000$, then advancing all of them one mile requires $\lceil s/C \rceil$ loaded traversals of that mile, because each traversal carries at most $C$. Each loaded traversal of a mile costs one apple. The empty drives back are free by hypothesis. So the price of a mile is

and that is three apples per mile while more than two thousand apples remain, two while more than one thousand remain, and one after that. The cost falls as the stock falls, so the truck gets cheaper to run the longer it goes, which is the counterintuitive part.

Where the rate changes

Run the burn rate forwards. Starting from three thousand apples at three per mile, the stock reaches two thousand after

From two thousand the rate drops to two per mile, and five hundred more miles bring the stock to one thousand, so the second change of rate happens at $\tfrac{1000}{3} + 500 = \tfrac{2500}{3} \approx 833.33$ miles. The last leg is a single loaded trip of $1000 - \tfrac{2500}{3} = \tfrac{500}{3}$ miles at one apple per mile, delivering

Mile 333 is the wrong place to change gear

Here is the error this problem is usually shipped with, and it is worth dwelling on because it produces a number that is above the true optimum and therefore looks like a better answer.

The continuous switch point is mile $1000/3 = 333.33$. Round it down and write the plan as three legs of $333$, $500$ and $167$ miles. That covers the distance, and the apples eaten are

which would deliver $834$. It cannot, and the reason is a single apple. After $333$ miles at three per mile the stock is $3000 - 999 = 2001$, and $\lceil 2001/1000 \rceil = 3$. That mile still needs three loaded passes. The plan charges two, which is only possible if that one surplus apple rides along for free, and no apple rides for free.

The honest integer schedule pushes the first change one mile further out, to mile $334$, where the stock is $3000 - 1002 = 1998$ and two passes really do suffice.

I find this the most instructive part of the problem. The continuous relaxation gives the right answer to within a rounding, and it gives the wrong plan. Anyone who quotes $834$ has done the calculus correctly and then handed a fractional apple to an integer truck.

Why nothing beats 833

Equation (6) exhibits a plan that delivers $833$, so $833$ is achievable. Showing that no plan does better needs an argument in the other direction, and the argument does not need a computer.

Integrating that bound over the thousand miles gives a consumption of at least $3000 - 2500/3$ apples, so at most $2500/3$ can arrive, and since the arrivals are whole apples, at most $833$. The bound and the construction meet, so $833$ is the optimum rather than merely the best plan anyone has thought of. Note what the bound does not assume: it says nothing about keeping the apples together in one pile, which the usual dynamic-programming treatment does assume.

The general shape of the answer, for a starting stock $S$ that is a multiple of the capacity $C$ with $S = mC$, is a sum of harmonic-looking terms: the stock drops by $C$ after $C/m$ miles, then after $C/(m-1)$ more, and so on. The furthest the whole operation can reach before nothing is left is

With $C = 1000$ and $m = 3$ that is $1000 \cdot \tfrac{11}{6} \approx 1833$ miles, comfortably beyond our thousand, which is exactly why some apples survive the trip. Because $H_m$ grows like $\ln m$, doubling the reach of the operation costs an exponential pile of apples. This is the same structure as the jeep problem, and the logarithm is the reason crossing a desert twice as wide is so much more than twice as hard.

The hypothesis that decides the answer

"He eats one apple per mile whenever he is carrying anything" has two readings, and they give different numbers. Under the reading used above, the empty drives back are free. Under the other reading, the driver eats on every mile he drives, loaded or not, so a mile that needs three loaded passes also needs two empty returns and costs five apples rather than three. The rates become $5, 3, 1$ and the answer becomes $533$, not $833$.

Three hundred apples turn on a clause about return legs. A problem statement that leaves it implicit is not testing whether you can integrate a step function, it is testing whether you say your assumption out loud before you compute.

Sources and further reading

• The family this problem belongs to — Jeep problem
• The harmonic reach in equation (7) — Harmonic number
• The step function in equation (2) — Floor and ceiling functions
• How the optimality claim was settled by machine — Dynamic programming

Every number above was checked before publication. The piecewise burn rate was integrated in exact rational arithmetic, so the depot positions $1000/3$ and $2500/3$ were never rounded inside a check. An exhaustive dynamic programme over every state of the form (mile, apples in hand), with abandonment allowed and no restriction to the three-leg shape above, returns $833$ as the optimum. The same programme confirms that mile $333$ still needs three passes while mile $334$ needs two, that the one-load plan in (1) arrives with exactly zero, and that the rival reading of the statement gives $533$. Five other combinations of starting stock, capacity and distance were cross-checked against the continuous formula and agreed to within one apple.