Authors: Grigory Solomatov and Mark Meleka
Date: January 2021
[Reading time: 15-20 minutes]
This web page was auto-generated by Google Docs. Sorry for the poor UX! It will be updated later.
This is an in-depth explainer article on how to solve the “game of lights”.
Here is a sneak peak at some of our favourite patterns:
We pretentiously (and narcissistically) name these patterns Solomatov-Meleka Matrices to justify the dozens of human and computer hours we put into this project.
---
[Return to Table of Contents]
[Reading time: 2 minutes]
You are given a grid of lights starting in an “off” state and we want to turn them all “on”.
When you “toggle the switch” for a light, all of the adjacent lights switch their state: beside, above, and below, but not diagonal. For example, turning on the middle light and then turning it off again creates:
Here’s an example where we toggle the switch for the top left light, top middle, and top right lights, one after the other.
The goal is to go from a grid of all “off” lights to a grid of all “on” lights.
Here is a solution for the 2x2 grid:
Can you find the solution for a 3x3 grid? Take a few minutes and try it on your own. You can try virtually with this link: https://markmeleka.com/lights/game
Here’s the solution:
Now that you’ve tried the 3x3 grid, consider trying the 4x4 grid, the 10x10 grid, 15x15 grid, and so on... The virtual game, linked here, makes it easy to try many grid sizes.
Do you notice any patterns?
Brainteaser: Can you find a reliable method to convert any size grid from all “off” to all “on”?
Many real-life problems can be modelled as math problems. Real-life problems can be hairy and complicated. If we can simplify the problem by adding assumptions it becomes much easier to find an analog in math with known solutions. Believe it or not, as our problem is currently stated, it already has an analog in math!
[Return to Table of Contents]
[Reading time: 2 minutes]
We’re going to model our problem as a square of 0s and 1s. Then we’ll use fancy addition and multiplication to solve our lightbulb problem!
If you already know what this means, feel free to skip ahead!
First, we’re going to create a new set of numbers. We will have 0 representing when the lightbulb is “off” and 1 representing when the lightbulb is “on”. No other numbers exist in our set, just 0 and 1.
In fancy math notation we might write: S = {0, 1}
In our set of numbers we’ll have fancy addition and multiplication. We can call these binary operators. It works the same as what you’re used to, but this time 1 + 1 = 0. We want this because when you toggle the switch for a lightbulb that’s already on, it turns off again.
For completeness, here are the addition and multiplication tables.
+ | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 0 |
x | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
This can be known as the:
Fields have some useful properties you’ve seen in grade school like:
You can read more about binary fields on it’s Wikipedia page: https://en.wikipedia.org/wiki/GF(2).
[Return to Table of Contents]
[Reading time: 2 minutes]
We’ll introduce linear systems of equations (or simply “linear systems”) by example.
You might remember the following kind of math problem from high school:
Problem: Two apples and three bananas cost 19 schmeckles in total, while three apples and five bananas cost 30 schmeckles in total. How many schmeckles does one apple cost and how many schmeckles does one banana cost?
Solution: Let “a” be the price of an apple and let “b” be the price of a banana. We can set up the following “inhomogeneous linear system of equations”:
E1 : 2a + 3b = 19
E2 : 3a + 5b = 30
If you need a reminder of how to solve these check out the Khan Academy lessons on systems of equations: https://www.khanacademy.org/math/algebra/x2f8bb11595b61c86:systems-of-equations.
You could also just use a system of equation solver: https://www.wolframalpha.com/calculators/system-equation-calculator.
The solution in this case is a=5 and b=3.
To be more pretentious we can put our original equations in matrix form:
Since *any* variable name would work we can shorten it to the following “augmented matrix”:
We can now find the solutions with a fancy technique called Gaussian elimination. It works basically the same as what you learned in high school, but augmented matrices make it easier to read, input into a computer, and compute many operations efficiently, especially for very large matrices. All you need to know for now is that we can make these matrices and a computer can solve them for us.
If you want to satisfy your curiosity on Gaussian elimination, check out:
What’s really cool is that instead of using “normal” numbers (i.e. the “integers”) we can use the “binary field” that we made before! In fact, Gaussian elimination works with any field.
[Return to Table of Contents]
[Reading time: 2 minutes]
Let’s apply what we’ve learned to our lightbulb problem.
Remember our 2x2 grid of lightbulbs?
We have 4 lightbulbs and we want to know which of the 4 to turn on so that the whole grid is turned on.
Let’s turn this into a linear system.
First, let’s number them to make them easier to reference.
We’ll call them lightbulb-1, lightbulb-2, and so on. To make it easier, we’ll call them l1,l2,l3, and l4. We’ll use the letter “i” to refer to any lightbulb, as in “li”.
We’ll say that li can take on a value of 1 if it gets toggled and 0 if the lightbulb does not get toggled. In fancy notation:
Each lightbulb will have its own equation that describes all of the lightbulbs that turn on when this lightbulb is turned on. For example, turning on l1 results in l1,l2, and l3 being turned on.
Let’s call this set N1 and say N1 = {1, 2, 3}.
Our first equation will be called E1 and E1 will be: l1 + l2+ l3 = 1. Again, this is because when l1 is toggled on it has a value of 1 and this means that l1,l2, and l3 are turned on.
In fancy math notation:
For completeness, the sets Ni are:
N1 = {1, 2, 3}
N2 = {1, 2, 4}
N3 = {1, 3, 4}
N4 = {2, 3, 4}
And the equations Ei are:
In matrix form (writing out the coefficients of the variables):
And as an augmented matrix (shortened version of matrix form):
Again, the augmented matrix is our preferred form because it minimizes redundant information and is fastest to type into a computer.
Try it on your own for the 3x3 grid. The solution is below and more detail is in Appendix A.
[Return to Table of Contents]
[Reading time: 1 minute]
This matrix is the adjacency matrix of our grid: it is possible to reconstruct our grid just by looking at the matrix. For example: since the entry in row 1 and column 3 is 1, we know that 1 and 3 are connected. Similarly, we can see that lightbulbs 2 and 3 are not connected since the entry at row 2 and column 3 is 0.
Notice that our matrix is “symmetric”: the value at row i, column j is the same as row j, column i.
[Return to Table of Contents]
[Reading time: 1 minute]
Our process is not limited to square grids! We could have used any graph with nodes and edges and modelled it as an adjacency matrix using the same steps described earlier.
Consider, for example, this graph:
With adjacency matrix:
Again, we can reconstruct our graph just by looking at this matrix. For example: since row 1, column 4 has a 1, we know there is an edge between lightbulb 1 and 4. Similarly, lightbulbs 3 and 4 are not connected since the entry at row 3, column 4 is 0.
[Return to Table of Contents]
[Reading time: 1 minute]
[Return to Table of Contents]
[Reading time: 2 minutes]
We can use a computer program to solve our linear system of equations.
The steps for our computer program are as follows:
This will give us the solution in a format where we can easily see which lightbulbs to toggle, and how many times to toggle them, to turn all the lightbulbs on.
We’ve provided you a basic implementation for the binary field in a popular programming language, Python, so that you can play with it yourself! Check it out, here: Google Colab link.
There’s a much more efficient implementation for solving systems of equations over finite fields in the computer algebra system named SageMath. Using that implementation you can solve much larger grids much faster. We provide you an implementation in SageMath here: CoCalc link.
We’d love your input and feedback- feel free to submit a pull request to our Github repo!
<TODO: clean up repo and make accessible>
---
[Return to Table of Contents]
[Reading time: 3 minutes]
We choose the simple-to-program case where our game starts with a square grid of size n x n.
The solution matrix is therefore an n x n matrix of numbers ranging from 0 to p, where “p” is 2 for the “simple” version of the game, and “p” is a prime number greater than 2 for the “hard” version of the game.
We map the numbers to colours and plot the result. The maximum number of colors possible is smaller than the grid-length, “n”, and our modulo, “p”. The larger the grid size and modulo, the greater the dimension of the resulting pattern (and also the longer it takes to compute a solution!).
We find one solution, where it exists, for every square grid up to size 70x70 and for every prime modulo up to 69. We apply 75 different color maps to every one of those solutions to find the coolest patterns. This represents about 100,000 combinations (75 colour maps * 70 grids * 19 prime numbers)! This took a few days of continuous computation using several cloud CPUs.
Most solutions we found are symmetrical along the horizontal center line, the vertical center line, a diagonal center line, or all of the above. Most of the solutions exhibit interesting patterns but the ones we particularly enjoyed were the anthropomorphic ones (some semblance of eyes and a mouth) and the ones with a high color contrast that emphasized a shape in the center.
Here are some neat patterns, in descending order by grid size and modulo:
Symmetric:
Crosses:
Cool:
Mod=5; Grid-length=5
Mod=5; Grid-length=15
Mod=29; Grid-length=57
Diagonal symmetry:
Anthropomorphic:
Unsymmetric:
We pretentiously (and narcissistically) name these patterns Solomatov-Meleka Matrices to justify the dozens of human and computer hours we put into this project.
You can find more patterns here.
Conjecture: There are infinitely many Solomatov-Meleka Matrices. This follows from the fact that there are infinitely many integers to use as our grid length, n, and the fact that there are infinitely many primes, p, to use as modulos. We have no reason to believe that solutions stop existing at a large enough grid size or modulo but have not tried to prove it yet.
---
[Return to Table of Contents]
Remember our 3x3 grid of lightbulbs?
We have 9 lightbulbs and we want to know which of the 9 to turn on so that the whole grid is turned on.
Let’s turn this into a linear system.
First, let’s number them to make them easier to reference.
We’ll call them lightbulb-1, lightbulb-2, and so on. To make it easier, we’ll call them l1,l2,...,l9. We’ll use the letter “i” to refer to any lightbulb, as in “li”.
We’ll say that li can take on a value of 1 if it gets toggled and 0 if the lightbulb does not get toggled. In fancy notation:
Each lightbulb will have its own equation that describes which lightbulbs turn on when this lightbulb is turned on. For example, turning on l1 results in l1,l2 and l4 being turned on.
Let’s call this set N1 and say N1 = {1, 2, 4}.
Our first equation will be called E1 and E1 will be: 1 = l1 + l2+ l4. Again, this is because when l1 is toggled on it has a value of 1 and this means that l1,l2 and l4 are turned on.
In fancy math notation:
For completeness, the sets Ni are:
N1 = {1, 2, 4}
N2 = {1, 2, 3, 5}
N3 = {2, 3, 6}
N4 = {1, 4, 5, 7}
N5 = {2, 4, 5, 6, 7}
N6 = {3, 5, 6, 9}
N7 = {4, 7, 8}
N8 = {5, 7, 8, 9}
N9 = {6, 8, 9}
And the equations Ei are:
In matrix form:
And as an augmented matrix:
/ 24
