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.

As I posted on the forum, I keep coming back to this problem, although I haven't worked on it significantly for a while. After seeing Tristan's solution for the 3-switch problem, I realized that I was interpreting the problem wrongly (one of the remaining biggest flaws in my thinking was that I did not realize that a "wire" could have multiple endpoints that current could go through if at least two endpoints were active).

Anyway, Tristran's solution seems to me easier to understand if you view it by the endpoints of each wire:

A: P1, 1+ 3+
B: P1, 1- 3-
C: P1, 2-

D: LB, 1+, 3-
E: LB, 1-, 3+
F: LB, 2+

G: 1- 2-
H: 1+ 2+
I: 2+ 3+
J: 1+ 2-

(1+ and 1- denote the two opposing ends of switch 1, and so on).

I can actually improve on his solution, by using less wires:

A: P1, 1+ 3+
B: P1, 1- 3-
C: P1, 2-

D: LB, 1+, 3-
E: LB, 1-, 3+
F: LB, 2+

G: 1- 2- 3- 1+ 2+ 3+

The reasoning is that in his solution, wires G-J are largely irrelevent, and can be condensed into a single wire that allows you to get to any side of any switch from any other side of any other switch. The important parts are wires A-C, which act as constraints on the Power Source, and D-F which act as constraints on the LightBulb. In order to have a circuit, at least two of each of those sets of three wires must allow current to flow through them. In fact, we can reduce these constraints to very simple logical statements:

A-C: "If switches 1 and 3 are in the same position, then switch 2 must be down (-)."

D-F: "If switches 1 and 3 are in opposing positions, then switch 2 must be up (+)."

The way this works is that wires A and B, and also D and E, are mutually exclusive with regards to switches 1 and 3. So if switches 1 and 3 are in such a configuration that will allow current only to wire A and not wire B (if they are both up), the second wire that connects to the power source will have to be C, which ensures that switch 2 is down. If A and B are both down, the same situation occurs where C must be used.

Now the intersection of these two constraints is sufficient for the 3-switch problem: you have 8 possible configurations of switches (2^3), and each constrain eliminates 2, which leaves 4 remaining good configurations that correspond to being able to flip any switch and have the status of the lightbulb toggle.

If we try to apply a similar solution to the 4-switch problem, we run into difficulties. We can try to apply separate constraints to both power sources, but the biggest hurdle I am facing is that the lightbulb is common to each power source. I have thus far not been able to come up with a reasonable constraint for the light bulb: every configuration of wires seems to either eliminate too much or too little. I've come very close, coming up with a configuration of wires that allows the light to be on (or off) for 10 of the 16 configurations of switches; actually I've come up with several such configurations, but I have yet to nail down any reasonable way of getting the magic 8.

Then I tried "reducing" the problem to the 3 switch problem: one power supply is connected via 2 wires to 4+, and the other power supply is connected via 2 other wires to 4-. The idea then is that 4+ replaces the power supply of the 3 switch problem, and somehow to make 4- be the inverse of that, but I have been unsuccessful in doing that, primarily for the same reason as above: the lightbulb must have the same constraint for both power supplies, which then eliminates the wrong configurations for one or the other power supply.

... unless I'm still misunderstanding part of the problem.

Edited on January 19, 2006, 3:50 pm

Edited on January 19, 2006, 3:52 pm

Posted by Avin on 2006-01-19 15:47:52