Global Reset

Switch Puzzles

Posted by Scott Hughes Thu, 29 Sep 2005 22:55:00 GMT

Recently, Harry Binswanger posted a logic puzzle to his mailing list that went something like this:

One hundred prisoners and a warden agree to play the following game. Each day, starting tomorrow, the warden will select a prisoner at random and lead him to a room that contains nothing but a lamp standing in the center of the room. The prisoner may do one of three things:

• Switch the lamp on if it is off, or switch it off if it is on, and then head back to his cell.
• Do nothing and head back to his cell.
• Announce: “All 100 prisoners have visited this room.”

If a prisoner makes such an announcement, and he is correct, then all 100 prisoners will be set free. If not, all will be executed. The game will continue until someone makes an announcement.

Knowing that they are about to play, what strategy can the 100 prisoners agree upon to ensure their freedom? Assume that the lamp is initially on and that all prisoners know this.

I found the answer pretty quickly when I realized that it didn’t really matter how long it took. If it takes 50 years, it I guess it still beats spending Life in prison.

Today, I stumbled upon an interesting variation that took a little bit more thought for me to solve. The twist (which might actually be the more popular telling) is that there are two switches, the initial position is unknown, and every prisoner must change the state of just one switch each time they go into the room. Not knowing the initial state makes this a bit more challenging, but the solution is extremely similar for my earlier phrasing of the problem.

Here’s one more that I found while searching for light switch puzzles that requires a completely different line of thought to solve:

Downstairs there are three light switches on panel. You are told only that one switch will turn on a light in the attic (which cannot be seen from the basement). With just one trip from the ground floor to the attic is it possible to determine which of the three switches operates the attic light?