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}$

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?$