#631 - Popular Toll Bridge Tax Puzzle
You have to send 3,000 grapes 1,000 kilometers from grapecity to appleland. Your truck can carry 1,000 grapes at a time. Every time you travel a kilometer towards appleland you must pay a tax of 1 grape but you pay nothing when going in the other direction (towards grapecity).
What is highest number of grapes you can get to appleland?
Step one: First you want to make 3 trips of 1,000 grapes 333 kilometers. You will be left with 2,001 grapes and 667 kilometers to go.
Step two: Next you want to take 2 trips of 1,000 grapes 500 kilometers. You will be left with 1,000 grapes and 167 kilometers to go (you have to leave a grape behind).
Step three: Finally, you travel the last 167 kilometers with one load of 1,000 grapes and are left with 833 grapes in appleland.