Return to Revisions

I'll use wrong/correct instead of off/on because I know I'll get it wrong otherwise. So we have an infinite grid with finitely many wrong lights, and can only switch lights with an even number of its 4 neighbours wrong.

Firstly, if any of the wrong lights can be switched, do so. This means all remaining wrong lights are odd (have an odd number of wrong neighbours).

Now look at a wrong light that is the furthest to the top-left of the grid. So the situation looks like this:

.....?
....??
...x??
..????
.?????

where x is the wrong light under consideration, dots are correct lights, and ? marks lights of unknown status. We can assume that the light to the top-right of x is correct (if not, you move along that diagonal to the last wrong light).

.....?
.....?
...x??
..????
.?????

We know the wrong light must have an odd number of wrong neighbours, so it must have exactly one of them. So we have one of the following:

.....?    .....?
.....?    .....?
...xy?    ...x.?
..?.??    ..?y??
.?????    .?????

where y is a wrong neighbour.

Do the moves 1 to 4 indicated here:

.....?    .....?
..12.?    ..12.?
...34?    ...3.?
..?.??    ..?4??
.?????    .?????

This shifts the two wrong lights from x and y to form a domino at the locations 1 and 2.

In this way you can separate off a domino. With similar moves you can move that domino further out to the top left, out of the way. By repeating this process you can split up any large clusters into dominos. You may find that you leave behind a shape with some even wrong lights, which you can switch before splitting off the next domino.

So any starting position of wrong lights can be transformed into a position consisting only of widely separated dominos. You can easily move these dominoes around, and by bringing two dominoes close to each other you can pairwise annihilate them:

.......
.xx.xx.
.......

.......
.xxxxx.
.......

.......
.x.x.x.
.......

.......
.......
.......

They don't need to be in line like that - they can be in any orientation as long as they are next to each other with one space between them.

The procedure I described can switch on all the lights, as long as you produce an even number of dominos. The parity argument that Gareth McCaughan gave can predict which starting positions produce an odd number of dominos. Count the number of adjacent pairs of wrong lights. Every move changes this by an even amount, so this number remains even or odd throughout. If it is odd, then the position is unsolvable because the fully solved grid is even. If you use the solving procedure, it must then produce an odd number of dominoes, and in that case we can only reduce it to exactly one remaining domino but no further. If this number of adjacent pairs of wrong lights is even, then we must get an even number of dominoes, and therefore be able to solve it.