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.

via Math puzzles.

667 apples. Can we do better than that?

Maybe. I don't have a converse proof.

I got to 889 by moving 1/3rd of the distance everytime.

1/3RD: 3 carts of 1000 brings 2000 Apples here

2/3RD: 2 carts of 1000 brings 2000*2/3 Apples here. (1000+1000*1/3)

FULL Distance: 1000*2/3(First Cart) + 1000*2/9 (Second Cart) = 8000/9 = 889 (approx)

Oops Sorry. 667 The second cart will never make it with the 333 Apples.

Don't you have to eat bananas while moving backwards also?

Nvm. He eats apples only when he HAS APPLES on board, so you are good

The other version of this problem I had will HAVE TO eat 1 apple per mile and must ensure he always has apples. In that case:

Round 1: Checkpoint Distance 200miles. 5 rounds needed to transport 3000 apples. 200*5=1000 exhausted. 2000 remaining.

Round 2: Checkpoint Distance 333.33miles. 3 rounds required. 333.33*3=1000 apples consumed. 1000 remaining.

Round 3: Remaining distance of 1000-200-333.33=466.67miles. 466.67 apples consumed, remaining 533.33 apples.

Since the granularity of eating apples is 1 mile, the best strategy would be to transport full-cart (i.e. 1000 apples whenever possible) over 1 mile every time, and the number of apples delivered thereby would be 833.

Just to give details, until you reach 334 miles, you would need to make 3 trips for every mile (and lose 1 apple per trip for a total loss of 3x334 = 1002 apples). From there on, until 833 miles (i.e. for the next 499 miles), you would need to make 2 trips for every mile (and lose 2x499 = 998 more apples).

So now you're stuck at 1000 apples at 833 miles. Just make one more trip to reach the destination (and lose 167 more apples in the process). So the total number of apples delivered is 833. Anything wrong?

Seems right!

for 3000 apples to be transported he need to make 3 trips(i.e. Up and Down for 1st 1000 apples UP and Down for 2nd 1000 and Up for 3rd 1000 apples) one trip means 1 up and 1 down i.e 2*UP. This comes out like 5 times he is travelling the same path for 3000 apples. So for 200 mile he will consume 1000 apples leaving 2000 apples. Similarly it takes 2 trips for 2000 apples i.e.Up and Down and again Up. So after 333 meters more he will consume 999 apples, 1001 remaining. Leaving 1 apple behind he will eat 467 apples for remaining distance thus transporting 532 apples max.

is there any optimality proof for this? any resemblance with some famous algo?

@Ravi: Not sure. I have tried for a while to obtain an optimality proof. Need some systematic argument. If you come up with one, please share

I get 833 delivered after a final trip that's "eats" up 167 apples. Notice that 833<1000, so only a single final trip is required which I believe is key to optimizing the amount delivered.My logic to arrive at the depot with exactly 1000 meant having two trips each carrying 500 apples over some distance. Going 499 miles twice does the job. 167(once)+499(twice) meant the first trip was 334 miles. 3X334=1002.3000-1002=998< 2000, which is important for that require two trip wheras 2001 or more requires 3 trip. I am having trouple "generalizing" a solution or coming up with an equation that finds a max. delivery. Thoughts please?

Hi, I am not sure of a converse proof for this puzzle. I am looking for one. Let me know if you find one.

It seems like you always want to travel (# of remaining miles) * (1 / (# of apples left / carrying capacity of car)). Just a guess though.

Have you considered moving the apple addict to the banana truck?