The distance between the towns A and B is 1000 miles.  There is 3000 apples in A, and the apples have to be delivered to B. The available car can take 1000 apples at most. The car driver has developed an addiction to apples: when he has apples aboard he eats 1 apple with each mile made.  Figure out the strategy that yields the largest amount of apples to be delivered to B. Generalize the strategy for an arbitrary amount of apples.

Apple drawing from  Dolly Smith's Web Page

Solution

There's a few ways to go about this.  The first is to cheat the problem:  The driver eats one apple each mile, so have him take one apple 0.999 miles, and repeat for every apple and every mile of the trip.  They'll probably be rotted by the time they arrive, but all 3000 will reach B.

Another way is to assume he starts eating a new apple each mile, and it takes the mile to finish it off.  For any single trip it's clear that the maximum apple delivery occurs when the trip starts with a full truck.  Therefore, you want the final leg to have a multiple of 1000 apples present.  That means either 1000, 2000, or 3000 when you start with 3000.  3000 is obviously bad, as each of the three trips delivers zero apples. 

Try 2000:  Since you began with 3000 there will be three trips, each of 334 miles, leaving you with 666 miles to go and 1998 apples.  If the next leg is the final one then there are two trips of 666 miles with 999 apples, for a total delivery of 666.  But there's still the option of starting the final leg with 1000, which means two trips of 499 miles with 999 apples, leaving 1000 apples with 167 miles to go, for a final delivery of 833 apples. 

With 1000 the first three trips are each 667 miles, leaving 333 miles for the last leg with 999 apples, again giving 666 delivered.

This leads to a general recursive solution:  Each leg of the trip reduces the number of loads by one until the trip is complete.  Notation is miles left(apples left)

2000:  500 (1000) 0 (500)
3000:  666 (1998) 167 (1000) 0 (833)
4000:  800 (3000) 466 (1998) 0 (1064)
9000:  888 (7992) 763 (6992) 621 (5998) 454 (4996) 254 (3996) 4 (2996) 0 (2984)
 

Delivery truck drawing from Genealogy.com

Since the apples are quantized there is obviously an upper limit to the number of legs; with 2 million apples the initial trip would want to be 0.5 miles, but going 1 mile results in the same number of apples, so really this looks like doing 1 million apples twice. I can't remember enough math to put the series into a

closed form, so the verbal description will have to do...

Jack