Though online gaming isn’t usually my thing, my friend Alec has been a World of Warcraft nerd for many years. One day, after spending the night chatting with a fellow guildy, Alec presented me with a lights game puzzle. He writes:

*I was hanging out in World of Warcraft one day, and a guildy was looking for the blue mechanowolf (Friender) pet for his Hunter. He came across the lights puzzle in Gnomeregan which summons Friender for you to tame, and was having trouble solving it. He asked for help in guild chat, and being a lover of puzzles, I decided I wanted to take a look.*

*The puzzle is pretty simple. You have a set of 8 lights, some of which are on, and some of which are off. If you click on a light, it toggles that light and the ones next to it. The object is to get all of the lights to be turned on. For instance, if the lights are currently set up like this:*

*You could click the second light, which would change the puzzle to look like this:*

* *

*Unfortunately we were struggling to solve it. In fact, if you attempt to solve the example I’ve given you, you’ll find it’s impossible. Surprised that I couldn’t solve this when it seemed so simple, I took the puzzle to bed with me on a notebook, using binary representation to write out steps. Using the above example, I would have written 10110000 on my notebook with 01010000 underneath it to indicate the new sequence after clicking the second light. I finally gave up around 3:00 AM, extremely frustrated.*

*The next morning, I went into work and decided I was going to ask my co-worker Jon about this. I was fairly certain that there was no solution to the puzzle, but I wanted to ask him if there was a way to prove mathematically that the starting sequence I was working with (say 10110000) was impossible to manipulate to 11111111 given the rules of the puzzle.*

After thinking about the problem for a while, I found that Alec was indeed correct. In particular, 1/2 of the starting configurations for the lights game have no solution! My reasoning is as follows:

Imagining each light to be independent of any other,

the 8 lights can be in any of 256 configurations, 2^8.

I aim to show that the 8 light operations in the light

game are dependent on one another and therefore not all

256 configurations can be reached from any other.

Further, from any starting configuration, only half of

the configurations, 2^7 = 128, can be reached.

Let us begin by considering the independent case.

Each light can be in any of two states, either on

or off. For modeling purposes let us assign the

number 1 to an on state and 0 to an off state.

Also, let us assign the function `add 1 modulo 2`,

which we will denote (+ 1), to the act of changing a single

light from its current state to its other state. In other

words we are mathematically representing the actions on a

single light as the cyclic group Z/2Z generated by (+ 1).

Effectively this means:

(a) performing (+ 1) an odd number of times affects the same

change on a light as just performing (+ 1) once. Let us denote

any performance like this with an ‘a’ for action. By parallel,

we notice that performing (+ 1) an even number of times effects

no change at all. Let us denote this trivial change by ‘e’.

Performing either ‘a’ or ‘e’ are the only two actions we can

perform on a given light, a(1) = 0 for instance.

(b) Both actions are self inverse and thus performing either

of them an even number of times is a trivial action,

a.a = e or e.e = e. This means that pairs of the same action

can be `cancelled` from a performance, ie.

(a.e.a.a.e.e.e.a)

(a.e.e.e.e.a)

(a.e.e.a)

(a.a)

(e)

(c) Possibly most crucially, performing the same actions in one

order versus another makes no difference to the outcome, ie.

(a.e.a.a.e.e.e.a) = (a.a.a.a.e.e.e.e). This last property of the

group is called the Abelian property.

Now for a leap of abstraction. While any one light can be

represented by one of our cyclic groups Z/2Z, we can also

consider pairs of Z/2Zs to represent pairs of lights (or more

generally n copies of Z/2Z can represent n many lights).

Now where elements of Z/2Z are either 1 or 0, elements of

pairs of Z/2Z can be written (0, 0), (0, 1), (1, 0), or (1, 1),

corresponding to the 4 configurations the pair of lights can

be found. Similarly, actions on these states can be written

(e, e), (e, a), (a, e), or (a, a). The act of performing paired

operations like (e, a) on paired states like (1, 1) can be

defined pairwise giving (e, a) (1, 1) = (e(1), a(1)) = (1, 0).

Notice how the nice properties (a)…(c) above extend in a rather

nice way.

(a’) Performing either (e, e), (e, a), (a, e), or (a, a) are the

only actions we can perform on a given pair of lights. Further,

(e, a) and (a, e) are generators in that combinations of these two

can be used to get to any other possible state.

(b’) Each action is self inverse.

(c’) This newly formed group of pairs has the Abelian property.

This suggests more generally that for n lights we can construct

an n-fold Abelian group whose elements (a1 … an) designate

any of 2^n possible light configurations and whose actions

(f1 … fn) designate any of 2^n possible ways to effect n lights.

Notice, that this model preserves the independence of any given

light. In other words, the only way to change the light in the jth

place in the a list, (a1…aj…an) is by having fj be an ‘a’.

pictorially,

This fact has far-reaching consequences for us. If we are to write

out each of the n generators for the n-fold Abelian group,

f1 = (a e e … e)

f2 = (e a e … e)

f3 = (e e a … e)

…

fn = (e e e … a)

Not one of them can be expressed as the combination of any of

the others. Changing the jth and kth light has no effect on the mth.

These n independent actions form what is called a basis for our group.

That no action can be written as the sum of any others also means

that from any configuration on n lights we can get to any of 2^n

light configurations by applying combinations of the n actions.

With 8 lights, for instance, we can get to any of 2^8 = 256

configurations via combinations of the 8 basis actions.

If, on the other hand, the actions were dependent so that some

action, fj, could be performed as the combination of any of the

others, fj = f1.f3.f2 say, so would any performance involving fj

be dependent on a combination of f1.f3.f2. This means that we

could only reach 2^(n-1) possible configurations, 2^7 = 128 in

our example.

Now for the punchline (no longer the independent case but rather

the actual case). The light game has 8 possible actions. Each action

effects a small handful of lights. Changing the leftmost light, for

example, also effects its next closest neighbor to the right.

Generally, changing any light also effects that lights nearest adjacent

lights. If these actions were independent, they could be used to

reach any of 256 configurations for any starting configuration.

If instead we can perform any action as the combination of any others,

we can then only reach 128 configurations, ie half of the possible

configurations.

Notice, that performing (f1.f5.f4.f2.f7) as above, is the same as

performing f8. This means that f8 is dependent on f1, f5, f4, f2,

and f7. Via the reasoning above, this means that f8 does not contribute

uniquely to arriving at any configurations we otherwise could get to using

the other actions and therefore the total number of configurations

we can arrive at with f1 through f7 is 128, ie. less than 256.

Of course we could have instead thought of the 8 operations as being a basis for a vector space and considered them as the rows of a matrix. Then by computing Gaussian elimination we would see that only 7 of these vectors form a basis, ie. one of the rows would be zero. Further, the 7 vectors form a basis for a space with 128 elements. This means that for any given initial configuration, only 1/2 of the total configurations can be reached, as is intended to be shown.

Lastly, this particular puzzle reappears in a different form later on in the game. There it appears as the Shaman’s Totem puzzle. Though the game pictorially has been extended to a 2-dimensional playing field, the mathematics works out the same. Here instead of 8 lights there are 25 lights. Encoding these as binary vectors and computing Gaussian elimination gives the basis for the space of accessible light configurations, which btw IS fully accessible for any starting configuration 😉

- Conjecture: Light games with n lights where n is congruent to 0 or 1 modulo 3 are completely solvable.