# 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:

Assignment:

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:

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.

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:

Which can be described with matrices like this:

Or:

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