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 reply to re: AAAAAAAAAAAAAAARGH! by Tristan)

One thing that is interesting about the 4-switch problem is that the inverse is not an identical problem, as in the 3-switch problem. That is, there is no obvious way to get the light to turn on for the cases where 0, 2, and 4 switches are up and off otherwise, whereas with the 3-switch problem, the solution can easily be inverted to toggle the light bulb in the opposite way. I am guessing without too much justification other than my repeated attempts that it is in fact impossible to do the inverse in the 4-switch problem as stated - if I had been able to succeed in "reducing" the 4-switch problem to the 3-switch problem, there would have been a reversible solution of course, but that approach didn't seem to work. I would be moderately interested in the value of the proposition that by adding more power supplies, that this would be possible as well.

By the way, did you ever think about how this problem might be reworded so it would be less counter-intuitive to the physical phenomena it is supposed to resemble? In my opinion this is a great problem and I really enjoyed solving it once I was clear on the rules, but I'd be hesitant to share it with others as it is due to the odd physics going on as the problem is described. I was trying to think if there was a more intuitive graph theoretic description of the same problem (in fact I was actually trying to do this as a precursor to solving the problem itself, to see if I could reduce it to other problems I was aware of): something along the lines of a graph with (for the 3 switch problem) 8 nodes: A, B, C1, C2, D1, D2, E1, and E2, and the goal was to create edges along with constraints in some way between them so that there existed a closed loop that went through exactly one node for each letter in some way ... ? I still couldn't quite reproduce the problem with precisely the same set of requirements without making some crazy rules there too.

Anyway, I would be interested in seeing your list of "truly" unsolved problems, Tristan, since I think I once looked through the unsolved problems list (probably when I first stumbled upon perplexus) and found that most of them were either new problems or ones that had been solved by commenters but not "officially", so I stopped looking through them.

Edited on January 24, 2006, 9:21 am

Posted by Avin on 2006-01-24 09:12:12