Thomas has a row of lamps, of odd length. Each lamp has two possible states: on or off. Next to each lamp, there is a switch. If a lamp is on, then pressing the switch next to it will change the state of the two neighbours of the lamp (only one if the lamp is at one of the ends of the row), but the lamp itself will remain on. The switches next to lamps that are off do nothing. At the start, only one lamp was on. At what positions in the row could this lamp have been, given that Thomas managed to turn all lamps on?
The source of this riddle can be found here
This problem can obviously be solved with an invariant. But strangely enough, finding this invariant by trial and error is harder than it seems. And even if you find it, this solution does not give you inside into how the problem works and how you could solve similar problems, so while they work, they are less than helpful.
For example, for the above riddle, I could state:
If we define
and
replace each on-lamp with A, and each off-lamp with B, and multiply all matrixes, the end result forms an invariant, and as AnBAm=B is only valid if m=n, the lamp has to be in the centre.
This solution works but is not helpful.
So instead of trying to find a solution, we will describe a semi-structural way to find a solution.
Structural solution.
First, we notice that switches work differently when they are on the first or last lamp. This can be fixed by adding virtual lamps at the start and end of the line. These lamps have a state but not a switch.
We work with a system that is discrete, local, one-dimensional and finite, so it might be a good idea to replace each lamp with a group element, and then multiply the group elements in order.
Let us use the following notation for this group:
a: lamp turned off
x: lamp turned on
Then our invariant has to satisfy the following equations:
Note that every group satisfying this will be invariant, but not every group will be useful. For example, if we take the group
and define a=1 and x=1, our invariant will be the total number of lamps.
Although, even as "the number of lamps in our final state has to be the same as our initial state" is obvious, the fact that a statement we know is true follows from our math, is a good check to verify if are statements are correct.
The difficult part here is finding a group that is simple enough to actually work with it, but complex enough so it still contains the information we need. This might cause some trial and error, and is very case dependent. Luckily, for this riddle, we can make the statement that we are interested in the position of our lamps, so elements of our group that are central, so that can be moved freely without changing the invariant, are useless. Therefore it might be useful to consider a centerless group.
In addition, we will assume that are group is generated by a and x, there is no reason to complicate our group with other generators.
So first, we notice that x^2 commutes with both x (by definition) and a, (given). Therefore,
Using this, we can see that:
Now we know that is group contains 2 elements that do not commute and square to the unit element. This means our group is the infinite dihedral group. But if you don’t know the group names from the top of your head, you can just go to Wikipedia: Symmetry groups and pick the one that has the correct properties.
To be fully rigorous, we have to check that x and b=ax do generate the group, but as a=bx, this is trivially true.
Given this group, The initial state can be represented as anxam and the final state as x. Putting both statements to be equal gives us am-n=1 which can only be true if m-n=0. Therefore the final state can only be reached if the centre lamp was on.
If you want to be fancier, you can prove that every state matching the invariant (and the invariant of the number of lamps) can be actually reached, but that is outside of the scope of this blogpost.