Camels
Mike Paterson gave me this puzzle a long time ago (some of the fondest moments of the time I spent being sent to Coventry was solving puzzles with Mike during lazy afternoons). You have 3000 bananas and a camel at one end of the desert that is 1000 miles wide. The camel can carry at most 1000 bananas at any time. How many bananas can you get across on the camel's back if it eats one banana before each mile of the trek across the desert?
Most of us can come up with the "right" upper bound and be convinced we can't do better. Is there is a nifty way to show the lower bound without branching off into case analysis. Is there a nice potential function perhaps?
ps: I stated this puzzle *before* my talk at a meeting at IMA and alas, lost my audience who preferred to mull over the camel munching bananas rather than focus on random projections and pseudorandom number generation.
pps: I am sure there is a version of this puzzle with tanks and gallons of gas, but the bovine camel with bananas is more enticing.
Most of us can come up with the "right" upper bound and be convinced we can't do better. Is there is a nifty way to show the lower bound without branching off into case analysis. Is there a nice potential function perhaps?
ps: I stated this puzzle *before* my talk at a meeting at IMA and alas, lost my audience who preferred to mull over the camel munching bananas rather than focus on random projections and pseudorandom number generation.
pps: I am sure there is a version of this puzzle with tanks and gallons of gas, but the bovine camel with bananas is more enticing.
posted by metoo at 9:23 AM
6 Comments:
Ok, what's the answer? I can't see how to do better than 400 bananas.
I can get 500, and my friend says he can get 533.
This is a spoiler, sorry.
***** Blinding Light *********
Trip 1: go 333 miles, leave 334 behind and return.
Trip 2: go 400 miles, leave 200 behind and return.
Trip 3: go 333 miles, replenish with the 333 there, go 67 further miles, pick up 67 from the 200 there, and finish.
--- gives a 400 bananas solution
Trip 1: go 250 miles, leave 500 behind and return.
Trip 2: Go 250 miles, replenish with 250, go upto 500 miles, leave 250 behind and return.
Trip 3: Go 250 miles, replenish with 250, go on to 500 miles mark, replenish with 250 and finish.
--- gives a 500 bananas solution.
Trip 1: go 200 miles, leave 600 behind and return.
Trip 2: go 200 miles, replenish with 200, go 333 further miles, leave 334 behind, return to 200 miles mark, replenish with 200 and return.
Trip 3. go 200 miles, replenish with 200, go 333 further miles, replenish with 333 bananas and finish.
-- gives a 533 bananas solution.
I mentioned this to John Iacono: he has a nice lower bound argument that matches the 533. In short, any solution reduces to "take as much as you can, go one step, dump whatever you can, and go back. Repeat till all bananas have been moved to step 1. Repeat". now proving a lower bound requires proving a lower bound for one step of this simplified algorithm,
it's a good one! I could not come up with the answer, so I had to google it and there it was! It was very entertaining, thank you for giving me a nice time just school!
It is a cool puzzle.
Post a Comment
<< Home