Lights Out is an electronic board game. (Click here to play.) The standard version consists of a \(5\times 5\) array of lights, some of which are on and the rest are off at the beginning of the game.
When a square is pressed, the light on that square as well as the lights on the squares that are immediately above, immediately below, immediately to the left, and immediately to the right will be toggled (that is, on becomes off and off becomes on). For example, starting with the following configuration,
pressing the middle square will give the following:
And then pressing the top-right square will give the following:
The goal of the game is to turn off all the lights.
We are going to analyze this game mathematically. Before we do that, we make a couple of observations.
The first is that pressing a square an even number of times has no effect on the configuration of lights.
The second is that the order in which the squares are pressed does not matter.
As a result, to describe a solution to the game, all we need is a set of squares that need to be pressed. In the following, pressing each of the squares with a green border once will turn off all the lights.
We can model the configuration of lights as a matrix of 0's and 1's. For example, the configuration
can be represented by the \(5 \times 5\) matrix \(\begin{bmatrix} 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 0 \end{bmatrix}\).
The action of pressing a square can also be represented by a 0-1 matrix where 0 represents a square that is not affected and 1 represents one that is. For example, pressing the middle square and pressing the top right square are represented by \(\begin{bmatrix} 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}\) and \(\begin{bmatrix} 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}\) respectively.
Now, to obtain the result after pressing the middle and top right squares, we simply compute the sum \[\begin{bmatrix} 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}.\]
The way we add matrices is to add component-wise. Hence, the result is \(\begin{bmatrix} 1 & 0 & 0 & 2 & 2\\ 0 & 0 & 2 & 0 & 2\\ 0 & 2 & 2 & 1 & 0\\ 0 & 0 & 2 & 1 & 1\\ 1 & 0 & 1 & 1 & 0 \end{bmatrix}.\) But we are looking for a 0-1 matrix. Yet this matrix has 2's in them!
What we need is in fact a different rule for addition here. Namely, we need \(1+1\) to equal 0, not 2. Why? Because toggling a square that is on turns it off. So using this rule, the actual result is \(\begin{bmatrix} 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 1 & 0 \end{bmatrix}\).
Even though a \(5\times 5\) matrix corresponds nicely to the board,
as we will see later, it is more convenient to use tuples instead. A tuple is
simply a column of numbers. To represent a \(5 \times 5\) board, we will
need a 25-tuple, a tuple with 25 entries.
We illustrate the idea on a \(3\times 3\) board. The configuration
is represented by the 9-tuple
\(\begin{bmatrix}
1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1\\
\end{bmatrix}\).
The first three entries of the tuple correspond to the squares in
the first row (read from left to right),
the next three entries of the tuple correspond to the squares in
the second row,
and the last three entres of the tuple correspond to the squares in
the last row.
Pressing the middle square is represented by \(\begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0\\ \end{bmatrix}\). Adding this to the tuple representing the light configuration (again using the rule \(1+1=0\)), we get \(\begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1\\ \end{bmatrix}\).
As a result, we can now play Lights Out simply by adding 0-1 tuples!
Quick quiz
Give the matrix and tuple representations of
.
Compute the following sum using the rule \(1+1=0\): \[\begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \end{bmatrix}+ \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \end{bmatrix}+ \begin{bmatrix} 1 \\ 0 \\ 1 \\ 1 \end{bmatrix}.\]
To play the game using only tuples, one must first form the tuple
representing the configuration as well as the tuples that
represent the pressing of each of the squares.
Consider the configuration:
Find a subset of these tuples so that when you add them to the tuple representing the configuration, you get the tuple of all 0's, thus finishing the game.