This project is about a game that consists of a \( 5 \times 5 \) grid of buttons. Buttons are considered adjacent if they are directly touching vertically or horizontally (not diagonally). In the game, all buttons can be in one of two states. The light behind it is either on or off. Pressing any button changes the state of that button and all adjacent buttons. (e.g. If you push button 8 for instance then buttons \( 3,7,8,9 \), and 13 would change their states.) The goal of the game is to turn off all of the lights on the game board. The goal of this project is to use linear algebra and matrix theory to analyze the game and find solutions to various starting conditions. A picture of the game with buttons labeled can be found below. The student should do at least the following analysis of the game: Note: If you are having difficulty answering these questions for the full \( 5 \times 5 \) game, do the mathematical thing and try out smaller versions of it (e.g. \( 2 \times 2 \) or \( 3 \times 3 \) ) to gain insight. a. Create an adjacency matrix, \( M \), for the \( 5 \times 5 \) game. This is a matrix consisting of Os and 1 s which encodes whether two buttons are adjacent to each other. The \( m_{i j} \) entry should be a 1 if and only if the \( i^{\text {th }} \) and \( j^{\text {th }} \) buttons are adjacent. For example, \( m_{12}=1 \) but \( m_{17}=0 \) since 1 and 2 are adjacent buttons, but 1 and 7 are not. (Note: Since in the game a button changes its own state when pressed, a button is considered adjacent to itself.) b. If \( \overrightarrow{x_{i}} \) is the initial state vector, what would it look like for the initial state of all the lights being on? (This should be a column vector. Use 0 for off and 1 for on.) c. If \( \overrightarrow{x_{f}} \) is the final state vector, what would it look like at the end of the game? d. Does it matter in what order the buttons are pushed? Why?
e. A push vector can be created, where 0 represents a button which is not pushed
and 1 a button which is pushed. Create a push vector where buttons 1,8 , and 25
are pushed and all others are not.
f. With M as the adjacency matrix and vec(p) as a push vector, what does M vec(p)
represent in context? If you have trouble with this simply try several push vectors
and compare them to the vector found when multiplying by the adjacency matrix.
It can help to map them out on the game grid so you can see them in context
instead of just as a column vector.
g. Calculate M vec(p) using the vector vec(p) from part d . Is this push vector a solution to the
5xx5 game which starts with all lights on? How do you know?
h. The goal is to find a push vector that does solve a given initial state vector. Do
you think the game has a solution when it is started with all light on? If so, what is
it and how did you find it? Is there only one? (Hint: Since this is a linear algebra
course, try making a system of equations to solve involving the various vectors
and the adjacency matrix you have developed.)
i
