Your friend’s birthday is tomorrow, and he’s turning... well... the issue is that you’ve forgotten. He’s older than 1, but beyond that, he looks timeless. You’d believe it if he was 2 or 200. The birthday boy is a giant, and you're afraid that if your forgetfulness becomes known, you'll become part of the feast. The baker has meticulously prepared a small mountain range of a cake, and your job is to sculpt the giant’s age as the chocolate centerpiece. You would love to just count the candles on the cake, but you're much too small to see the top of it. Then you remember: the baker made an interior tunnel to activate the candles from below. While the giant is asleep, you can sneak in, count the candles and escape undetected.
As night sets, you pull on a full bodysuit and brace yourself for vanilla cream.
Anywhere in the tunnel, you can see whether the candle above you is lit, and can switch it on or off. Some are currently on, and others off, in no discernible pattern. The tunnel is a single loop, and in the dark you can’t tell its shape or size. You aren’t carrying anything with you, and any marks you make will disappear.
You need a strategy. How can you count the candles?
Pause here to figure it 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’s exactly one way to mark a location in the tunnel: the state of the candle. You can mark the first candle you reach by lighting it or keeping it on. If you walk forward, you’ll eventually find another lit candle— either a new one or you’re starting one. The question is: how could you know which? Here’s one approach: turn it off and backtrack to the start by passing the same number of candles you passed on the way there. If the starting candle is now off, you’ve completed the loop and know the giant’s age! Otherwise, depart again, continuing until the next lit candle, testing if it’s your starting one and so on.
This will work... eventually. But if the giant isn’t young, and many candles are on, you might have a marathon to run between now and sunrise. And you definitely don’t want to be in the cake when he starts digging in. So let’s look for a more efficient solution.
How about testing a series of hypotheses about the giant's age? Suppose you guess he’s turning 10. You could light the starting candle, walk forward 10, switch or leave the destination candle off, and return. If the starting candle’s still on, 10 isn’t the answer. If it’s off, 10 could be right, but you may have made multiple loops— so 10′s factors 5 and 2 are also possibilities. Then you would have passed a repeating pattern— but that could have just been the starting arrangement. So what if you changed the candles on the way? If you turned them all on while walking from candle 1 to 11, switch that off, then turn back, the first unlit candle you find would tell you the exact candle count. And if you don't hit any extinguished candles, you'll know that the total must be higher than 10. You could then pick a larger guess and try again.
To be systematic, you could increase your guess by the same number each time, say 4. If there were 99 candles, this method would take 24 roundtrips and involve visiting nearly 2,700 candles. But you don’t have to increase your guess linearly. For instance, you could double it, from 10 to 20 to 40, and discover the true number on your 5th trip after around 560 candles. Doubling allows you to reach high numbers quickly, while starting with small intervals in case there are only a few candles.
After expecting a lengthy trek, you’re pleased to discover the giant is only turning 12. You hurry to change into slightly more inconspicuous clothing; chisel up some enormous chocolate numbers; and at the party, make your own wish: that you’re not downwind when your friend blows out his candles.
