Another spin on a classic: Transporting Apples

[BMAD]

A truck driver needs to transport 3000 apples to a local business. His truck can only hold 1000 apples. However, complicating the apple delivery is the drivers habit of eating his delivery apples while driving. If there are any apples in the truck, the driver will manage to eat 1 apple per mile.

What is the best means for the driver getting the apples to the market (eating the fewest apples while making the delivery)?

Assume that there is a safe fruit storage points along the way and that time or gas is of no issue.

[plasmid]

Up until he gets the 3000 apples to his destination, he will have to transport more than 3000 apples through any point "A" along the way and will need to make at least four trips carrying apples from point A to his final destination. In order to move a bunch of apples from point A to his destination if he brings them in four hauls, he would essentially be eating 4 apples per mile from point A to the destination. If point A is 250 miles from his destination, then to bring four hauls of apples from point A to the destination he would eat 1000 apples, and therefore would have to start at point A with 4000 apples. At any point farther away from his destination than that, he would have to have more than 4000 apples and therefore need to bring them forward in at least five hauls.

The pattern of how this progresses should now be obvious.

If we allow him to slice the apples that he's going to eat along the way and eat fractions of apples for fractions of miles, then going backwards from his destination, we would have:

Destination - 3000 apples

Point A - 4000 apples - 250 miles from destination

Point B - 5000 apples - 200 miles from point A and 450 miles from destination

Point C - 6000 apples - 166 2/3 miles from point B and 616 2/3 miles from destination

Point D - 7000 apples - 142 6/7 miles from point C and 759 11/21 miles from destination

Point E - 8000 apples - 125 miles from point D and 884 11/21 miles from destination

Point F - 9000 apples - 111 1/9 miles from point E and 995 40/63 miles from destination

To get from the start to point F which is 4 23/63 miles away in 10 trips, eating 10 apples per mile, he would consume 43 41/63 apples along the way. So he would have to start with 9043 41/63 apples.

That raises the question of whether his supplier is frugal enough to want to cut an apple into 63 pieces and try to sell the remaining 22 slivers of apple. If he were, I doubt he'd want to hire someone who'll eat twice as many apples as he delivers.

[bonanova]

Assume the business is 3000 miles away. The driver will consume all the apples.

Assume the business is one inch away. Almost any scheme delivers all the apples.

So, don't we need to know how far away the business is?

Or should we take the distance to be x<3000 and optimize for each x?

[BMAD]

Assume the business is 3000 miles away. The driver will consume all the apples.

Assume the business is one inch away. Almost any scheme delivers all the apples.

So, don't we need to know how far away the business is?

Or should we take the distance to be x<3000 and optimize for each x?

oops. I meant to also state that the business is 1000 miles away.

[plasmid]

Does the driver start off with 3000 apples and need to deliver as many of them as possible to his destination, or does he need to end up with 3000 apples at his destination while starting the delivery with as few apples as possible?

[BMAD]

Does the driver start off with 3000 apples and need to deliver as many of them as possible to his destination, or does he need to end up with 3000 apples at his destination while starting the delivery with as few apples as possible?

He needs to deliver 3000 apples from some unlimited supply of apples eating as few of them along the way as possible.

[vinay.singh84]

Assume the business is 3000 miles away. The driver will consume all the apples.

Assume the business is one inch away. Almost any scheme delivers all the apples.

So, don't we need to know how far away the business is?

Or should we take the distance to be x<3000 and optimize for each x?

oops. I meant to also state that the business is 1000 miles away.

How does that qualify as local?

[BMAD]

Assume the business is 3000 miles away. The driver will consume all the apples.

Assume the business is one inch away. Almost any scheme delivers all the apples.

So, don't we need to know how far away the business is?

Or should we take the distance to be x<3000 and optimize for each x?

oops. I meant to also state that the business is 1000 miles away.

How does that qualify as local?

it is all a matter of scale, semantics, and poor translations.

[bonanova]

Assume the business is 3000 miles away. The driver will consume all the apples.

Assume the business is one inch away. Almost any scheme delivers all the apples.

So, don't we need to know how far away the business is?

Or should we take the distance to be x<3000 and optimize for each x?

oops. I meant to also state that the business is 1000 miles away.

How does that qualify as local?

The OP might mean the store sells only to nearby customers.

As opposed to a national chain or a wholesale distributor.

[dgreening]

The problem statement says

• "His truck can only hold 1000 apples."

​the update says that the store is 1000 miles away

If the driver starts with a full load [1000 apples] and drives 1000 miles, he will have 0 apples left upon arrival.

Thus, unless he can ferry apples to some point(s) in between and then move these forward, there is no way to every deliver even 1 apple.

If we assume that there is a point halfway [500 miles] then he could do the following:

• leave the warehouse with 1000 apples
• drive 500 miles [now has 500 apples]
• leave the apples at the halfway point [now has 500 apples]
• drive back to the ware house
• leave the warehouse with 1000 apples
• drive 500 miles [now has 500 apples]
• Picks up 500 the apples at the halfway point [now has 1000 apples in the truck and 0 apples at the halfway point]]
• Drives the remaining 500 miles to the store and delivers 500 apples

Thus for 2 trips[500 and 1000 miles one way (3000 miles total round trip)] 500 apples can be delivered

to deliver 3000 apples would require:

• an interim storage area at 500 miles
• 6 "short" round trips between the warehouse and the interim storage area [1000 miles R/T each]
• 6 "long" round trips from the warehouse [stopping at the interim storage area to reload] to the store [2000 miles R/T each]

Notes:

• you can break this up many ways
• it is not clear what the optimal interim storage area distance [from the ware house] is [and if more than 1 helps]

[DeGe]

The problem statement says

• "His truck can only hold 1000 apples."

​the update says that the store is 1000 miles away

If the driver starts with a full load [1000 apples] and drives 1000 miles, he will have 0 apples left upon arrival.

Thus, unless he can ferry apples to some point(s) in between and then move these forward, there is no way to every deliver even 1 apple.

If we assume that there is a point halfway [500 miles] then he could do the following:

• leave the warehouse with 1000 apples
• drive 500 miles [now has 500 apples]
• leave the apples at the halfway point [now has 500 apples]
• drive back to the ware house
• leave the warehouse with 1000 apples
• drive 500 miles [now has 500 apples]
• Picks up 500 the apples at the halfway point [now has 1000 apples in the truck and 0 apples at the halfway point]]
• Drives the remaining 500 miles to the store and delivers 500 apples

Thus for 2 trips[500 and 1000 miles one way (3000 miles total round trip)] 500 apples can be delivered

to deliver 3000 apples would require:

• an interim storage area at 500 miles
• 6 "short" round trips between the warehouse and the interim storage area [1000 miles R/T each]
• 6 "long" round trips from the warehouse [stopping at the interim storage area to reload] to the store [2000 miles R/T each]

Notes:

• you can break this up many ways
• it is not clear what the optimal interim storage area distance [from the ware house] is [and if more than 1 helps]

Yes, but for returning also he would need to eat apples

So, if he goes 500KM, he would eat 500 while going and 500 while coming back.

533

[BMAD]

The problem statement says

• "His truck can only hold 1000 apples."

​the update says that the store is 1000 miles away

If the driver starts with a full load [1000 apples] and drives 1000 miles, he will have 0 apples left upon arrival.

Thus, unless he can ferry apples to some point(s) in between and then move these forward, there is no way to every deliver even 1 apple.

If we assume that there is a point halfway [500 miles] then he could do the following:

• leave the warehouse with 1000 apples
• drive 500 miles [now has 500 apples]
• leave the apples at the halfway point [now has 500 apples]
• drive back to the ware house
• leave the warehouse with 1000 apples
• drive 500 miles [now has 500 apples]
• Picks up 500 the apples at the halfway point [now has 1000 apples in the truck and 0 apples at the halfway point]]
• Drives the remaining 500 miles to the store and delivers 500 apples

Thus for 2 trips[500 and 1000 miles one way (3000 miles total round trip)] 500 apples can be delivered

to deliver 3000 apples would require:

• an interim storage area at 500 miles
• 6 "short" round trips between the warehouse and the interim storage area [1000 miles R/T each]
• 6 "long" round trips from the warehouse [stopping at the interim storage area to reload] to the store [2000 miles R/T each]

Notes:

• you can break this up many ways
• it is not clear what the optimal interim storage area distance [from the ware house] is [and if more than 1 helps]

Yes, but for returning also he would need to eat apples

So, if he goes 500KM, he would eat 500 while going and 500 while coming back.

533

very very close. consider the fact that the store he delivers to accepts and sells parts of apples to

[plasmid]

Wait, does the driver have to have apples in his truck and be eating them in order to drive?

If so, then I'll have to change my answer in post 6. I was thinking that he only ate apples if there were any in his truck, but he could drive without eating apples if he wasn't carrying any.

[BMAD]

Wait, does the driver have to have apples in his truck and be eating them in order to drive?

If so, then I'll have to change my answer in post 6. I was thinking that he only ate apples if there were any in his truck, but he could drive without eating apples if he wasn't carrying any.

very good point plasmid, the way i wrote the op is that he only eats apples if he has them so i made a mistake when i made my previous post. now the other answer is close if he was eating to drive.

[DeGe]

very very close. consider the fact that the store he delivers to accepts and sells parts of apples to

selling an apple that is 2/3rd eaten would be difficult

But if you insist, add 1/3 to my previous answer

[BMAD]

very very close. consider the fact that the store he delivers to accepts and sells parts of apples to

selling an apple that is 2/3rd eaten would be difficult

But if you insist, add 1/3 to my previous answer

that bellies the assumption that he must have apples to drive. which is not the case. he only eats apples while driving if they are available.

ps. you are also answering a different question.

[DeGe]

that bellies the assumption that he must have apples to drive. which is not the case. he only eats apples while driving if they are available.

ps. you are also answering a different question.

If he eats apples only if they are available, it is much simpler then

He takes 3 trips carrying 1000 apples on each trip to a distance of 333 1/3 miles

Now he has 2000 apples left.

Now he takes 2 trips of 500 KMs each; he has 1000 apples left and has covered 833 1/3 miles

He drives the remaining 166 1/3 miles and delivers 833 1/3 apples to the store.

Although a better way could be for the driver to drive an empty truck to the local store and explain the problem. Let the local store send a non-apple-eating driver with the truck who makes 3 trips delivering all the 3000 apples.

[Rainman]

He needs 9000 + 10000*(1-1/4-1/5-1/6-1/7-1/8-1/9) apples. He drives 10 trucks with 900 + 1000*(1-1/4-1/5-1/6-1/7-1/8-1/9)<1000 apples each, for 1000*(1-1/4-1/5-1/6-1/7-1/8-1/9) miles, ending up with 9000 apples at that point. He proceeds to drive 9 trucks of 1000 apples each, for 1000/9 miles, ending up with 8000 apples at 1000*(1-1/4-1/5-1/6-1/7-1/8) miles along the way. He now drives 8 trucks with 1000 apples each, for 1000/8 miles, ending up with 7000 apples at 1000*(1-1/4-1/5-1/6-1/7) miles along the way. Repeating this process, he eventually ends up with 4000 apples at 1000*(1-1/4)=750 miles along the way. He drives 4 trucks with 1000 apples each, for the remaining 250 miles, ending up with 3000 apples at the store.

[BMAD]

He needs 9000 + 10000*(1-1/4-1/5-1/6-1/7-1/8-1/9) apples. He drives 10 trucks with 900 + 1000*(1-1/4-1/5-1/6-1/7-1/8-1/9)<1000 apples each, for 1000*(1-1/4-1/5-1/6-1/7-1/8-1/9) miles, ending up with 9000 apples at that point. He proceeds to drive 9 trucks of 1000 apples each, for 1000/9 miles, ending up with 8000 apples at 1000*(1-1/4-1/5-1/6-1/7-1/8) miles along the way. He now drives 8 trucks with 1000 apples each, for 1000/8 miles, ending up with 7000 apples at 1000*(1-1/4-1/5-1/6-1/7) miles along the way. Repeating this process, he eventually ends up with 4000 apples at 1000*(1-1/4)=750 miles along the way. He drives 4 trucks with 1000 apples each, for the remaining 250 miles, ending up with 3000 apples at the store.

Plasmid's answer is more efficient in terms of the amount of apples to be used.

[Rainman]

Actually we have the same amount of apples used, but he was more efficient in terms of answering first

9000 + 10000*(1-1/4-1/5-1/6-1/7-1/8-1/9) = 9043 + 41/63

Edited July 19, 2013 by Rainman

[BMAD]

LoL, my mistake