### Beautiful Simplicity

As a child I was fascinated by a pair of switches in our house that controlled a light upstairs. There was one switch at the bottom of the stairs and another at the top that controlled the same light. Flipping either switch could turn the light on or off. For a long time I couldn't figure out how this worked: how did the switch downstairs "know" the light was on or off and "know" how to change the light? How did the two switches "communicate" with each other?

After much experimentation I unscrewed the switch downstairs and looked at the wiring. I was surprised to discover three wires (and three upstairs as well) and finally figured out that the switches were wired as follows with two switches in blue that can flip between two poles. Flipping either switch changes the state of the lamp from on to off, or off to on.

Later I visited a friend's house and discovered that they had three switches controlling a single lamp. That requires a more complex switch that can flip between two states connecting either the two wires straight through or in an X pattern like this:

You might like to stop here and look at those two diagrams and convince yourself that flipping any switch can turn the lamp on or off. Once you've done that notice that there aren't really two different sorts of switch at all, you could do this with three switches that flip between the straight through and X positions (just with some wires left unconnected).

Once you make that step, it doesn't take a lot of imagination to realize that this scheme will work for any number of switches. You can connect an arbitrary number of switches together in this fashion to control a single lamp. Here are four such switches connected together. You might like to pause again and convince yourself that this would work:

Now you can use a mathematical technique to prove that this will work for any number of switches. The technique is induction. The idea is that if you can prove something true for some base case (that this works with one switch), and you can prove that if it works for n switches it'll work for n+1 switches then you know it works for any number switches.

First, take the base case. Does a single X/straight switch control the lamp so that flipping it changes the lamp's state? Clearly, yes, this is a simple case.

Now suppose that there are n switches joined together and that flipping any switch will change the state of the lamp. If we add a switch to the end of the switches wiring it as in the examples above is it still true that any switch will flip the lamp from one state to the other? It is.

To see that consider the two terminals at the end of the row of n switches. One has power coming out of it, the other does not. Flipping the new switch just swaps where the power is coming from and thus lights or extinguishes the lamp.

Amusingly, my doctoral thesis on computer security uses a light controlled by three switches to illustrate the security properties of a system:

Turns out that the things that you learn as a child affect the rest of your life. The big lesson I learnt is that many things of apparent complexity are built from repeated simple building blocks. And also that you can find an opportunity to apply mathematics everywhere, even in your household lighting.

PS If you need a bit more beautiful simplicity go and read about NAND logic and realize that they are all you're ever going to need.

After much experimentation I unscrewed the switch downstairs and looked at the wiring. I was surprised to discover three wires (and three upstairs as well) and finally figured out that the switches were wired as follows with two switches in blue that can flip between two poles. Flipping either switch changes the state of the lamp from on to off, or off to on.

Later I visited a friend's house and discovered that they had three switches controlling a single lamp. That requires a more complex switch that can flip between two states connecting either the two wires straight through or in an X pattern like this:

You might like to stop here and look at those two diagrams and convince yourself that flipping any switch can turn the lamp on or off. Once you've done that notice that there aren't really two different sorts of switch at all, you could do this with three switches that flip between the straight through and X positions (just with some wires left unconnected).

Once you make that step, it doesn't take a lot of imagination to realize that this scheme will work for any number of switches. You can connect an arbitrary number of switches together in this fashion to control a single lamp. Here are four such switches connected together. You might like to pause again and convince yourself that this would work:

Now you can use a mathematical technique to prove that this will work for any number of switches. The technique is induction. The idea is that if you can prove something true for some base case (that this works with one switch), and you can prove that if it works for n switches it'll work for n+1 switches then you know it works for any number switches.

First, take the base case. Does a single X/straight switch control the lamp so that flipping it changes the lamp's state? Clearly, yes, this is a simple case.

Now suppose that there are n switches joined together and that flipping any switch will change the state of the lamp. If we add a switch to the end of the switches wiring it as in the examples above is it still true that any switch will flip the lamp from one state to the other? It is.

To see that consider the two terminals at the end of the row of n switches. One has power coming out of it, the other does not. Flipping the new switch just swaps where the power is coming from and thus lights or extinguishes the lamp.

Amusingly, my doctoral thesis on computer security uses a light controlled by three switches to illustrate the security properties of a system:

Turns out that the things that you learn as a child affect the rest of your life. The big lesson I learnt is that many things of apparent complexity are built from repeated simple building blocks. And also that you can find an opportunity to apply mathematics everywhere, even in your household lighting.

PS If you need a bit more beautiful simplicity go and read about NAND logic and realize that they are all you're ever going to need.

Labels: pseudo-randomness

*If you enjoyed this blog post, you might enjoy my travel book for people interested in science and technology: The Geek Atlas. Signed copies of The Geek Atlas are available.*

<$BlogCommentBody$>

Create a Link

<< Home