Switches

By /
⏱ 3 min read

The warden meets with 23 new prisoners when they arrive. He tells them, “You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

“In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the ‘on’ or the ‘off’ position. I am not telling you their present positions. The switches are not connected to anything.

“After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can’t move both but he can’t move none either. Then he’ll be led back to his cell.

“No one else will enter the switch room until I lead the next prisoner there, and he’ll be instructed to do the same thing. I’m going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

“But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, ‘We have all visited the switch room.’ and be 100% sure.

“If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators.”

What is the strategy they come up with so that they can be free?

Solution

I haven’t written up a solution for this yet, but smarter people than I have described some on the discussion forum.

You can read their thoughts here.

2026 Update: The Light Switch Puzzle — State Encoding and Gray Code

Switch puzzles (e.g., “3 switches control 3 lights in another room, you can only visit once — identify which switch controls which light”) appear in interviews and connect to binary encoding and Gray code.

Classic solution: Toggle switch 1 for 10 minutes (bulb heats up), turn it off. Turn switch 2 on, enter room. Hot+off=switch 1, on=switch 2, cold+off=switch 3.

def light_switch_puzzle():
    """
    Simulate the 3-switch, 3-bulb puzzle with observable states:
    - is_on: currently on
    - is_warm: was on recently (was switch 1)
    """
    import random

    # Hidden mapping (unknown to solver)
    secret = {0: 'A', 1: 'B', 2: 'C'}  # switch → bulb

    # Solver's strategy:
    # Step 1: Turn switch 0 on for time T (makes bulb warm)
    # Step 2: Turn switch 0 off, turn switch 1 on
    # Step 3: Observe: on=switch1, warm+off=switch0, cold+off=switch2

    bulb_states = {}
    for switch, bulb in secret.items():
        if switch == 0:
            bulb_states[bulb] = ('off', 'warm')
        elif switch == 1:
            bulb_states[bulb] = ('on', 'cold')
        else:
            bulb_states[bulb] = ('off', 'cold')

    # Decode
    result = {}
    for bulb, (power, temp) in bulb_states.items():
        if power == 'on':
            result[bulb] = 'switch 1'
        elif temp == 'warm':
            result[bulb] = 'switch 0'
        else:
            result[bulb] = 'switch 2'

    return result

# Information theory: n bulbs identified with k visits
# Each visit: observe 2^n states. Need to identify n! possibilities.
# Min visits = ceil(log_{2^n}(n!)) ... but with physical constraints (heat) = 1 visit for 3

# Gray code: encoding sequences of switches where adjacent states differ by 1 bit
def gray_code(n: int) -> list:
    """Generate n-bit Gray code — consecutive codes differ by exactly 1 bit."""
    if n == 0:
        return [0]
    lower = gray_code(n - 1)
    return lower + [x | (1 < list:
    """G(i) = i XOR (i >> 1)"""
    return [i ^ (i >> 1) for i in range(2**n)]

print(gray_code_iterative(3))
# [0,1,3,2,6,7,5,4] in decimal
# [000,001,011,010,110,111,101,100] in binary
# Consecutive values always differ by exactly 1 bit

# Gray code applications:
# - Rotary encoders: adjacent physical positions → adjacent Gray codes
#   (no ambiguous intermediate states during rotation)
# - Karnaugh maps: rows/columns ordered in Gray code for easy minimization
# - Error correction: if 1 bit flips in transmission, only adjacent value is received

Interview connections: Switch puzzles test lateral thinking and state encoding. The deeper question is: “How much information can you extract per observation?” — fundamental to information theory. Gray code solves the “transition problem” in digital systems where multiple bits changing simultaneously cause glitches — used in ADCs, rotary encoders, and digital communications.

Scroll to Top