runouw.com

Christmas is almost here, and Santa Claus shall make all kids in the world happy with sweets. To reach the civilized world from the North Pole, he must first cross a 1,500 miles long passage full of ice and snow. Because it is so exhausting for his fleet of reindeers, they have to be fed with one ton of sweets after each mile they go (apparently, the size of the fleet in detail doesn't matter). As soon as the passage is traversed, the reindeers can take off and fly everywhere all the way withou needing any more sweets or other food, and once the gift-giving is done, they can even fly the way back to the north pole.

Now, stupidly, Santa's sleigh can only carry 1,500 tons of sweets at most! Does this mean that Christmas must be cancelled? Luckily not, because although the passage is so damn exhausting, it's still not so forbidding that you couldn't drop and store any sweets on mid-path, and knowing in advance, Santa has produced 4,500 tons of sweets at the North pole. So, his strategy must be to travel a certain fraction of the passage, store some sweets, go back, relade the sleigh etc. until he must traverse the passage (the reindeers are cooperative of course). What is his optimal strategy and how many tons of sweets will be left for the children?

Supershroom wrote:Back so soon am I? Now this seems to be a real brain teaser, I don't have a safe solution for it yet. (from my graph theory exam, but is it really connected to graph theory?)

Here's the thing: You have 40 batteries, 10 are full (working) and 30 are empty. You don't know which ones are working or not. You have a flashlight with two batteries; it only flashes up if both batteries put in are working. Now, your objective is to forcedly find a pair of two working batteries with as few tries as possible.

I mean, my approach was: If the torch flashes up, you have a pair of two full batteries. Then you're lucky. The only thing you can try to be after forcedly is showing that a battery is not working. So, I've picked up 2 batteries, calling them A and B. If the torch doesn't flash, there are three cases: Only A is working, only B is working, or both are not working. I'm trying to check the premise "A is working". So I check other batteries together with A, and there is 9 working batteries left (since I assumed A is working) and 29 empty ones (since B cannot work, as I also assumed). At the 30th check latest I meet a full battery, and if even then no pair has flashed up, I can say clearly that A cannot be working.

Same I do with B, if I have to. After that I've needed 61 tries (1 + 30 + 30). Then I compare two other batteries, C and D, and this time, to prove that they're not working, I need 2 comparisons less on each (since A and B have shown not to be working). This makes 4 comparisons less this time, so 57 in total. And so it goes on if I'm not lucky. The total sum of tries I could meet is 61 + 57 + 53 + ... + 13 + 9 + 5 = 495. At the latest after that, I've found all non-working batteries and any of the other 10 I put in make the torch flash.

I would be extremely stunned if there was an even better strategy (and also be pissed since I would lose points on the exam). Discuss if you want.