There is a special suite of rooms designed with light switches in an odd way. Our goal is to turn off all of the the lights.
There are 25 rooms in the suite arranged in a square of five by five rooms:
1 2 3 4 5 6 7 8 9 10 21 22 13 14 15 16 17 18 19 20 21 22 23 24 25
If you switch the light switch in any room, it toggles the lights in the adjacent room. For example,
-assuming all of the lights are on and you switch the switch in room 1, the lights in room 2 and 6 are turned off and there is no other change in the status of the lights.
-or assuming all of the light are on and you switch the switch in room 18, the lights in room 13, 17, 19, 23 are all turned off and there is no other change in the status of the lights.
-
Assuming all of the lights are on, please advise on how to turn off all of the lights. You can use a web app for row reduction.
-
Assuming all of the lights in even number rooms are on, please advise on how to turn off all of the lights.
After row reduction, we get a free column where,
$$x_4 = t$$
$$x_1 = -2 + t$$
$$x_2 = 2 – t$$
$$x_3 = 1 – t$$
Can anyone help out with the rest?
Best Answer
Here, all work will be done in $\Bbb F_2$, that is, nothing but zeroes and ones.
Construct a $25\times 25$ matrix $A$ such that $A_{i,j} = \begin{cases}1&\text{if button}~j~\text{toggles light}~i\\ 0&\text{otherwise}\end{cases}$
Let $x$ be a $25\times 1$ matrix corresponding to what our button selections were.
Then given an initial configuration of lights, $v$, one has $v+Ax$ is the resulting configuration.
If we have a desired final configuration, $r$, then we wish to solve the matrix equation $v+Ax=r$ for the vector $x$. If it so happens that $A$ is invertible, then this will simply be $x=A^{-1}(r-v)$
Instead of going through the effort of explicitly writing out the $25\times 25$ matrix (it is incredibly tedious), I will show with an example how it works for the $9\times 9$ case corresponding to a $3\times 3$ grid of rooms with lightswitches.
$A=\begin{bmatrix}1&1&0&1&0&0&0&0&0\\ 1&1&1&0&1&0&0&0&0\\ 0&1&1&0&0&1&0&0&0\\ 1&0&0&1&1&0&1&0&0\\ 0&1&0&1&1&1&0&1&0\\ 0&0&1&0&1&1&0&0&1\\ 0&0&0&1&0&0&1&1&0\\ 0&0&0&0&1&0&1&1&1\\ 0&0&0&0&0&1&0&1&1\end{bmatrix}$
As it so happens, is in fact invertible over $\Bbb F_2$ in this case, but that is not always the case. Here we have $A^{-1}=\left[\begin{smallmatrix}1&0&1&0&0&1&1&1&0\\0&0&0&0&1&0&1&1&1\\1&0&1&1&0&0&0&1&1\\0&0&1&0&1&1&0&0&1\\0&1&0&1&1&1&0&1&0\\1&0&0&1&1&0&1&0&0\\1&1&0&0&0&1&1&0&1\\1&1&1&0&1&0&0&0&0\\0&1&1&1&0&0&1&0&1\end{smallmatrix}\right]$
Using this matrix, a starting configuration (say, all lights on) and a desired final configuration (say, all lights off), we can compute $A^{-1}(r-v) = x$ which in this case would be $\left[\begin{smallmatrix}1\\0\\1\\0\\0\\1\\0\\1\\0\\1\end{smallmatrix}\right]$, telling us that to switch the lights from all on to all off in the $3\times 3$ grid, we can flip the switches in rooms $1,3,5,7,9$.
In the case of the $5\times 5$ grid, requiring a $25\times 25$ matrix, we approach similarly.
Our matrix is:
1100010000000000000000000 1110001000000000000000000 0111000100000000000000000 0011100010000000000000000 0001100001000000000000000 1000011000100000000000000 0100011100010000000000000 0010001110001000000000000 0001000111000100000000000 0000100011000010000000000 0000010000110001000000000 0000001000111000100000000 0000000100011100010000000 0000000010001110001000000 0000000001000110000100000 0000000000100001100010000 0000000000010001110001000 0000000000001000111000100 0000000000000100011100010 0000000000000010001100001 0000000000000001000011000 0000000000000000100011100 0000000000000000010001110 0000000000000000001000111 0000000000000000000100011Unfortunately, as alluded to earlier, this matrix happens to not be invertible. That is to say, given a starting position, there are some ending positions which are impossible to reach. There are also multiple ways to reach the same ending position given a starting position if possible to reach in the first place. Regardless, that is not to say that the desired start and end that we are looking for are impossible. We find that the matrix above happens to be of rank $23$.
Trying to solve the matrix equation then, $Ax=r-v$, we can try to row reduce the augmented matrix $[A~|~(r-v)]$. If the system is inconsistent, then no solution exists. If it is consistent, then you should be able to interpret the results of the reduced form in such a way to get one of the possible vectors $x$ which gets you the desired outcome.
Note: this method can be generalized for similar related problems given arbitrarily shaped grids and lightswitches which may operate differently than those given in the above problem. Say for example where flipping a light in a room in the top row will toggle the lights in all adjacent rooms and itself, flipping a light in the second row will toggle all diagonal rooms and itself, flipping the light in room 20 toggles itself and room 1, etc...