You have two tasks. You must design a 3-switch lamp and a 4-switch lamp. It is recommended that you try the 3-switch lamp first. Your design will include a lightbulb, wires, switches and power sources. The design must follow these rules:

1. You may only use 1 lightbulb for each lamp. The 3-switch lamp can only have one power source, and the 4-switch lamp must have exactly two. You may use any number of wires.
2. Every flip of a switch, no matter the previous positions, must turn the lamp from on to off or off to on.
3. Each wire may connect to any number of switches, power sources, and other wires, and to the lightbulb.
4. Each switch has two separate positions to which wires can connect. If the switch is up, then all the wires connected to position 1 are considered connected to each other. If the switch is down, all the wires connected to position 2 are considered connected to each other.
5. The lightbulb turns on if and only if there exists a complete circuit that includes both the lightbulb and at least one power source.
6. A circuit is a sequence of wires, power sources, and the lightbulb where each is connected to the next item in the sequence (the last is connected to the first). No such sequence may list the same wire, power source, or the lightbulb twice.

I recommend that you denote the different wires with letters like A, B, C, etc.

I've been thinking about this problem almost continuously for the past couple days. I had half convinced myself that it was impossible. But I just came up with this (for the four switch problem) and it appears to work:

A: LB 4+ 3+ 2+ 1+
B: LB 4- 3- 2- 1-
C: P1 1- 4+
D: P1 1+ 4-
E: 1+ 2+ 3+ 4+
F: 1- 2- 3- 4-
G: P2 2+ 3-
H: P2 3+ 2-

The lamp will turn on when exactly one or three switches are up, and will be off when 0, 2, or 4 switches are up.

The Lightbulb constrains that the two switches current comes from are different. P1 constrains that switches 1 and 4 are the same, P2 constrains that switches 2 and 3 are the same. For every valid circuit, the current will flow out of the powersource, hit a switch, go to the lightbulb, and to return it must use one of the wires that connect to the opposite power source to flip sides, go to another switch of the same side, and then back to the original power source. So each circuit will take the form:

Power source -> Up switch -> Light bulb -> Down switch -> Up switch -> Up switch -> Power source

or the inverse.

And you're right Tristan, this would not have been possible with only one power source. It was precisely in considering how an extra power source could help that I stumbled on this.

Posted by Avin on 2006-01-23 17:29:57