Your friend's birthday is tomorrow, and he's turning... well... the problem is that you've forgotten. He's older than 1, but beyond that, he seems timeless. You would believe it if he were 2 or 200 years old.
You'd Love To Just Count The Candles On The Cake
But you're too young to see the top. Then you remember: Baker built an inner tunnel to activate the candles from below. While the giant is sleeping, you can sneak in, count the candles and escape without being detected.
As night falls, you don a full body suit and prepare yourself for vanilla cream. Anywhere in the tunnel, you can see if the candle above you is lit, and turn it on or off. Some are currently on, and some are off, with no discernible pattern.
The tunnel is a single loop, and in the dark you can't tell its shape or size. You're not taking anything with you, and any marks you make will disappear. You need a strategy. How can you count the candles? Stop by to find out for yourself.
Answer in 3 Answer in 2 Answer in 1 There are a few ways to solve this problem. Let's start with the most straightforward. There is exactly one way to mark the position in the tunnel: the position of the candle. You can mark your first candle by lighting it or keeping it lit.
If you keep going, you'll eventually find another lit candle—either a new one or you're starting one.
The question is, how do you know which one?
Here's An Approach
turn it off and backtrack to the start, passing the same number of candles you passed along the way.
If the starting candle is now closed, you have completed the loop and know the age of the giant! Otherwise, exit again, continue to the next lit candle, check if it's your start and so on. It will work...eventually.
But if the giant is not young, and many candles are burning, you may have a marathon to run between now and sunrise. And you definitely don't want to end up in the cake when he starts digging. So let's find a more efficient solution.
How about testing a series of hypotheses about the age of the giant?
Suppose You Think He Is Turning 10 Years Old
You can light the starting candle, advance 10, switch or skip the destination candle, and come back. If the starting candle is still on, 10 is no answer.
If it's off, 10 might be correct, but you might have created multiple loops—so factors of 10, 5 and 2, are also possibilities. Then you would have passed the repeating pattern—but that could have been just the initial arrangement.
So what if you change the candles along the way?
If you light them all, going from candles 1 to 11, turn it off, then turn back, the first burning candle you find will tell you the correct number of candles. And if you don't hit any unlit candles, you'll know that the total must be more than 10. Then you can try again with a bigger guess.
To be organized, you can increase your estimate by a single number each time, say 4. If there were 99 candles, this method would take 24 cycles and involve looking at about 2,700 candles. But you don't have to increase your estimate linearly.
For example, you can double it from 10 to 20 to 40, and discover the correct number on your 5th trip after about 560 candles. Doubling allows you to reach higher numbers faster, while starting with smaller intervals if there are only a few candles.
After expecting a long journey, you are happy to know that Dev is only turning 12. You hurry to change into a slightly more inconspicuous outfit.
Chisel Some Very High Chocolate Numbers
And at the party, make your own wish: that you are not disappointed when your friend blows out his candles.
Comments
Post a Comment