# Game Theory

When I created this game, I was generating random configurations of 3 by 3 square with 3 colors. I immediately asked myself "How can I be sure that these initials configurations are solvable ?"

As a former Computer Science student, I tried to describe the game with Mathematical concepts in order to investigate on the question. The more I was digging in, the more questions were coming to my mind. What happen if I change the number of colors ? Is it still solvable if I change the size of the square ? What if I remove certain tiles of the squares ?

This is the result of my investigations, do not hesitate to comment or share if you find mistakes or if you can help me understanding the Game!

## Mathematical Representation

The first thing I did to prove solvability was to write a linear system which was representing the game. I assign a number to each tile of the square. See below an example with 3 by 3 square:

0
1
2
0
1
2
0
1
2

Assignment:

$\begin{matrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9\\ \end{matrix}$

We know that the game must be solve by clicking on specific tiles, let's call $x_{i}$ the number of times we need to click on the tile number $i$. We are then looking to find the vector:

$\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \\ x_{8} \\ x_{9} \\ \end{pmatrix}$

We remark that if we click on the same tile 3 times, then the game goes back to the previous configuration and nothing as changed. This means that all $x_{i}$ are between 0 and 2 included. Clicking 3 times on a tile is the same as not clicking on it.

0
1
2
0
1
2
0
1
2

This is because we have 3 colors, if we had n colors, then we would need to click n times on a tile to go back to the initial configuration.

Assuming we want to turn all tiles in red and starting with the initial configuration above, we have the following linear system:

$\begin{cases} x_1 + x_2 + x_4 + 0 = 0 \\ x_1 + x_2 + x_3 + x_5 + 1 = 0 \\ x_2 + x_3 + x_6 + 2 = 0 \\ x_1 + x_4 + x_5 + x_7 + 0 = 0 \\ x_2 + x_4 + x_5 + x_6 + x_8 + 1 = 0 \\ x_3 + x_5 + x_6 + x_9 + 2 = 0 \\ x_4 + x_7 + x_8 + 0 = 0 \\ x_5 + x_7 + x_8 + x_9 + 1 = 0 \\ x_6 + x_8 + x_9 + 2 = 0 \\ \end{cases}$

Which can be described with matrices like this:

$\begin{pmatrix} 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{pmatrix} \times \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \\ x_{8} \\ x_{9} \\ \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \\ 2 \\ 0 \\ 1 \\ 2 \\ 0 \\ 1 \\ 2 \\ \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix}$

Or:

$AX + B = 0$

From this equation we can say that if the matrix A is inversible in $\mathbb{Z} / 3 \mathbb{Z}$ the all initial configurations B are solvable!

We can use the same process for an arbitrary length of the square and any number of colors $p$. Where $p$ is prime. Because when $p$ is prime, $\mathbb{Z} / p \mathbb{Z}$ is a field.

## Solving

This is part is to be continued, I have created a repository with python code implementing the Gaussian elimination for 3, 5 and 7 colors. You can find it here

Play