Multiple light switches which control one light and modular arithmetic

The problem I would like to discuss is the following. Most people have seen a room where there are two independent light switches. For instance, in some bedrooms the light can be turned on and off at the entrance door and also at a switch next to the bed. In this case you can turn on the light when you enter the room at night and then later turn off the light when you are already in bed. You can then turn on the light again using the switch at the door. Of course you can also turn on the light again using the switch at the bed. In fact, the light can be turned on and off at any switch in any sequence – i.e. each switch works independently of the state of the other switch.

The question is, how does this work?

To illustrate, let us first draw a diagram of a circuit with one light switch.

Here are two attempts which do not work.

In Attempt 1, the light is turned on only if both Switch 1 and Switch 2 are turned on. So, for instance, if one turns off the light using Switch 1, then one cannot turn on the light using Switch 2.

In Attempt 2, the light is only turned off if both Switch 1 and Switch 2 are turned off. So, for instance, if one turns on the light using Switch 2, then one cannot turn off the light using Switch 1.

So the question then is, what does one have to do to have 2 switches where the light can be turned on and off at each switch, regardless of the state of the other switch? Can you find a solution? (A solution can be found here.)

If you have found a solution with two switches, can you design a circuit with n =3, 4, \ldots switches?

Modular arithmetic

Let {}S denote a switch and assume that it can have two possible states, namely {}0 and {}1 as shown in the following picture.

Then let us write, if S=0 the light is turned on and if S=1 the light is turned off.

Now assume we have two switches S_1 and S_2, each of which can take on the values {}0 or {}1. Then we want to construct a circuit such that if S_1=S_2, then, say, the light is turned on (the overall state {}S is {}0) and if S_1\neq S_2 the light is turned off (the overall state {}S is {}1). Mathematically, we can describe this using modular arithmetic by writing

\displaystyle S \equiv S_1+S_2 \pmod{2},

which means that we calculate S_1+S_2-2k, where {}k is chosen such that S_1+S_2-2k\in\{0,1\} (or we can say that S=0 if S_1+S_2 is even and S=1 if S_1+S_2 is odd.)

Notice that attempt 2 above corresponds to the function

\displaystyle S_1 S_2.

Only if S_1=S_2=1 do we get {}1, i.e. only if both S_1 and S_2 are in position {}1 is the light turned off (state {}1). In all other cases the light is turned on (state {}0).

If we have {}n switches, where n\in\mathbb{N}, denoted by S_1,S_2,\ldots, S_n, then we want a circuit which represents the function

\displaystyle S \equiv S_1+S_2+\cdots +S_n \pmod{2},

where again we have S_1+S_2+\cdots+S_n\pmod{2} is {}0 if the sum S_1+S_2+\cdots +S_n is even and {}1 otherwise (notice this is the same as described above for S_1+S_2\pmod{2}).

Notice that the modular arithmetic described above has the following properties:

  • S_1+S_2 \pmod{2} \in \{0,1\}
  • S_1 + S_2 \equiv S_2+S_1 \pmod{2}
  • If S_1=0 and S_2 \in\{0,1\} then S_2 \equiv S_1+S_2\pmod{2}
  • For each state of S_1, there exists a state of S_2 such that 0 \equiv S_1+S_2 \pmod{2}
  • S_1+(S_2+S_3) \equiv (S_1+S_2)+S_3 \pmod{2}

These properties describe an abelian group (see also here).

If you have found a circuit with {}n switches, you can check these properties for the circuit.

Let k=\kappa_0 + \kappa_1 2 and l = \lambda_0 + \lambda_1 2 with \kappa_0,\kappa_1, \lambda_0,\lambda_1 \in \{0,1\}. Can you design circuits which “calculate” k+l and kl?

Advertisements

One response to “Multiple light switches which control one light and modular arithmetic

  1. Also ich muss sagen, ich verstehe hier nur Bahnhof!!!!
    Dette

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s