The solution to the lights game
Consider the following
game:
The game is a grid of
5 by 5 buttons that can light up. Pressing a button will toggle its light
(on/off or off/on), but it will also toggle the lights of the (4, 3, or 2)
adjacent buttons around. Each problem presents you with a certain pattern of
lit buttons and to solve the puzzle you have to turn all the lights out (which
is not easy because if you're not careful you will turn more lights on than
off). This is the primary goal; the secondary goal is to accomplish this with
as few moves (pressing a button is one move) as possible.
The solution presented
here uses the algebraic notion of "fields". A field is a set with two operations, addition and multiplication
that satisfies the following axioms:
1. Closure under addition.
2. Closure under multiplication.
3. Associative Law of Addition.
4. Associative Law of Multiplication.
5.
Distributive Law.
6. Existence of 0.
7. Existence of 1.
8. Existence of additive inverses (negatives).
9. Existence of multiplicative inverses
(reciprocals), except for 0.
10. Commutative Law
of Addition.
11. Commutative Law
of Multiplication.
Examples of fields are
Q (rational numbers), R (real numbers), C (complex numbers), and Z/pZ
(integers modulo a prime p).
In particular, Z/2Z (denoted usually by Z_{2}) is a field consisting of
only two elements 0 and 1. The addition and multiplication on Z_{2} will be explained later.
One can talk about a vector space over a field k. One example of such a
space is k^{n} where n is a positive integer.
Let us return to our
game now. Carsten Haese gives the solution presented below.
The goal here is to
find a universal solution to this puzzle, i.e. to find a general algorithm that
will tell you which buttons you have to press given a certain initial pattern.
The central questions concerning this universal solution are
a) Is there a solution
for any initial pattern? If yes, why? If not, describe the set of initial
patterns that have a solution.
b) Assuming a solution
exists for a given initial pattern, how can this solution be derived from the
pattern?
This approach to the
puzzle is to find an equation that describes how pressing the buttons will
affect the lights. First, I need to represent the lights numerically. One
obvious representation that incidentally will also prove to be algebraically
very useful is to represent an unlit button with 0 and a lit button with 1. I
enumerate the 25 buttons/lights from left to right, top to bottom and thus each
pattern of lights is represented by a
25-tuple of 0’s and
1’s, i.e. by an element of the set
_{}.
To represent the way
in which pressing a button affects the pattern of lights, I define an addition
operator on the set
_{}
by
_{}
This describes
accurately the switching mechanism when one summand represents the state of a
light and the other summand represents whether or not that light is switched.
(Not switching an unlit button results in an unlit button, as well as switching
a lit button; not switching a lit button results in a lit button, as well as
switching an unlit button.) By componentwise application, the addition on Z_{2} yields an addition on Z_{2}^{25} in a natural
way.
Of course, to take
advantage of this addition in Z_{2}^{25}
I will want to represent the effect of pressing a button as an element of Z_{2}^{25 }. I do this
the obvious way. Each button has its own pattern of which lights it will switch
and which lights it will leave. By writing 0 for leaving the button unchanged
and 1 for switching, each of the buttons (or rather the "button
action", i.e. the effect of pressing that button) is described by an
element in Z_{2}^{25}.
Let a_{i} in Z_{2}^{25} (i=1,..,25) be the button action that is
caused by pressing the i-th button.
For example,
a_{2} =
(1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
a_{19} =
(0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,1,0).
I can now start the
first attempt at writing down an equation that will solve a lights out puzzle.
Let y in Z_{2}^{25}
be the initial light pattern of the puzzle. Now I might play around with the
buttons, for example by pressing the 21st button I would transform the light
pattern y into a_{21} + y.
Then I might press the 15th button, resulting in a_{15} + (a_{21 }+ y). And so on. The addition is
associative, so I can spare the parentheses without ambiguity. The goal is to
find a (finite!) sequence (n(1),n(2),...,n(N))
such that
a_{n(N)} + a_{n(N-1)}
+ ... + a_{n(1)} + y = (0,0,...,0).
This approach is
awkward, though. The addition in Z_{2}^{25}
is commutative, so without loss of generality the sequence n(1)...n(N) can be chosen to be non-decreasing. Furthermore, since a_{i}
+ a_{i} = 0 for all i=1,..,25 (in fact, v + v = 0 for
all v in Z_{2}^{25}
), the sequence can even be chosen to be strictly increasing since no button
action needs to be performed more than once. Evidently this means that N≤25.
To achieve an elegant form of the equation with exactly 25 summands, I define a
multiplication operator on Z_{2}^{
}that will allow me to skip those button actions that are not needed
in the solution sequence. I define 0*0 := 0*1 := 1*0 := 0 and 1*1 := 1. It is
known that (Z_{2}, + ,*) is a
field, and with the natural multiplication s*(v_{1},..,v_{25})
:= (s*v_{1},..,s*v_{25}), (Z_{2}^{25},+,*)
is a vector space over the field Z_{2}.
Now, the above
equation can be equivalently rewritten as
x_{1}*a_{1} + ... + x_{25}*a_{25
}+ y = (0,0,...,0)
with some x=(x_{1},...,x_{25})
in Z_{2}^{25}. By
adding y to both sides of this equation I get
x_{1}*a_{1} + ... + x_{25}*a_{25} = y.
Now I want to write the left hand side as a
matrix product. I should mention at this point that all vectors are supposed to
be columns, even if I write them as rows for convenience.
If I let M be
the matrix whose i-th row is a_{i}_{ } (transposed), my equation becomes
Mx = y.
It is easy to verify that
M is the block matrix
_{}
with
_{},
I is the identity matrix 5x5 and 0 is the zero
matrix 5x5.
Now I have completed
the task of finding an equation that describes the solution of a lights out
puzzle. A sequence of button actions that is described by x=(x_{1},...,x_{25})
in Z_{2}^{25} will
make the light pattern y in Z_{2}^{25}
vanish if and only if Mx = y. This is a linear equation in a vector
space, so even though the equation does not deal with real numbers, I can apply
standard solving methods.
The above questions
can now be answered by studying the properties of M.
I have written a small
computer program that simultaneously solves the 25 equations
Mx = b_{i}
(where { b_{i}
| i=1,...,25} is the Cartesian basis of Z_{2}^{25}) using Gauss elimination. If you want to
solve the equation by hand, feel free to do so)
I won't flood this
paper with the result matrix, even though the following main results can't
really be verified without it.
The main results are:
* dim range M =
23, dim ker M = 2.
Therefore there are puzzles that can't be
solved. Those that can be solved have 4 different solutions because (x_{24},
x_{25}) can be chosen arbitrarily from Z_{2}^{2}
* Examining the last
two lines in the final matrix yields a criterion for the existence of a
solution. With the vectors
k_{1}=(1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,1),
k_{2}=(1,1,0,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,1,0,1,1).
The criterion can be written as 0 =
<y, k_{1}> = <y, k_{2}>, where < . , .
> denotes the canonical scalar product in Z_{2}^{25}. It turns out that {k_{1}, k_{2}}
is a basis of ker M, which is not really surprising because the
solvability of Mx=y is equivalent to y being in range M
which (since M is symmetric) is equivalent to y being orthogonal
to ker M.
* A general solving
algorithm (i.e. a formula that expresses x in terms of y) can also be found
easily by evaluating the result matrix. Such an algorithm would only be
suitable for a computer, though. If you are interested in a solution that a
human can easily perform, I suggest the following exercises:
1) Show that for any initial pattern there
is a sequence of moves that reduces the pattern to the first line.
2) Assuming solvability, show that there are
7 nontrivial patterns that have lights only in the first line.
3) Derive the solutions of these seven
patterns from the final matrix.
4) Memorize them and impress your friends.
This approach never yields a minimal
solution because you will most likely press buttons twice, but it is a solution
nevertheless.