Light Puzzle

This puzzle is taken from a lab assignment given to UCSD undergraduates in their linear algebra course. (It can be found here.)

In a kingdom far, far away, the King decided that the time had come to find a husband for his princess daughter. The King wanted to find a worthy lad for his princess, so he promised to give his daughter away to the first young (or old) man who would solve the puzzle that had stumped the best of his court mathematicians for years. The puzzle was very simple: in a palace, there are 25 rooms arranged in a square---5 rows of rooms with 5 rooms in each row. In every room there is a light switch which not only switches on/off the light in that room, but also switches the lights in the adjacent rooms---the room to the right, to the left, the room above, and the room below. Initially, all of the lights are turned off. The goal is to turn the lights on in every room of the palace.

You can try out the puzzle below. The "Clear" button will allow you to clear all the lights and start over.

Encode each switch as a vector of zeros and ones. A one in the $i$th position indicates that the switch will toggle the light in the $i$th room. For example, Switch 1 toggles the lights in Rooms 1, 2, and 6; therefore, the switch in Room 1 can be encoded as the following vector: $$v_{1} = \left[ 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\right]^{T}.$$

The switch in Room 2 is $$v_{2} = \left[ 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\right]^{T}.$$

What happens if we flip both switches in Room 1 and Room 2? This is accomplished by adding $v_{1}$ and $v_{2}$. The trick, though, is to do all calculations mod 2. To see why this makes sense, consider Room 1: the vector $v_{1}$ has a one in the first slot, so when we flip the switch in Room 1, the light in Room 1 turns on. Now we flip the switch in Room 2. The vector $v_{2}$ also has a one in the first slot, so if we add $v_{1} + v_{2}$, we get a two in the first slot. But the actual effect of the latter switch is to turn the light in Room 1 off again. So this two should be a zero.

Let's try this in Sage.

Check that the above answer makes sense by going to the game board above and verifying that flipping the switches in Room 1 and Room 2 will result in having the lights on in Rooms 3, 6, and 7.

To solve the problem, we need to turn on a set of switches. Note that the order in which we flip the switches is irrelevant and we never need to flip any switch more than once. In other words, each switch will either be flipped or not.

Let $v_{init}$ be the initial state of the lights. (This is just the zero vector in our scenario.)

Now let $c_{i} = 0$ if we leave the switch in Room $i$ alone and $c_{i} = 1$ if we flip the switch in Room $i$. Then the final state of the lights will be $$v_{init} + c_{1}v_{1} + c_{2} v_{2} + \dots + c_{25} v_{25}.$$

Let $v_{final}$ be the final state we want to achieve. (If the goal is to turn on all the lights, then $v_{final}$ will be a vector of all ones.)

Therefore, solving our puzzle is equivalent to solving the equation $$v_{init} + c_{1}v_{1} + c_{2} v_{2} + \dots + c_{25} v_{25} = v_{final}$$ for the coefficients $c_{i}$. Or put another way, if we let $v = v_{final} - v_{init}$, then we need to solve $$c_{1}v_{1} + c_{2} v_{2} + \dots + c_{25} v_{25} = v.$$

Recall that the above expression of a linear combination of vectors is equivalent to a system of linear equations, encoded in a matrix-vector equation as $$Vc = v$$ where $V$ is the matrix with columns $v_{i}$, and $c$ is the vector of coefficients $c_{i}$.

Let's set up the augmented matrix for this system. If you write out the 25 x 25 matrix $V$, you'll see that it takes the block form $$\begin{bmatrix} A & I & O & O & O \\ I & A & I & O & O \\ O & I & A & I & O \\ O & O & I & A & I \\ O & O & O & I & A \end{bmatrix}$$ where $A$ is the 5x5 block $$\begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix},$$ $I$ is the 5x5 identity matrix, and $O$ is the 5x5 zero matrix.

Let's define $V$ in Sage.

Now we can form the augmented matrix with $v = v_{final} - v_{init}$ as the last column. Remember that $v_{final}$ is a vector of all ones (all the lights need to be turned on) and $v_{init}$ is the zero vector (all the lights are off at the beginning).

Now we simply row reduce. The row reduction will automatically be done mod 2 because all the objects that form $V_{aug}$ were defined over the integers mod 2.