## Lights Out

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.

## Observations

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.

## Matrices versus tuples

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!

## Exercises

1. Give the matrix and tuple representations of .

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

3. 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:

1. List all 9 tuples representing the pressing of each of the 9 squares.

2. 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.