Bananas to the Bazaar

You have $3{,}000$ bananas and a camel that carries at most $1{,}000$ at a time. The bazaar is $1{,}000$ miles away. Whenever the camel is carrying bananas it eats one per mile travelled; when it carries none it walks free. What is the largest number of bananas you can get to the bazaar, and how?

The Riddler, FiveThirtyEight(original post)

Solution

The detail that unlocks everything is the free walk back. The camel eats only when loaded, so an empty return trip costs nothing, and the only thing you ever pay for is a loaded mile. Three thousand bananas do not fit in one load, so to inch the whole hoard forward by a mile you must drive the camel forward loaded three times, eating three bananas for that mile. The plan, then, is to shed loaded trips as fast as you can.

A hoard of $B$ bananas needs $\lceil B/1000\rceil$ loaded passes to advance, so the cost per mile is $3$ while you hold more than $2{,}000$ bananas, drops to $2$ once you are at or below $2{,}000$, and drops to $1$ once you are at or below $1{,}000$. Cross each threshold as early as possible.

Stage 1. Start with $3{,}000$ bananas, paying $3$ per mile. Walk until the hoard falls to $2{,}000$: that costs $1{,}000$ bananas, so it happens after $$\frac{1000}{3} = 333\tfrac13 \text{ miles}.$$ Stage 2. Now $2{,}000$ bananas, paying $2$ per mile. Walk until the hoard falls to $1{,}000$: another $1{,}000$ bananas, after $$\frac{1000}{2} = 500 \text{ miles}.$$ You are now $333\tfrac13 + 500 = 833\tfrac13$ miles along, holding exactly $1{,}000$ bananas, with $166\tfrac23$ miles left.

Stage 3. A single load, paying $1$ per mile, over the final $166\tfrac23$ miles. You arrive with $$1000 - 166\tfrac23 = \boxed{833\tfrac13}$$ bananas, so you can sell $833$. Crossing the thresholds any later would drag the expensive multi-pass miles out longer, and you cannot cross them earlier, so this is the best you can do.

The computation

Encode the rule, not the answer. Track the hoard as it moves: at each moment the number of loaded passes is $\lceil \text{hoard}/1000\rceil$, and that many bananas vanish per mile. To confirm the staging is optimal rather than assumed, sweep the distance at which you first consolidate the hoard and check that the best outcome is the one above.

import math

def deliver(B, cap=1000, dist=1000):
    pos, bananas = 0.0, float(B)
    while pos < dist - 1e-12:
        passes = math.ceil(round(bananas, 9) / cap)     # loaded forward trips
        if passes <= 1:
            bananas -= (dist - pos); break
        drop = bananas - (passes - 1) * cap             # shed one pass after this
        seg = min(drop / passes, dist - pos)
        bananas -= passes * seg; pos += seg
    return bananas

print("delivered :", round(deliver(3000), 4))

def first_station(d1):                  # 3 passes for d1 miles, then play on
    b = 3000 - 3 * d1
    if d1 < 0 or d1 > 1000 or b < 0:
        return -1
    return deliver(b, 1000, 1000 - d1)

best = max((round(first_station(i / 4), 4), i / 4) for i in range(4001))
print("best, where:", best)
# delivered : 833.3333
# best, where: (833.3333, 333.25)