Puzzle group of $4times 4$ “flip” game
$begingroup$
I have been goofing around with the game "flip," which can be played at the following link. The puzzle consists of an $ntimes n$ grid of squares that are either black or white, and when one clicks on one of the squares, its color and the colors of each of its four neighbors are toggled.
It is easy to show that any board configuration is solvable for the $2times 2$ and $3times 3$ versions of the puzzle. Thus, since game moves commute, the groups corresponding to these puzzles are $mathbb Z_2^4$ and $mathbb Z_2^9$ respectively.
However, I have discovered that the $4times 4$ game is not so simple; there exist some board configurations that are not solvable. This can be demonstrated as follows.
Suppose we color the board like this:
One may easily verify that any move toggles an even number of the red-colored squares; thus, in any solvable puzzles, the number of black squares in the red region is even. This narrows down the group of solvable puzzles to $mathbb Z_2^{15}$; however, since reflections/rotations of this coloring produce further restrictions, the group must be even smaller than this. In fact, using this strategy, I have narrowed it down to a subgroup of $mathbb Z_2^{14}$, and I suspect it can be narrowed down even further to $mathbb Z_2^{13}$.
My question is: what is the puzzle group of the $4times 4$ puzzle? I know this problem can be reduced to finding the rank of a $16times 16$ matrix, but... surely there's a better way.
linear-algebra group-theory logic abelian-groups puzzle
asked Dec 26 '18 at 23:53
FrpzzdFrpzzd
23k841109
$endgroup$
add a comment |
$begingroup$
I have been goofing around with the game "flip," which can be played at the following link. The puzzle consists of an $ntimes n$ grid of squares that are either black or white, and when one clicks on one of the squares, its color and the colors of each of its four neighbors are toggled.
It is easy to show that any board configuration is solvable for the $2times 2$ and $3times 3$ versions of the puzzle. Thus, since game moves commute, the groups corresponding to these puzzles are $mathbb Z_2^4$ and $mathbb Z_2^9$ respectively.
However, I have discovered that the $4times 4$ game is not so simple; there exist some board configurations that are not solvable. This can be demonstrated as follows.
Suppose we color the board like this:
One may easily verify that any move toggles an even number of the red-colored squares; thus, in any solvable puzzles, the number of black squares in the red region is even. This narrows down the group of solvable puzzles to $mathbb Z_2^{15}$; however, since reflections/rotations of this coloring produce further restrictions, the group must be even smaller than this. In fact, using this strategy, I have narrowed it down to a subgroup of $mathbb Z_2^{14}$, and I suspect it can be narrowed down even further to $mathbb Z_2^{13}$.
My question is: what is the puzzle group of the $4times 4$ puzzle? I know this problem can be reduced to finding the rank of a $16times 16$ matrix, but... surely there's a better way.
linear-algebra group-theory logic abelian-groups puzzle
asked Dec 26 '18 at 23:53
FrpzzdFrpzzd
23k841109
$endgroup$
$begingroup$
Perhaps a definition of "puzzle group" is in order, if we are to justify an answer here. It seems connected with the possible "states" of a game of size $ntimes n$. You may be thinking that the "moves" form a group that acts on the states. It is then of interest to determine any "unsolvable" states by working out the orbits of the states under the group action.
$endgroup$
– hardmath
Dec 27 '18 at 0:08
$begingroup$
This game is called "Lights out". I will write a program to find out the groups of $ntimes m$ lightsout for some values for you, give me a minute.
$endgroup$
– SmileyCraft
Dec 27 '18 at 0:46
add a comment |
$begingroup$
I have been goofing around with the game "flip," which can be played at the following link. The puzzle consists of an $ntimes n$ grid of squares that are either black or white, and when one clicks on one of the squares, its color and the colors of each of its four neighbors are toggled.
It is easy to show that any board configuration is solvable for the $2times 2$ and $3times 3$ versions of the puzzle. Thus, since game moves commute, the groups corresponding to these puzzles are $mathbb Z_2^4$ and $mathbb Z_2^9$ respectively.
However, I have discovered that the $4times 4$ game is not so simple; there exist some board configurations that are not solvable. This can be demonstrated as follows.
Suppose we color the board like this:
One may easily verify that any move toggles an even number of the red-colored squares; thus, in any solvable puzzles, the number of black squares in the red region is even. This narrows down the group of solvable puzzles to $mathbb Z_2^{15}$; however, since reflections/rotations of this coloring produce further restrictions, the group must be even smaller than this. In fact, using this strategy, I have narrowed it down to a subgroup of $mathbb Z_2^{14}$, and I suspect it can be narrowed down even further to $mathbb Z_2^{13}$.
My question is: what is the puzzle group of the $4times 4$ puzzle? I know this problem can be reduced to finding the rank of a $16times 16$ matrix, but... surely there's a better way.
linear-algebra group-theory logic abelian-groups puzzle
asked Dec 26 '18 at 23:53
FrpzzdFrpzzd
23k841109
$endgroup$
I have been goofing around with the game "flip," which can be played at the following link. The puzzle consists of an $ntimes n$ grid of squares that are either black or white, and when one clicks on one of the squares, its color and the colors of each of its four neighbors are toggled.
It is easy to show that any board configuration is solvable for the $2times 2$ and $3times 3$ versions of the puzzle. Thus, since game moves commute, the groups corresponding to these puzzles are $mathbb Z_2^4$ and $mathbb Z_2^9$ respectively.
However, I have discovered that the $4times 4$ game is not so simple; there exist some board configurations that are not solvable. This can be demonstrated as follows.
Suppose we color the board like this:
One may easily verify that any move toggles an even number of the red-colored squares; thus, in any solvable puzzles, the number of black squares in the red region is even. This narrows down the group of solvable puzzles to $mathbb Z_2^{15}$; however, since reflections/rotations of this coloring produce further restrictions, the group must be even smaller than this. In fact, using this strategy, I have narrowed it down to a subgroup of $mathbb Z_2^{14}$, and I suspect it can be narrowed down even further to $mathbb Z_2^{13}$.
My question is: what is the puzzle group of the $4times 4$ puzzle? I know this problem can be reduced to finding the rank of a $16times 16$ matrix, but... surely there's a better way.
linear-algebra group-theory logic abelian-groups puzzle
linear-algebra group-theory logic abelian-groups puzzle
asked Dec 26 '18 at 23:53
FrpzzdFrpzzd
23k841109
asked Dec 26 '18 at 23:53
FrpzzdFrpzzd
23k841109
asked Dec 26 '18 at 23:53
FrpzzdFrpzzd
23k841109
asked Dec 26 '18 at 23:53
FrpzzdFrpzzd
23k841109
asked Dec 26 '18 at 23:53
FrpzzdFrpzzd
23k841109
23k841109
$begingroup$
Perhaps a definition of "puzzle group" is in order, if we are to justify an answer here. It seems connected with the possible "states" of a game of size $ntimes n$. You may be thinking that the "moves" form a group that acts on the states. It is then of interest to determine any "unsolvable" states by working out the orbits of the states under the group action.
$endgroup$
– hardmath
Dec 27 '18 at 0:08
$begingroup$
This game is called "Lights out". I will write a program to find out the groups of $ntimes m$ lightsout for some values for you, give me a minute.
$endgroup$
– SmileyCraft
Dec 27 '18 at 0:46
add a comment |
$begingroup$
Perhaps a definition of "puzzle group" is in order, if we are to justify an answer here. It seems connected with the possible "states" of a game of size $ntimes n$. You may be thinking that the "moves" form a group that acts on the states. It is then of interest to determine any "unsolvable" states by working out the orbits of the states under the group action.
$endgroup$
– hardmath
Dec 27 '18 at 0:08
$begingroup$
This game is called "Lights out". I will write a program to find out the groups of $ntimes m$ lightsout for some values for you, give me a minute.
$endgroup$
– SmileyCraft
Dec 27 '18 at 0:46
$begingroup$
Perhaps a definition of "puzzle group" is in order, if we are to justify an answer here. It seems connected with the possible "states" of a game of size $ntimes n$. You may be thinking that the "moves" form a group that acts on the states. It is then of interest to determine any "unsolvable" states by working out the orbits of the states under the group action.
$endgroup$
– hardmath
Dec 27 '18 at 0:08
$begingroup$
Perhaps a definition of "puzzle group" is in order, if we are to justify an answer here. It seems connected with the possible "states" of a game of size $ntimes n$. You may be thinking that the "moves" form a group that acts on the states. It is then of interest to determine any "unsolvable" states by working out the orbits of the states under the group action.
$endgroup$
– hardmath
Dec 27 '18 at 0:08
$begingroup$
This game is called "Lights out". I will write a program to find out the groups of $ntimes m$ lightsout for some values for you, give me a minute.
$endgroup$
– SmileyCraft
Dec 27 '18 at 0:46
$begingroup$
This game is called "Lights out". I will write a program to find out the groups of $ntimes m$ lightsout for some values for you, give me a minute.
$endgroup$
– SmileyCraft
Dec 27 '18 at 0:46
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
As I mentioned in the comment, this game is called Lights Out. The moves form a finite abelian boolean group ($g^2=0$ for all $g$), which means it will always be isomorphic to $mathbb{Z}_2^k$ for some $k$. Also notice that any solution can be encoded as a set of cells that you have to click.
Without ever clicking the top row, you can always click the squares until only the bottom row has lit up squares. Simply go from top to bottom and keep clicking below lit up squares. It is also easy to see that there is a unique way to achieve this. Let us call this "fixing the board".
To speedrun this game, as I used to do some times, fixing the board was step one. For step two, you must memorize for every cell in the top row which cells in the bottom row will flip when you click the top cell and then fix the board. Let us call these the bottom vectors. You should then quickly recognize what linear combination of bottom vectors equals the current bottom row. Then click all corresponding cells in the top row and once again fix the board.
Notice that, in $1times1$, $2times2$ and $3times3$ Lights Out, the bottom vectors are linearly independent. This exactly means that every possible board can be solved. The $4times4$ Lights Out is also quite special, since every bottom vector is all $0$. This means that for every solvable Lights Out, there are $2^4$ ways of solving it. This is because we can click any cells in the top row and then fix the board. Hence $4times4$ Lights Out is isomorphic to $mathbb{Z}_2^{12}$.
In general, for $ntimes m$ Lights Out ($n$ wide $m$ high), we can consider the span of all bottom vectors (these are of length $n$). Let $c$ denote the codimension of this span inside $mathbb{Z}_2^n$. Then $ntimes m$ Lights Out is isomorphic to $mathbb{Z}_2^{ntimes m-c}$. Also, any solvable Lights Out board has $2^c$ solutions.
Here is a table of some codimensions:
begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
hline
times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\hline
1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0\hline
3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\hline
4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0\hline
5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1\hline
6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0\hline
7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2\hline
8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6\hline
9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1\hline
10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\hline
11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2\hline
12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0\hline
13&&&&&&&&&&&&&0&1&0&0&13&0&0&1\hline
14&&&&&&&&&&&&&&4&2&8&1&0&6&0\hline
15&&&&&&&&&&&&&&&0&0&4&0&0&2\hline
16&&&&&&&&&&&&&&&&8&0&0&0&0\hline
17&&&&&&&&&&&&&&&&&2&0&3&7\hline
18&&&&&&&&&&&&&&&&&&0&0&0\hline
19&&&&&&&&&&&&&&&&&&&16&2\hline
20&&&&&&&&&&&&&&&&&&&&0\hline
end{array}
Here is a much bigger table, which you will have to compile yourself, since it does not fit on the page:
begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
hline
times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32&33&34&35&36&37&38&39&40&41&42&43&44&45&46&47&48&49&50&51&52&53&54&55&56&57&58&59&60&61&62\hline
1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0\hline
3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\hline
4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\hline
5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1\hline
6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\hline
7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2\hline
8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\hline
9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1&0&4&1&0&0&1&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1\hline
10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0\hline
11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2&1&0&10&0&1&2&3&0&4&0&8&2&1&0&6&0&1&2&7&0&4&0&3&2&1&0&11&0&1&2&3&0&4&0&7&2&1&0&6&0&1&2\hline
12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&12\hline
13&&&&&&&&&&&&&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7\hline
14&&&&&&&&&&&&&&4&2&8&1&0&6&0&1&0&2&4&1&0&2&0&5&0&2&0&9&4&2&0&1&0&6&0&1&0&2&4&1&0&2&0&5&8&2&0&1&4&2&0&1&0&6&0&1&0\hline
15&&&&&&&&&&&&&&&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\hline
16&&&&&&&&&&&&&&&&8&0&0&0&0&0&0&0&0&0&0&0&0&8&0&0&0&8&0&0&0&0&0&0&0&0&0&0&8&0&0&0&0&0&8&0&0&0&0&0&0&0&0&8&0&0&0\hline
17&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&15&0&2&0&4&1&1&6&4&0&1&1&4&0&14&0&3&1&1&0&5&6&1&1&3&0&2&0&16&1&1&0&4&0&1&7\hline
18&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
19&&&&&&&&&&&&&&&&&&&16&2&0&0&3&4&0&2&0&0&11&0&0&2&0&4&3&0&0&2&16&0&3&0&0&6&0&0&3&0&8&2&0&0&3&4&0&2&0&0&19&0&0&2\hline
20&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&6&2&0&1&0&2&0&1&0&8&0&1&0&2&0&1&0&2&6&1&0&2&0&1&0&2&0&7&0&2&0&1&0&2&0&1&6\hline
21&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&10&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&20&1\hline
22&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
23&&&&&&&&&&&&&&&&&&&&&&&14&0&1&2&3&0&5&0&16&2&1&0&10&0&1&2&7&0&5&0&3&2&1&0&22&0&1&2&3&0&5&0&7&2&1&0&10&0&1&2\hline
24&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\hline
25&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&13\hline
26&&&&&&&&&&&&&&&&&&&&&&&&&&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\hline
27&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&27&0&0&2&0&0&3&0&0&8&0&0&3&0&0&2&0&0&15&0&0&2&0&0&3&0&0&8\hline
28&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
29&&&&&&&&&&&&&&&&&&&&&&&&&&&&&10&0&4&1&17&4&4&0&1&1&12&0&2&0&3&5&1&0&5&0&9&9&3&0&2&4&4&1&1&0&12&0&1&1\hline
30&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&20&0\hline
31&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&31&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\hline
32&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&11&0\hline
33&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&16&0&1&0&0&1&0&0&1&0&0&9&0&0&1&0&0&9&0&0&1&0&0&1&0&0&17&0&0&1\hline
34&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&6&0&0&0&4&0&0&0&0&10&0&0&0&0&4&0&0&0&6&4&0&0&0&0&4&0&0&6\hline
35&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&6&0&1&2&7&0&16&0&3&2&1&0&11&6&1&2&3&0&4&0&31&2&1&0&6&0&1&8\hline
36&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
37&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
38&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&12\hline
39&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&32&0&4&0&0&6&0&0&7&0&8&2&0&0&4&4&0&2&0&0&23&0&0&2\hline
40&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
41&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&3&0&14&0&4&1&1&0&4&0&1&7\hline
42&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
43&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&20&2\hline
44&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&1&0&2&6&5&8&2&0&1&4&8&0&1&0&6&0&1&6\hline
45&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
46&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
47&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&30&0&1&2&3&0&5&0&7&2&1&0&11&0&1&2\hline
48&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\hline
49&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&1&0&0&1&4&0&1&0&0&9&0&0&1\hline
50&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&2&0&1&0&2&0&1&0&10&0&1&0\hline
51&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&3&0&0&14\hline
52&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\hline
53&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&16&1&1&0&4&0&1&7\hline
54&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&10&0\hline
55&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&7&0&0&8\hline
56&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&0\hline
57&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1\hline
58&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0\hline
59&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&22&0&1&2\hline
60&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0\hline
61&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&40&1\hline
62&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&24\hline
end{array}
answered Dec 27 '18 at 1:44
SmileyCraftSmileyCraft
3,591517
$endgroup$
$begingroup$
Amazing, thank you so much! I wonder if there are any notable patterns in this table. Most numbers seem to be zero... I wonder if we can find a nice sequence of integers (not necessarily exhaustive) that guarantee the $ntimes n$ game to have deficiency zero. Perhaps this is always true if $n$ is a triangular number?
$endgroup$
– Frpzzd
Dec 27 '18 at 15:00
$begingroup$
One interesting pattern is that every row is repetative. I think you can show that the period of row $n$ is at most $4^{n^2}$. Also interesting is that every column corresponding to a multiple of $6$ (and column $10$ for some reason) appears to be all $0$.
$endgroup$
– SmileyCraft
Dec 27 '18 at 18:33
$begingroup$
Any idea about why this is true for rows that are multiples of $6$? Have you verified this for higher multiples of $6$ like $24,30,36,$ etc, or just the multiples of $6$ in the table?
$endgroup$
– Frpzzd
Dec 27 '18 at 21:49
$begingroup$
I have no idea why this happens, no. In order to verify for higher multiples of $6$, I'll have to get a faster algorithm, the one I currently have is exponential in width. With Gaussian elimination I should be able to make it polynomial, though.
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:05
$begingroup$
Okay the pattern does not even hold up to $24$ :P
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:08
|
show 2 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053448%2fpuzzle-group-of-4-times-4-flip-game%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As I mentioned in the comment, this game is called Lights Out. The moves form a finite abelian boolean group ($g^2=0$ for all $g$), which means it will always be isomorphic to $mathbb{Z}_2^k$ for some $k$. Also notice that any solution can be encoded as a set of cells that you have to click.
Without ever clicking the top row, you can always click the squares until only the bottom row has lit up squares. Simply go from top to bottom and keep clicking below lit up squares. It is also easy to see that there is a unique way to achieve this. Let us call this "fixing the board".
To speedrun this game, as I used to do some times, fixing the board was step one. For step two, you must memorize for every cell in the top row which cells in the bottom row will flip when you click the top cell and then fix the board. Let us call these the bottom vectors. You should then quickly recognize what linear combination of bottom vectors equals the current bottom row. Then click all corresponding cells in the top row and once again fix the board.
Notice that, in $1times1$, $2times2$ and $3times3$ Lights Out, the bottom vectors are linearly independent. This exactly means that every possible board can be solved. The $4times4$ Lights Out is also quite special, since every bottom vector is all $0$. This means that for every solvable Lights Out, there are $2^4$ ways of solving it. This is because we can click any cells in the top row and then fix the board. Hence $4times4$ Lights Out is isomorphic to $mathbb{Z}_2^{12}$.
In general, for $ntimes m$ Lights Out ($n$ wide $m$ high), we can consider the span of all bottom vectors (these are of length $n$). Let $c$ denote the codimension of this span inside $mathbb{Z}_2^n$. Then $ntimes m$ Lights Out is isomorphic to $mathbb{Z}_2^{ntimes m-c}$. Also, any solvable Lights Out board has $2^c$ solutions.
Here is a table of some codimensions:
begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
hline
times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\hline
1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0\hline
3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\hline
4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0\hline
5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1\hline
6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0\hline
7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2\hline
8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6\hline
9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1\hline
10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\hline
11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2\hline
12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0\hline
13&&&&&&&&&&&&&0&1&0&0&13&0&0&1\hline
14&&&&&&&&&&&&&&4&2&8&1&0&6&0\hline
15&&&&&&&&&&&&&&&0&0&4&0&0&2\hline
16&&&&&&&&&&&&&&&&8&0&0&0&0\hline
17&&&&&&&&&&&&&&&&&2&0&3&7\hline
18&&&&&&&&&&&&&&&&&&0&0&0\hline
19&&&&&&&&&&&&&&&&&&&16&2\hline
20&&&&&&&&&&&&&&&&&&&&0\hline
end{array}
Here is a much bigger table, which you will have to compile yourself, since it does not fit on the page:
begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
hline
times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32&33&34&35&36&37&38&39&40&41&42&43&44&45&46&47&48&49&50&51&52&53&54&55&56&57&58&59&60&61&62\hline
1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0\hline
3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\hline
4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\hline
5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1\hline
6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\hline
7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2\hline
8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\hline
9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1&0&4&1&0&0&1&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1\hline
10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0\hline
11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2&1&0&10&0&1&2&3&0&4&0&8&2&1&0&6&0&1&2&7&0&4&0&3&2&1&0&11&0&1&2&3&0&4&0&7&2&1&0&6&0&1&2\hline
12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&12\hline
13&&&&&&&&&&&&&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7\hline
14&&&&&&&&&&&&&&4&2&8&1&0&6&0&1&0&2&4&1&0&2&0&5&0&2&0&9&4&2&0&1&0&6&0&1&0&2&4&1&0&2&0&5&8&2&0&1&4&2&0&1&0&6&0&1&0\hline
15&&&&&&&&&&&&&&&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\hline
16&&&&&&&&&&&&&&&&8&0&0&0&0&0&0&0&0&0&0&0&0&8&0&0&0&8&0&0&0&0&0&0&0&0&0&0&8&0&0&0&0&0&8&0&0&0&0&0&0&0&0&8&0&0&0\hline
17&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&15&0&2&0&4&1&1&6&4&0&1&1&4&0&14&0&3&1&1&0&5&6&1&1&3&0&2&0&16&1&1&0&4&0&1&7\hline
18&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
19&&&&&&&&&&&&&&&&&&&16&2&0&0&3&4&0&2&0&0&11&0&0&2&0&4&3&0&0&2&16&0&3&0&0&6&0&0&3&0&8&2&0&0&3&4&0&2&0&0&19&0&0&2\hline
20&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&6&2&0&1&0&2&0&1&0&8&0&1&0&2&0&1&0&2&6&1&0&2&0&1&0&2&0&7&0&2&0&1&0&2&0&1&6\hline
21&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&10&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&20&1\hline
22&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
23&&&&&&&&&&&&&&&&&&&&&&&14&0&1&2&3&0&5&0&16&2&1&0&10&0&1&2&7&0&5&0&3&2&1&0&22&0&1&2&3&0&5&0&7&2&1&0&10&0&1&2\hline
24&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\hline
25&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&13\hline
26&&&&&&&&&&&&&&&&&&&&&&&&&&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\hline
27&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&27&0&0&2&0&0&3&0&0&8&0&0&3&0&0&2&0&0&15&0&0&2&0&0&3&0&0&8\hline
28&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
29&&&&&&&&&&&&&&&&&&&&&&&&&&&&&10&0&4&1&17&4&4&0&1&1&12&0&2&0&3&5&1&0&5&0&9&9&3&0&2&4&4&1&1&0&12&0&1&1\hline
30&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&20&0\hline
31&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&31&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\hline
32&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&11&0\hline
33&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&16&0&1&0&0&1&0&0&1&0&0&9&0&0&1&0&0&9&0&0&1&0&0&1&0&0&17&0&0&1\hline
34&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&6&0&0&0&4&0&0&0&0&10&0&0&0&0&4&0&0&0&6&4&0&0&0&0&4&0&0&6\hline
35&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&6&0&1&2&7&0&16&0&3&2&1&0&11&6&1&2&3&0&4&0&31&2&1&0&6&0&1&8\hline
36&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
37&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
38&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&12\hline
39&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&32&0&4&0&0&6&0&0&7&0&8&2&0&0&4&4&0&2&0&0&23&0&0&2\hline
40&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
41&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&3&0&14&0&4&1&1&0&4&0&1&7\hline
42&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
43&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&20&2\hline
44&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&1&0&2&6&5&8&2&0&1&4&8&0&1&0&6&0&1&6\hline
45&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
46&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
47&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&30&0&1&2&3&0&5&0&7&2&1&0&11&0&1&2\hline
48&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\hline
49&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&1&0&0&1&4&0&1&0&0&9&0&0&1\hline
50&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&2&0&1&0&2&0&1&0&10&0&1&0\hline
51&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&3&0&0&14\hline
52&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\hline
53&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&16&1&1&0&4&0&1&7\hline
54&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&10&0\hline
55&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&7&0&0&8\hline
56&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&0\hline
57&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1\hline
58&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0\hline
59&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&22&0&1&2\hline
60&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0\hline
61&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&40&1\hline
62&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&24\hline
end{array}
answered Dec 27 '18 at 1:44
SmileyCraftSmileyCraft
3,591517
$endgroup$
$begingroup$
Amazing, thank you so much! I wonder if there are any notable patterns in this table. Most numbers seem to be zero... I wonder if we can find a nice sequence of integers (not necessarily exhaustive) that guarantee the $ntimes n$ game to have deficiency zero. Perhaps this is always true if $n$ is a triangular number?
$endgroup$
– Frpzzd
Dec 27 '18 at 15:00
$begingroup$
One interesting pattern is that every row is repetative. I think you can show that the period of row $n$ is at most $4^{n^2}$. Also interesting is that every column corresponding to a multiple of $6$ (and column $10$ for some reason) appears to be all $0$.
$endgroup$
– SmileyCraft
Dec 27 '18 at 18:33
$begingroup$
Any idea about why this is true for rows that are multiples of $6$? Have you verified this for higher multiples of $6$ like $24,30,36,$ etc, or just the multiples of $6$ in the table?
$endgroup$
– Frpzzd
Dec 27 '18 at 21:49
$begingroup$
I have no idea why this happens, no. In order to verify for higher multiples of $6$, I'll have to get a faster algorithm, the one I currently have is exponential in width. With Gaussian elimination I should be able to make it polynomial, though.
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:05
$begingroup$
Okay the pattern does not even hold up to $24$ :P
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:08
|
show 2 more comments
$begingroup$
As I mentioned in the comment, this game is called Lights Out. The moves form a finite abelian boolean group ($g^2=0$ for all $g$), which means it will always be isomorphic to $mathbb{Z}_2^k$ for some $k$. Also notice that any solution can be encoded as a set of cells that you have to click.
Without ever clicking the top row, you can always click the squares until only the bottom row has lit up squares. Simply go from top to bottom and keep clicking below lit up squares. It is also easy to see that there is a unique way to achieve this. Let us call this "fixing the board".
To speedrun this game, as I used to do some times, fixing the board was step one. For step two, you must memorize for every cell in the top row which cells in the bottom row will flip when you click the top cell and then fix the board. Let us call these the bottom vectors. You should then quickly recognize what linear combination of bottom vectors equals the current bottom row. Then click all corresponding cells in the top row and once again fix the board.
Notice that, in $1times1$, $2times2$ and $3times3$ Lights Out, the bottom vectors are linearly independent. This exactly means that every possible board can be solved. The $4times4$ Lights Out is also quite special, since every bottom vector is all $0$. This means that for every solvable Lights Out, there are $2^4$ ways of solving it. This is because we can click any cells in the top row and then fix the board. Hence $4times4$ Lights Out is isomorphic to $mathbb{Z}_2^{12}$.
In general, for $ntimes m$ Lights Out ($n$ wide $m$ high), we can consider the span of all bottom vectors (these are of length $n$). Let $c$ denote the codimension of this span inside $mathbb{Z}_2^n$. Then $ntimes m$ Lights Out is isomorphic to $mathbb{Z}_2^{ntimes m-c}$. Also, any solvable Lights Out board has $2^c$ solutions.
Here is a table of some codimensions:
begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
hline
times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\hline
1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0\hline
3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\hline
4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0\hline
5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1\hline
6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0\hline
7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2\hline
8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6\hline
9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1\hline
10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\hline
11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2\hline
12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0\hline
13&&&&&&&&&&&&&0&1&0&0&13&0&0&1\hline
14&&&&&&&&&&&&&&4&2&8&1&0&6&0\hline
15&&&&&&&&&&&&&&&0&0&4&0&0&2\hline
16&&&&&&&&&&&&&&&&8&0&0&0&0\hline
17&&&&&&&&&&&&&&&&&2&0&3&7\hline
18&&&&&&&&&&&&&&&&&&0&0&0\hline
19&&&&&&&&&&&&&&&&&&&16&2\hline
20&&&&&&&&&&&&&&&&&&&&0\hline
end{array}
Here is a much bigger table, which you will have to compile yourself, since it does not fit on the page:
begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
hline
times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32&33&34&35&36&37&38&39&40&41&42&43&44&45&46&47&48&49&50&51&52&53&54&55&56&57&58&59&60&61&62\hline
1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0\hline
3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\hline
4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\hline
5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1\hline
6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\hline
7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2\hline
8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\hline
9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1&0&4&1&0&0&1&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1\hline
10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0\hline
11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2&1&0&10&0&1&2&3&0&4&0&8&2&1&0&6&0&1&2&7&0&4&0&3&2&1&0&11&0&1&2&3&0&4&0&7&2&1&0&6&0&1&2\hline
12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&12\hline
13&&&&&&&&&&&&&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7\hline
14&&&&&&&&&&&&&&4&2&8&1&0&6&0&1&0&2&4&1&0&2&0&5&0&2&0&9&4&2&0&1&0&6&0&1&0&2&4&1&0&2&0&5&8&2&0&1&4&2&0&1&0&6&0&1&0\hline
15&&&&&&&&&&&&&&&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\hline
16&&&&&&&&&&&&&&&&8&0&0&0&0&0&0&0&0&0&0&0&0&8&0&0&0&8&0&0&0&0&0&0&0&0&0&0&8&0&0&0&0&0&8&0&0&0&0&0&0&0&0&8&0&0&0\hline
17&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&15&0&2&0&4&1&1&6&4&0&1&1&4&0&14&0&3&1&1&0&5&6&1&1&3&0&2&0&16&1&1&0&4&0&1&7\hline
18&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
19&&&&&&&&&&&&&&&&&&&16&2&0&0&3&4&0&2&0&0&11&0&0&2&0&4&3&0&0&2&16&0&3&0&0&6&0&0&3&0&8&2&0&0&3&4&0&2&0&0&19&0&0&2\hline
20&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&6&2&0&1&0&2&0&1&0&8&0&1&0&2&0&1&0&2&6&1&0&2&0&1&0&2&0&7&0&2&0&1&0&2&0&1&6\hline
21&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&10&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&20&1\hline
22&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
23&&&&&&&&&&&&&&&&&&&&&&&14&0&1&2&3&0&5&0&16&2&1&0&10&0&1&2&7&0&5&0&3&2&1&0&22&0&1&2&3&0&5&0&7&2&1&0&10&0&1&2\hline
24&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\hline
25&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&13\hline
26&&&&&&&&&&&&&&&&&&&&&&&&&&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\hline
27&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&27&0&0&2&0&0&3&0&0&8&0&0&3&0&0&2&0&0&15&0&0&2&0&0&3&0&0&8\hline
28&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
29&&&&&&&&&&&&&&&&&&&&&&&&&&&&&10&0&4&1&17&4&4&0&1&1&12&0&2&0&3&5&1&0&5&0&9&9&3&0&2&4&4&1&1&0&12&0&1&1\hline
30&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&20&0\hline
31&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&31&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\hline
32&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&11&0\hline
33&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&16&0&1&0&0&1&0&0&1&0&0&9&0&0&1&0&0&9&0&0&1&0&0&1&0&0&17&0&0&1\hline
34&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&6&0&0&0&4&0&0&0&0&10&0&0&0&0&4&0&0&0&6&4&0&0&0&0&4&0&0&6\hline
35&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&6&0&1&2&7&0&16&0&3&2&1&0&11&6&1&2&3&0&4&0&31&2&1&0&6&0&1&8\hline
36&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
37&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
38&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&12\hline
39&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&32&0&4&0&0&6&0&0&7&0&8&2&0&0&4&4&0&2&0&0&23&0&0&2\hline
40&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
41&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&3&0&14&0&4&1&1&0&4&0&1&7\hline
42&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
43&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&20&2\hline
44&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&1&0&2&6&5&8&2&0&1&4&8&0&1&0&6&0&1&6\hline
45&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
46&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
47&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&30&0&1&2&3&0&5&0&7&2&1&0&11&0&1&2\hline
48&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\hline
49&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&1&0&0&1&4&0&1&0&0&9&0&0&1\hline
50&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&2&0&1&0&2&0&1&0&10&0&1&0\hline
51&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&3&0&0&14\hline
52&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\hline
53&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&16&1&1&0&4&0&1&7\hline
54&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&10&0\hline
55&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&7&0&0&8\hline
56&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&0\hline
57&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1\hline
58&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0\hline
59&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&22&0&1&2\hline
60&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0\hline
61&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&40&1\hline
62&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&24\hline
end{array}
answered Dec 27 '18 at 1:44
SmileyCraftSmileyCraft
3,591517
$endgroup$
$begingroup$
Amazing, thank you so much! I wonder if there are any notable patterns in this table. Most numbers seem to be zero... I wonder if we can find a nice sequence of integers (not necessarily exhaustive) that guarantee the $ntimes n$ game to have deficiency zero. Perhaps this is always true if $n$ is a triangular number?
$endgroup$
– Frpzzd
Dec 27 '18 at 15:00
$begingroup$
One interesting pattern is that every row is repetative. I think you can show that the period of row $n$ is at most $4^{n^2}$. Also interesting is that every column corresponding to a multiple of $6$ (and column $10$ for some reason) appears to be all $0$.
$endgroup$
– SmileyCraft
Dec 27 '18 at 18:33
$begingroup$
Any idea about why this is true for rows that are multiples of $6$? Have you verified this for higher multiples of $6$ like $24,30,36,$ etc, or just the multiples of $6$ in the table?
$endgroup$
– Frpzzd
Dec 27 '18 at 21:49
$begingroup$
I have no idea why this happens, no. In order to verify for higher multiples of $6$, I'll have to get a faster algorithm, the one I currently have is exponential in width. With Gaussian elimination I should be able to make it polynomial, though.
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:05
$begingroup$
Okay the pattern does not even hold up to $24$ :P
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:08
|
show 2 more comments
$begingroup$
As I mentioned in the comment, this game is called Lights Out. The moves form a finite abelian boolean group ($g^2=0$ for all $g$), which means it will always be isomorphic to $mathbb{Z}_2^k$ for some $k$. Also notice that any solution can be encoded as a set of cells that you have to click.
Without ever clicking the top row, you can always click the squares until only the bottom row has lit up squares. Simply go from top to bottom and keep clicking below lit up squares. It is also easy to see that there is a unique way to achieve this. Let us call this "fixing the board".
To speedrun this game, as I used to do some times, fixing the board was step one. For step two, you must memorize for every cell in the top row which cells in the bottom row will flip when you click the top cell and then fix the board. Let us call these the bottom vectors. You should then quickly recognize what linear combination of bottom vectors equals the current bottom row. Then click all corresponding cells in the top row and once again fix the board.
Notice that, in $1times1$, $2times2$ and $3times3$ Lights Out, the bottom vectors are linearly independent. This exactly means that every possible board can be solved. The $4times4$ Lights Out is also quite special, since every bottom vector is all $0$. This means that for every solvable Lights Out, there are $2^4$ ways of solving it. This is because we can click any cells in the top row and then fix the board. Hence $4times4$ Lights Out is isomorphic to $mathbb{Z}_2^{12}$.
In general, for $ntimes m$ Lights Out ($n$ wide $m$ high), we can consider the span of all bottom vectors (these are of length $n$). Let $c$ denote the codimension of this span inside $mathbb{Z}_2^n$. Then $ntimes m$ Lights Out is isomorphic to $mathbb{Z}_2^{ntimes m-c}$. Also, any solvable Lights Out board has $2^c$ solutions.
Here is a table of some codimensions:
begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
hline
times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\hline
1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0\hline
3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\hline
4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0\hline
5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1\hline
6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0\hline
7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2\hline
8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6\hline
9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1\hline
10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\hline
11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2\hline
12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0\hline
13&&&&&&&&&&&&&0&1&0&0&13&0&0&1\hline
14&&&&&&&&&&&&&&4&2&8&1&0&6&0\hline
15&&&&&&&&&&&&&&&0&0&4&0&0&2\hline
16&&&&&&&&&&&&&&&&8&0&0&0&0\hline
17&&&&&&&&&&&&&&&&&2&0&3&7\hline
18&&&&&&&&&&&&&&&&&&0&0&0\hline
19&&&&&&&&&&&&&&&&&&&16&2\hline
20&&&&&&&&&&&&&&&&&&&&0\hline
end{array}
Here is a much bigger table, which you will have to compile yourself, since it does not fit on the page:
begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
hline
times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32&33&34&35&36&37&38&39&40&41&42&43&44&45&46&47&48&49&50&51&52&53&54&55&56&57&58&59&60&61&62\hline
1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0\hline
3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\hline
4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\hline
5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1\hline
6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\hline
7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2\hline
8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\hline
9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1&0&4&1&0&0&1&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1\hline
10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0\hline
11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2&1&0&10&0&1&2&3&0&4&0&8&2&1&0&6&0&1&2&7&0&4&0&3&2&1&0&11&0&1&2&3&0&4&0&7&2&1&0&6&0&1&2\hline
12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&12\hline
13&&&&&&&&&&&&&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7\hline
14&&&&&&&&&&&&&&4&2&8&1&0&6&0&1&0&2&4&1&0&2&0&5&0&2&0&9&4&2&0&1&0&6&0&1&0&2&4&1&0&2&0&5&8&2&0&1&4&2&0&1&0&6&0&1&0\hline
15&&&&&&&&&&&&&&&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\hline
16&&&&&&&&&&&&&&&&8&0&0&0&0&0&0&0&0&0&0&0&0&8&0&0&0&8&0&0&0&0&0&0&0&0&0&0&8&0&0&0&0&0&8&0&0&0&0&0&0&0&0&8&0&0&0\hline
17&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&15&0&2&0&4&1&1&6&4&0&1&1&4&0&14&0&3&1&1&0&5&6&1&1&3&0&2&0&16&1&1&0&4&0&1&7\hline
18&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
19&&&&&&&&&&&&&&&&&&&16&2&0&0&3&4&0&2&0&0&11&0&0&2&0&4&3&0&0&2&16&0&3&0&0&6&0&0&3&0&8&2&0&0&3&4&0&2&0&0&19&0&0&2\hline
20&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&6&2&0&1&0&2&0&1&0&8&0&1&0&2&0&1&0&2&6&1&0&2&0&1&0&2&0&7&0&2&0&1&0&2&0&1&6\hline
21&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&10&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&20&1\hline
22&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
23&&&&&&&&&&&&&&&&&&&&&&&14&0&1&2&3&0&5&0&16&2&1&0&10&0&1&2&7&0&5&0&3&2&1&0&22&0&1&2&3&0&5&0&7&2&1&0&10&0&1&2\hline
24&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\hline
25&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&13\hline
26&&&&&&&&&&&&&&&&&&&&&&&&&&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\hline
27&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&27&0&0&2&0&0&3&0&0&8&0&0&3&0&0&2&0&0&15&0&0&2&0&0&3&0&0&8\hline
28&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
29&&&&&&&&&&&&&&&&&&&&&&&&&&&&&10&0&4&1&17&4&4&0&1&1&12&0&2&0&3&5&1&0&5&0&9&9&3&0&2&4&4&1&1&0&12&0&1&1\hline
30&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&20&0\hline
31&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&31&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\hline
32&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&11&0\hline
33&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&16&0&1&0&0&1&0&0&1&0&0&9&0&0&1&0&0&9&0&0&1&0&0&1&0&0&17&0&0&1\hline
34&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&6&0&0&0&4&0&0&0&0&10&0&0&0&0&4&0&0&0&6&4&0&0&0&0&4&0&0&6\hline
35&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&6&0&1&2&7&0&16&0&3&2&1&0&11&6&1&2&3&0&4&0&31&2&1&0&6&0&1&8\hline
36&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
37&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
38&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&12\hline
39&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&32&0&4&0&0&6&0&0&7&0&8&2&0&0&4&4&0&2&0&0&23&0&0&2\hline
40&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
41&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&3&0&14&0&4&1&1&0&4&0&1&7\hline
42&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
43&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&20&2\hline
44&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&1&0&2&6&5&8&2&0&1&4&8&0&1&0&6&0&1&6\hline
45&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
46&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
47&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&30&0&1&2&3&0&5&0&7&2&1&0&11&0&1&2\hline
48&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\hline
49&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&1&0&0&1&4&0&1&0&0&9&0&0&1\hline
50&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&2&0&1&0&2&0&1&0&10&0&1&0\hline
51&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&3&0&0&14\hline
52&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\hline
53&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&16&1&1&0&4&0&1&7\hline
54&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&10&0\hline
55&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&7&0&0&8\hline
56&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&0\hline
57&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1\hline
58&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0\hline
59&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&22&0&1&2\hline
60&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0\hline
61&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&40&1\hline
62&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&24\hline
end{array}
answered Dec 27 '18 at 1:44
SmileyCraftSmileyCraft
3,591517
$endgroup$
As I mentioned in the comment, this game is called Lights Out. The moves form a finite abelian boolean group ($g^2=0$ for all $g$), which means it will always be isomorphic to $mathbb{Z}_2^k$ for some $k$. Also notice that any solution can be encoded as a set of cells that you have to click.
Without ever clicking the top row, you can always click the squares until only the bottom row has lit up squares. Simply go from top to bottom and keep clicking below lit up squares. It is also easy to see that there is a unique way to achieve this. Let us call this "fixing the board".
To speedrun this game, as I used to do some times, fixing the board was step one. For step two, you must memorize for every cell in the top row which cells in the bottom row will flip when you click the top cell and then fix the board. Let us call these the bottom vectors. You should then quickly recognize what linear combination of bottom vectors equals the current bottom row. Then click all corresponding cells in the top row and once again fix the board.
Notice that, in $1times1$, $2times2$ and $3times3$ Lights Out, the bottom vectors are linearly independent. This exactly means that every possible board can be solved. The $4times4$ Lights Out is also quite special, since every bottom vector is all $0$. This means that for every solvable Lights Out, there are $2^4$ ways of solving it. This is because we can click any cells in the top row and then fix the board. Hence $4times4$ Lights Out is isomorphic to $mathbb{Z}_2^{12}$.
In general, for $ntimes m$ Lights Out ($n$ wide $m$ high), we can consider the span of all bottom vectors (these are of length $n$). Let $c$ denote the codimension of this span inside $mathbb{Z}_2^n$. Then $ntimes m$ Lights Out is isomorphic to $mathbb{Z}_2^{ntimes m-c}$. Also, any solvable Lights Out board has $2^c$ solutions.
Here is a table of some codimensions:
begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
hline
times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\hline
1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0\hline
3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\hline
4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0\hline
5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1\hline
6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0\hline
7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2\hline
8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6\hline
9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1\hline
10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\hline
11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2\hline
12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0\hline
13&&&&&&&&&&&&&0&1&0&0&13&0&0&1\hline
14&&&&&&&&&&&&&&4&2&8&1&0&6&0\hline
15&&&&&&&&&&&&&&&0&0&4&0&0&2\hline
16&&&&&&&&&&&&&&&&8&0&0&0&0\hline
17&&&&&&&&&&&&&&&&&2&0&3&7\hline
18&&&&&&&&&&&&&&&&&&0&0&0\hline
19&&&&&&&&&&&&&&&&&&&16&2\hline
20&&&&&&&&&&&&&&&&&&&&0\hline
end{array}
Here is a much bigger table, which you will have to compile yourself, since it does not fit on the page:
begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
hline
times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32&33&34&35&36&37&38&39&40&41&42&43&44&45&46&47&48&49&50&51&52&53&54&55&56&57&58&59&60&61&62\hline
1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0\hline
3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\hline
4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\hline
5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1\hline
6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\hline
7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2\hline
8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\hline
9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1&0&4&1&0&0&1&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1\hline
10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0\hline
11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2&1&0&10&0&1&2&3&0&4&0&8&2&1&0&6&0&1&2&7&0&4&0&3&2&1&0&11&0&1&2&3&0&4&0&7&2&1&0&6&0&1&2\hline
12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&12\hline
13&&&&&&&&&&&&&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7\hline
14&&&&&&&&&&&&&&4&2&8&1&0&6&0&1&0&2&4&1&0&2&0&5&0&2&0&9&4&2&0&1&0&6&0&1&0&2&4&1&0&2&0&5&8&2&0&1&4&2&0&1&0&6&0&1&0\hline
15&&&&&&&&&&&&&&&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\hline
16&&&&&&&&&&&&&&&&8&0&0&0&0&0&0&0&0&0&0&0&0&8&0&0&0&8&0&0&0&0&0&0&0&0&0&0&8&0&0&0&0&0&8&0&0&0&0&0&0&0&0&8&0&0&0\hline
17&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&15&0&2&0&4&1&1&6&4&0&1&1&4&0&14&0&3&1&1&0&5&6&1&1&3&0&2&0&16&1&1&0&4&0&1&7\hline
18&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
19&&&&&&&&&&&&&&&&&&&16&2&0&0&3&4&0&2&0&0&11&0&0&2&0&4&3&0&0&2&16&0&3&0&0&6&0&0&3&0&8&2&0&0&3&4&0&2&0&0&19&0&0&2\hline
20&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&6&2&0&1&0&2&0&1&0&8&0&1&0&2&0&1&0&2&6&1&0&2&0&1&0&2&0&7&0&2&0&1&0&2&0&1&6\hline
21&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&10&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&20&1\hline
22&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
23&&&&&&&&&&&&&&&&&&&&&&&14&0&1&2&3&0&5&0&16&2&1&0&10&0&1&2&7&0&5&0&3&2&1&0&22&0&1&2&3&0&5&0&7&2&1&0&10&0&1&2\hline
24&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\hline
25&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&13\hline
26&&&&&&&&&&&&&&&&&&&&&&&&&&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\hline
27&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&27&0&0&2&0&0&3&0&0&8&0&0&3&0&0&2&0&0&15&0&0&2&0&0&3&0&0&8\hline
28&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
29&&&&&&&&&&&&&&&&&&&&&&&&&&&&&10&0&4&1&17&4&4&0&1&1&12&0&2&0&3&5&1&0&5&0&9&9&3&0&2&4&4&1&1&0&12&0&1&1\hline
30&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&20&0\hline
31&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&31&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\hline
32&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&11&0\hline
33&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&16&0&1&0&0&1&0&0&1&0&0&9&0&0&1&0&0&9&0&0&1&0&0&1&0&0&17&0&0&1\hline
34&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&6&0&0&0&4&0&0&0&0&10&0&0&0&0&4&0&0&0&6&4&0&0&0&0&4&0&0&6\hline
35&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&6&0&1&2&7&0&16&0&3&2&1&0&11&6&1&2&3&0&4&0&31&2&1&0&6&0&1&8\hline
36&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
37&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
38&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&12\hline
39&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&32&0&4&0&0&6&0&0&7&0&8&2&0&0&4&4&0&2&0&0&23&0&0&2\hline
40&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
41&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&3&0&14&0&4&1&1&0&4&0&1&7\hline
42&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
43&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&20&2\hline
44&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&1&0&2&6&5&8&2&0&1&4&8&0&1&0&6&0&1&6\hline
45&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\hline
46&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\hline
47&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&30&0&1&2&3&0&5&0&7&2&1&0&11&0&1&2\hline
48&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\hline
49&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&1&0&0&1&4&0&1&0&0&9&0&0&1\hline
50&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&2&0&1&0&2&0&1&0&10&0&1&0\hline
51&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&3&0&0&14\hline
52&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\hline
53&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&16&1&1&0&4&0&1&7\hline
54&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&10&0\hline
55&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&7&0&0&8\hline
56&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&0\hline
57&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1\hline
58&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0\hline
59&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&22&0&1&2\hline
60&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0\hline
61&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&40&1\hline
62&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&24\hline
end{array}
answered Dec 27 '18 at 1:44
SmileyCraftSmileyCraft
3,591517
edited Dec 28 '18 at 17:28
answered Dec 27 '18 at 1:44
SmileyCraftSmileyCraft
3,591517
answered Dec 27 '18 at 1:44
SmileyCraftSmileyCraft
3,591517
answered Dec 27 '18 at 1:44
SmileyCraftSmileyCraft
3,591517
3,591517
$begingroup$
Amazing, thank you so much! I wonder if there are any notable patterns in this table. Most numbers seem to be zero... I wonder if we can find a nice sequence of integers (not necessarily exhaustive) that guarantee the $ntimes n$ game to have deficiency zero. Perhaps this is always true if $n$ is a triangular number?
$endgroup$
– Frpzzd
Dec 27 '18 at 15:00
$begingroup$
One interesting pattern is that every row is repetative. I think you can show that the period of row $n$ is at most $4^{n^2}$. Also interesting is that every column corresponding to a multiple of $6$ (and column $10$ for some reason) appears to be all $0$.
$endgroup$
– SmileyCraft
Dec 27 '18 at 18:33
$begingroup$
Any idea about why this is true for rows that are multiples of $6$? Have you verified this for higher multiples of $6$ like $24,30,36,$ etc, or just the multiples of $6$ in the table?
$endgroup$
– Frpzzd
Dec 27 '18 at 21:49
$begingroup$
I have no idea why this happens, no. In order to verify for higher multiples of $6$, I'll have to get a faster algorithm, the one I currently have is exponential in width. With Gaussian elimination I should be able to make it polynomial, though.
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:05
$begingroup$
Okay the pattern does not even hold up to $24$ :P
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:08
|
show 2 more comments
$begingroup$
Amazing, thank you so much! I wonder if there are any notable patterns in this table. Most numbers seem to be zero... I wonder if we can find a nice sequence of integers (not necessarily exhaustive) that guarantee the $ntimes n$ game to have deficiency zero. Perhaps this is always true if $n$ is a triangular number?
$endgroup$
– Frpzzd
Dec 27 '18 at 15:00
$begingroup$
One interesting pattern is that every row is repetative. I think you can show that the period of row $n$ is at most $4^{n^2}$. Also interesting is that every column corresponding to a multiple of $6$ (and column $10$ for some reason) appears to be all $0$.
$endgroup$
– SmileyCraft
Dec 27 '18 at 18:33
$begingroup$
Any idea about why this is true for rows that are multiples of $6$? Have you verified this for higher multiples of $6$ like $24,30,36,$ etc, or just the multiples of $6$ in the table?
$endgroup$
– Frpzzd
Dec 27 '18 at 21:49
$begingroup$
I have no idea why this happens, no. In order to verify for higher multiples of $6$, I'll have to get a faster algorithm, the one I currently have is exponential in width. With Gaussian elimination I should be able to make it polynomial, though.
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:05
$begingroup$
Okay the pattern does not even hold up to $24$ :P
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:08
$begingroup$
Amazing, thank you so much! I wonder if there are any notable patterns in this table. Most numbers seem to be zero... I wonder if we can find a nice sequence of integers (not necessarily exhaustive) that guarantee the $ntimes n$ game to have deficiency zero. Perhaps this is always true if $n$ is a triangular number?
$endgroup$
– Frpzzd
Dec 27 '18 at 15:00
$begingroup$
Amazing, thank you so much! I wonder if there are any notable patterns in this table. Most numbers seem to be zero... I wonder if we can find a nice sequence of integers (not necessarily exhaustive) that guarantee the $ntimes n$ game to have deficiency zero. Perhaps this is always true if $n$ is a triangular number?
$endgroup$
– Frpzzd
Dec 27 '18 at 15:00
$begingroup$
One interesting pattern is that every row is repetative. I think you can show that the period of row $n$ is at most $4^{n^2}$. Also interesting is that every column corresponding to a multiple of $6$ (and column $10$ for some reason) appears to be all $0$.
$endgroup$
– SmileyCraft
Dec 27 '18 at 18:33
$begingroup$
One interesting pattern is that every row is repetative. I think you can show that the period of row $n$ is at most $4^{n^2}$. Also interesting is that every column corresponding to a multiple of $6$ (and column $10$ for some reason) appears to be all $0$.
$endgroup$
– SmileyCraft
Dec 27 '18 at 18:33
$begingroup$
Any idea about why this is true for rows that are multiples of $6$? Have you verified this for higher multiples of $6$ like $24,30,36,$ etc, or just the multiples of $6$ in the table?
$endgroup$
– Frpzzd
Dec 27 '18 at 21:49
$begingroup$
Any idea about why this is true for rows that are multiples of $6$? Have you verified this for higher multiples of $6$ like $24,30,36,$ etc, or just the multiples of $6$ in the table?
$endgroup$
– Frpzzd
Dec 27 '18 at 21:49
$begingroup$
I have no idea why this happens, no. In order to verify for higher multiples of $6$, I'll have to get a faster algorithm, the one I currently have is exponential in width. With Gaussian elimination I should be able to make it polynomial, though.
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:05
$begingroup$
I have no idea why this happens, no. In order to verify for higher multiples of $6$, I'll have to get a faster algorithm, the one I currently have is exponential in width. With Gaussian elimination I should be able to make it polynomial, though.
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:05
$begingroup$
Okay the pattern does not even hold up to $24$ :P
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:08
$begingroup$
Okay the pattern does not even hold up to $24$ :P
$endgroup$
– SmileyCraft
Dec 28 '18 at 16:08
|
show 2 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053448%2fpuzzle-group-of-4-times-4-flip-game%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Perhaps a definition of "puzzle group" is in order, if we are to justify an answer here. It seems connected with the possible "states" of a game of size $ntimes n$. You may be thinking that the "moves" form a group that acts on the states. It is then of interest to determine any "unsolvable" states by working out the orbits of the states under the group action.
$endgroup$
– hardmath
Dec 27 '18 at 0:08
$begingroup$
This game is called "Lights out". I will write a program to find out the groups of $ntimes m$ lightsout for some values for you, give me a minute.
$endgroup$
– SmileyCraft
Dec 27 '18 at 0:46