The Math Thread

[Supershroom]

Here's a bonus riddle from my Graph Theory exercise sheet over the Christmas holidays. It has nothing to do with Graph Theory, so I just show it off.

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?

Spoiler: show

Apparently, with 4,500 tons in total and the sleigh carrying 1,500 tons, Santa can return to the North pole twice, and on the third go he must cross the passage. A travel away and back costs 2 tons per mile for the reindeers, so in order to leave something for later, Santa must drop at least 3 tons per mile within the area he advances in. The goal is to advance as far as possible in the first two rounds. The distance which is "revealed" thus far is exactly the amount of sweets that will be left for the kids.

Now, a first naive approach lets us advance 500 miles in the first round, using exactly 3 tons per mile. How far can we proceed in the 2nd round? We have 1,500 tons on our sleigh and 500 are on the path, aka 2,000 in total (1,000 have been fed), so the best we can go is 2000/3 = 666.6 ... miles (we declare it to be 666).

But we can do better by reducing the length of the travel distance overall, so less is fed to the reindeers, and so we already cover more than one further way on the first go. What if we drop 4 tons per mile in the 1st round? Then we can go "only" 375 miles far, but we already have covered these 375 miles for both our way off and our way back in the 2nd round! This means that overall we can use 2,250 tons instead of 2,000 in the second round, and the kids will get 750 tons.

Now, the best and optimal way is obvious. We already use five tons per mile in the first round, so even the 3rd round will be already covered by a bit (and this concludes that more than 5 tons per mile would be a pure waste). So this means that we turn back after 300 miles. Now, in the 2nd round, the reindeers eat one of the three "sweet rows" that are left on the first 300 miles, another one on their way back, and the third one in the final round. Now, with 1,500 tons still left on the sleigh, it is possible to go 500 miles further, turn back and having revealed 800 miles in total. This is the optimal solution.

[Supershroom]

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.

[1018peter]

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.

Solved on chat with Supershroom, but I think I should leave my solution here:


Split the batteries into two stacks of twenty batteries.

Check each stack separately. (20 2)= (20 * 19/2)=190 tries for each stack.

But if I have to go through TWO stacks, that means the first stack at most may only contain 1 working battery, which means there are 9 working batteries and 11 empty batteries in the other stack.

190 * 2 - (9 2) = 344

It takes 344 tries at max to find a working pair of batteries.


(Special thanks to Supershroom for helping me out with the rough ends!)

[NanTheDark]

Engineer's solution

Also I made a writing error, it should say "it doesn't turn on" instead of "it doesn't on".