# Light Bulb Puzzles

You get home at night. The house is dark. You switch on the light in the hallway before proceeding upstairs to the second-floor bedroom. As you settle in for the night, you use another switch on the upstairs landing to turn off the hallway light.

Most people take such an everyday occurrence for granted. Two switches control one light, and somehow, in this instance, the upstairs switch “knows” that the hallway light is on, so flipping the switch turns the light off.

This light-switching problem is an illuminating example of the intimate link between electrical circuits and binary logic (Boolean algebra). When two widely separated switches control one light, you set up the circuit so that if the light is off, changing the state of either switch will turn it on, and if the light is on, either switch will turn it off. From a logic perspective, this arrangement is an exclusive “OR” circuit.

Light bulbs and switches have been the subject of a variety of popular and perplexing mathematical puzzles. Here’s one that Martin Gardner mentions in an article on the binary Gray code.

Imagine a light bulb connected to n switches in such a way that it lights only when all the switches are closed. A push button opens and closes each switch, but you have no way of knowing which push opens and which closes. What is the smallest number of pushes required to be certain that you will turn on the light regardless of how many switches are set at the outset?

One way of solving the problem involves using a binary Gray code. In essence, a Gray code is a way of encoding numbers so that adjacent numbers have a single digit differing by 1 (see http://mathworld.wolfram.com/GrayCode.html). For example, 193 and 183 would be adjacent counting numbers in a decimal Gray code (the middle digits differ by 1), but 193 and 173 would not be.

This switch effect is perplexing enough that it forms the basis for an amusing magic trick. Available in magic stores (sometimes under the name Electronic Monte), the device has three push-button switches and one light (see http://www.thetrickery.com/?nd=full&key=5576). “The magician demonstrates how a single button seems to control the light,” Gardner notes, “but the control mysteriously changes from one push button to another, like the pea in a three-shell game.”

One of the most widely circulated of switch puzzles focuses on a light bulb and three switches, and the solution requires you to go beyond Boolean algebra.

A downstairs panel contains three on-off switches, one of which controls the light bulb in the attic—but which one? Your mission is to do something with the switches, then determine after one trip to the attic which switch is connected to the attic fixture.

It’s impossible to tell which switch is connected to the attic fixture if all you get is one bit of information from your trip to the attic. But you can get additional information with your hand. Turn on switches 1 and 2, wait a few minutes, then turn off switch 2 before ascending to the attic. If the bulb is off, but warm, you can conclude that switch 2 is the winner. If the bulb is on, it’s switch 1. If the bulb is off, but cold, it’s switch 3.

If you can’t reach the bulb but have enormous patience, you can achieve the same effect by turning switch 2 on and then waiting several months (or longer) before turning on switch 1 and visiting the attic. If the bulb is burnt out, switch 2 is the culprit.

Recently, Lee Krasnow, who is a puzzle designer and maker currently based in New Zealand, created a bit a stir with a somewhat different lights-and-switches problem, which he shared with other puzzle aficionados via the NOBNET mailing list.

There’s an infinitely long hallway with an infinite number of light bulbs hanging from the ceiling. These lights are evenly spaced as you walk down the hallway, and they’re the type that you turn on or off by pulling on a string that hangs down from the fixture. There’s an infinitely long line of people who are waiting to walk down the hallway, pulling on the switches as they go. The first person pulls on every switch that he walks past. The second person pulls only on every second switch; the third person pulls on every third switch, and so on. In effect, person n pulls on switch m if n divides evenly into m.

If all the lights begin in the off position, which lights will be turned on once all of the people have walked down the hallway and pulled the proper switches?

When Krasnow posed this puzzle to a friend, the friend decided that all the bulbs would be off because they would all have burn out by the time an infinitely long line of people had passed down the hallway.

Aside from this technicality, the solution involves prime numbers and factors.

Interestingly, there is a finite variant of this problem, which can be found in some textbooks. Here’s a version posted by Karl Dahlke in his list of “fun and challenging math problems for the young, and young at heart” (see http://www.eklhad.net/funmath.html).

A school has 1,000 students and 1,000 lockers, all in a row. The lockers all start out closed. The first student walks down the line and opens each one. The second student closes the even-numbered lockers. The third student approaches every third locker and changes it state. If it’s open, he closes it; if it’s closed, he opens it. The fourth student does the same, and so on, through 1,000 students. How many lockers end up open?

Now, what sort of circuit would I need if I wanted to use three switches to control one light in my three-story house? Would it still work if my house had infinitely many stories, with one switch for each story?

There seems to be no end to these bulb-and-switch puzzles!