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.

In the same format as my previous post:

A: LB 1+ 2+ 3+
B: LB 1+ 2- 3-
C: P1 1- 2+ 3-
D: P1 1- 2- 3+
E: 1+ 1- 2+ 2-

This is essentially the same idea, but the two constraints are condensed into two wires each. So A and B constrain that if 2 and 3 are the same, 1 is +, and C and D constrain that if 2 and 3 are different, 1 is -. Or it could be viewed that out of wires A, B, C, and D, all four must be used in order to have a viable circuit, and each of A, B, C and D represents one of the four "good" configurations of switches we want to let through, and each of the "bad" configurations happens to be the binary negation of one of the "good" configurations, so that wire will not be active. Wire E then contains the necessary link between the switches, and it appears you don't actually need to include one of the switches (either 2 or 3, since 1 is the one we have constraints placed on), since the one that is excluded will necessarily then be the one for which current can go through in one hop from the power source to the light bulb.

This is provably the minimum amount of wires since in order to have a viable solution, current must form a complete circuit and go through each switch at least once, and the minimum number of edges to form a closed loop that goes through exactly 5 nodes is 5.

Posted by Avin on 2006-01-20 08:28:22