Appleville to Bananaville transportation

Note: This is not a perfect solution yet. Just some thoughts.

I assume that we can't divide the apples, so that you must always travel an integral number of miles.

Suppose we traverse the $n$ -th mile for $a_n$ times (in the forward direction). Then we lose $\sum_{i=1}^{1000} a_i$ apples just because we made all those trips, or in other words, we can get $3000 - \sum_{i=1}^{1000} a_i$ apples through... can we? There's another restriction, the "1000 apples at a time" limit.

If we traverse the $n$ -th mile for $a_n$ times, then we can only get at most $1000a_n$ apples past the $n$ -th mile (and $a_n$ of them are gone for the cost of the $n$ -th mile). In other words, the number of apples we can get through is at most $1000a_n - \sum_{i=n}^{1000} a_i$ apples.

I think these are all the restrictions. The number of apples we can get through is bounded above by the minimum of all of these; that is, $\min \{3000 - \sum_{i=1}^{1000} a_i\} \cup \{1000a_n - \sum_{i=n}^{1000} a_i | 1 \le n \le 1000\}$ . For the sake of brevity, let $s_0 = 3000 - \sum_{i=1}^{1000} a_i, s_n = 1000a_n - \sum_{i=n}^{1000} a_i$ , so the answer is bounded by $\min \{s_i\}$ . But there are 1000 variables to take care of; can we simplify it?

Of course we can. Clearly we need to have all $a_i$ 's to be at least 1. It also seems that no $a_i$ needs to be more than 3. And finally, it's pretty clear that the sequence of $a_i$ 's is non-increasing; if we traverse the $n$ -th mile for $a_n$ times, we don't need to traverse the $n+1$ -th mile for more than $a_n$ times, since all the load that's present can be carried in just $a_n$ trips past the $n+1$ -th mile. Thus, we can actually simplify the expression to just two variables. Let $p, q$ be integers satisfying $1 \le p \le q \le 1000$ such that $a_1 = a_2 = \ldots = a_p = 3$ , $a_{p+1} = a_{p+2} = \ldots = a_q = 2$ , and $a_{q+1} = a_{q+2} = \ldots = a_{1000} = 1$ . Now most of the $s_i$ 's are redundant (if $a_n = a_{n+1}$ , then $s_n \le s_{n+1}$ ), so $s_{n+1}$ doesn't matter. The only important terms are $s_1, s_{p+1}, s_{q+1}$ .

• $s_1 = 1000a_1 - \sum_{i=1}^{1000} a_i = 3000 - (3p + 2(q-p) + 1(1000-q)) = 2000 - p - q$
• $s_{p+1} = 1000a_{p+1} - \sum_{i=p+1}^{1000} a_i = 2000 - (2(q-p) + 1(1000-q)) = 1000 + 2p - q$
• $s_{q+1} = 1000a_{q+1} - \sum_{i=q+1}^{1000} a_i = 1000 - (1(1000-q)) = q$

Thus we're looking for $p,q$ to maximize the value of $\min \{2000-p-q, 1000+2p-q, q\}$ .

This is pretty much an integer programming problem. Had it been a normal real optimization problem, finding the best $p,q$ would be as easy as equating the three expressions together (there are two variables and there will be two equations, so there should be a unique solution--and indeed there is, $p = \frac{1000}{3}, q = \frac{2500}{3}$ , with the value of the expression being $\frac{2500}{3}$ ). But integer programming cannot be solved that way... can it?

As it turns out, this particular case can be solved approximately that way. We did get the solution $p = \frac{1000}{3}, q = \frac{2500}{3}$ , so we try the points around it, $p = 333 \text{ or } 334$ and $q = 833 \text{ or } 834$ . We find that $q = 833$ (and either choice of $p$ ) gives the value of the expression being 833, and since we know the real optimization problem has value $\frac{2500}{3} < 834$ , we know for sure that our 833 is optimal for our integer programming case.

So we know that the number of apples that we can get through is at most 833. Can we achieve this? As it turns out, yes, we can:

• Make 3 trips of 333 miles each, dumping the remaining 667 apples at the 333th mile mark.
• Make 2 trips of 500 miles each, dumping the remaining 500 apples at the 833th mile mark. (We leave 1 apple.)
• Make a trip of 167 miles, finishing with 833 apples remaining.

This corresponds precisely with $p = 333, q = 833$ . Thus the answer should be 833 . Note that this is "should be" because I'm still not very certain about the italicized parts above.

Answer: 833 apples.

Step one: First you want to make 3 trips of 1,000 apples 333 miles. You will be left with 2,001 apples and 667 miles to go. Step two: Next you want to take 2 trips of 1,000 apples 500 miles. You will be left with 1,000 apples and 167 miles to go (you have to leave an apple behind). Step three: Finally, you travel the last 167 miles with one load of 1,000 apples and are left with 833 apples in Bananaville

You should load the truck as much as possible to lose minimum number of apples.

Rest calculation can be done tediously or lazily like

1
2
3
4
5
6
7

apples=3000
for mile in range(1,1001):
    if apples%1000==0:
        apples-=apples/1000
    else:
        apples-=apples//1000+1
print (apples)