Can you solve the birthday cake riddle? - Marie Brodsky
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.
