How Quickly Can You Label
Your Circuit Breaker Box?
You start by switching all 100
lights in the house to “on,” and then head to the basement to
begin the onerous mapping process. On every trip to your
basement, you can switch any number of circuit breakers on or
off. You can then roam the hallways of your mansion to discover
which lights are on and which are off. What is
the minimum number of trips you need to make to the basement to
map every circuit breaker to every light?
HINT Don't try switching on or off the
light switches in your house or feeling how hot the lightbulbs
are. Think about solving for the case of 10 unlabeled circuit
breakers first.
Solution
The simplest strategy
would be to switch each circuit breaker off one at a time. This
would take 99 trips to the basement (the 100th circuit breaker
would be mapped by the process of the elimination).However, by
using the right strategy, you can solve the riddle much easier.
In fact,
you can map all 100 circuit breakers to their
respective lights in just seven trips to the
basement!
HOW?
Place a piece of masking
tape on each circuit breaker and on each light. On the first
trip to the basement, flip 50 circuit breakers to off. Mark
these circuit breakers with a "0." Mark the 50 circuit
breakers that are on with a “1.” As you roam around
the house to tally the lights, mark the 50 lights that are off
with a “0” and mark the other 50 lights with a "1."
On your second trip to the basement, keep off half of the
circuit breakers that are marked with a "0," turn off half of
the circuit breakers that are marked with a "1," and mark all of
these circuit breakers with a second number of "0." Flip on all
other circuit breakers if they’re not already on, and mark their
second number as "1." Now go around the house, and again mark
the lights that are off with a "0" and those lights that are on
with a "1."
By the end of this step, all of your circuit breakers and lights
will be marked with either "00," "11," "10" or "01." In fact,
you’ve completely separated the matching problem into four
different groups of 25—i.e., all lights must be matched to a
circuit breaker with their same two-digit code.
Continue this process: In the third trip, flip half (or
actually, 13 since 25 is an odd number) of all of the circuit
breakers in each group ("00," "11," "10" and "01") to off, and
mark them with an additional "0." Mark the 12 "on" circuit
breakers in each group with a "1." Go around the house, and once
again mark all lights that are off with a "0" and all lights
that are on with a "1."
You’ll have created eight different groups of either 12 or
13 lights and circuit breakers: "00," "100," "011," "111,"
"010," "110," "001" and "111." The lights still must be matched
to a circuit breaker with the same three-digit string.
After your fourth trip, you’ll have subdivided the groups into
16 groups with either six or seven lights and circuit breakers
in each group. After the fifth trip, you’ll have 32 groups with
three or four lights and circuit breakers in each. And after the
sixth trip, you’ll have either one or two lights or circuit
breakers in each group.
For those groups that each have one light and one circuit
breaker, you’ve successfully mapped those circuit breakers to
their lights! For the rest, it takes only one more trip—the
seventh trip—to finally map them to their respective lights.
If you’re familiar with binary numbers, you’ll recognize that
there are exactly 128 numbers that use seven digits, 0000000 to
1111111, which may help to explain why this strategy works so
well: Each circuit breaker and light ends up with a unique
“code” that maps to a specific binary number.
Using this strategy, you can map up to 256 circuit breakers in eight trips,
512 circuit breakers in nine trips and 1,024 in ten trips!