A driver must transport 3000 apples with his truck from city A to city B. The distance between the two cities is 1000 miles and his truck can carry at most 1000 apples at once. If every mile the driver eats one of the apples he is transporting (if there are any with him), what is the optimal strategy which will insure that the least amount of apples are eaten on the way?
The optimal strategy is the following - the driver takes 1000 apples, transports them one mile away from city A, drops them there and comes back. Then transport another 1000 and so on. After there are no more apples in city A, he stars transporting the piled apples further 1 mile away towards B. He continues like this until all (remaining) apples are moved to city B. Using this strategy, the driver will eat 3.334+2.499+167=2167 apples on the way and transport 833 to city B.
It is easy to see that this strategy is optimal. To show it rigorously, without loss of generality you can assume that every day the driver transports as much apples as he can from some chosen spot on the way to 1 mile closer to city B. Also, it is always better first to transport apples from a spot which is closer to A than a spot which is further from it. These two arguments show that the suggested strategy above is optimal.