Christmas light horror story!

Question

Inspired by stories of strangely behaved Christmas lights here on Puzzling, I feel comfortable now to share my own Christmas light horror story.

It all started when I ordered a grid of star lights on eBay. Advertised as 'inifinitely bright!', I wasn't sure what to expect when I unboxed them. To my surprise, the grid of stars was infinitely large! More to my surprise, a finite number of the stars were OFF.

Obviously, I couldn't deal with such a tacky detail. I tried turning them all on but only some of them would turn on; confused, I read the instructions:

'You may only switch a light on/off if it is adjacent to an EVEN number of lights that are on (including zero).'

What a fuss! I eventually managed to turn the lights all on. However, I then realised I didn't have any place to fit an infinitely large wall of lights, so I put it back into the box and asked for a refund from the eBay seller, who only sent me a fez and the apology 'take this instead, fezzes are cool.'

If there's a silver lining to this, it's that I started to ponder a strange puzzle:

Suppose you had an infinite grid of lights, of which a finite number are off and the rest are on, and you can only toggle a light if it has en even number of orthogonally adjacent ON lights. Can you characterise ALL light patterns that can get completely turned on?

(EXAMPLE: Suppose only 4 lights were off, in the following pattern:

  1  
 2  
34  

You can't toggle lights 2 or 3. But you can turn 1 and 4 on, and then turn 2 and 3 on.
This is an easy example, some patterns of lights will require you to turn other lights OFF before you can make useful progress.)

EDIT: This is something known as a 'combinatorics' problem in Olympiad Mathamatics. Cominatorics problems are notorious for having many 'fake solves', or solutions that seem solid but actually skate over important parts of the question. Both answers so far are definitely on the right track but are unfortunately not complete solutions. It's super easy to make assumptions and statements that don't always hold... be careful!

Answer 1

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.

Answer 2

[I wrote an answer before and it was wrong. The following is right but doesn't yet amount to an actual answer.]

Consider the quantity $Q$ defined to be

the number of adjacent pairs of "wrong" lights. (If the definition of "wrong" isn't obvious, see below.)

When you toggle the state of a light with an even number of neighbours in each state

the parity of $Q$ doesn't change.

(Note: an earlier version of this answer defined $Q$ differently and definitely wrongly.)

I conjecture that

when only finitely many lights are in one state, you can get them all into the other state if and only if $Q$ is even.

(Of course $Q$ is not well defined if there are infinitely many lights in each state, and obviously then you can't hope to get them all the same.)

OK, so let's explore a bit and see where we get. (Warning: half-baked thoughts follow.) First of all, it doesn't matter whether we ask about turning off finitely many lights that are on, or turning on finitely many lights that are off; these are the same problem since "even number of neighbours on" <=> "even number of neighbours off". I'll say that the kind of light we have finitely many of is "wrong" and the other kind is "right".

Now, let's see if we can perhaps always reduce $Q$ (or, maybe, always reduce the number of wrong lights; we'll see which turns out to be easier) provided $Q>1$, and see where that takes us. First of all, if any lights are both wrong and even (i.e., have an even number of wrong neighbours) we can make them right immediately. So if we can't reduce $Q$ then all wrong lights are odd; that is, they have either one or three wrong neighbours.

Now, consider a wrong (and hence odd) light. Walk away from it in two opposite directions until you reach an even light. (You must do eventually, because you will eventually reach a right light surrounded by right lights.) so now you have EOO...OOOE. We can now toggle the even light at one end (EOO...OOEE) and then its predecessor (EOO...OEOE) and then its predecessor (EOO...EEEE) and so on, until the even light at the other end becomes odd and cannot be toggled. At this point we have changed the state of one even light but not the other, and of all odd lights in between. If our initial configuration was unimprovable then at least half of the lights we did this to must have been right. Unfortunately there's no obvious reason why this shouldn't happen.

Consider a wrong light with three wrong neighbours, so we have a configuration like this where a dot indicates a "right" light, an $o$ indicates an odd wrong light, and an $e$ (if there were any) indicates an even wrong light:

$\begin{array}x&o&\\o&o&o\\&.& \end{array}$

If any of these wrong lights has an even neighbour, it's not hard to reduce the number of wrong lights (and also the value of $Q$) by a process that starts with toggling that even neighbour. Therefore, in any configuration we can't improve and that contains a wrong light with three wrong neighbours, all the neighbours of those four (whether wrong or not) are odd.

[Earlier wrong answer follows. Some bits of it will probably be useful in proving or refuting my conjecture.]

The answer is that

any configuration with finitely many "exceptional" lights can have all lights put into the same state.

[EDITED to add: no, it isn't, or at least my reasons for thinking so had an important hole in them. See below.]

Here are the details; those who prefer to remain unspoiled should just not read what follows :-).

First, we can ask about turning on a finite number of "exceptionally" off lights, or turning off a finite number of "exceptionally" on lights; the two situations are equivalent because "even number of neighbours on" <=> "even number of neighbours off". In what follows I'll call the states "right" and "wrong" and assume there are finitely many wrong lights that we want to make right.

Now, we can immediately toggle any isolated wrong lights; that is, any with no wrong neighbours. Unfortunately this doesn't quite mean that we only need to consider connected groups and can do so in isolation, because sometimes we might be able to do better by making lights temporarily wrong, as in the following situation:

$\begin{array} .\square & \square & \square & \square & \square \\ \square & \blacksquare & \blacksquare & \square & \square \\ \square & \square & \square & \blacksquare & \square \\ \square & \square & \square & \blacksquare & \square \\ \square & \square & \square & \square & \square \end{array}$

where we can't fix any of the wrong lights but can add an extra one at top right to "join" the groups, whereupon we can correct each of its neighbours and then clean up the remaining three isolated wrong lights.

I think the answer is going to be that any finite configuration of wrong lights can be righted. Let's see if we can prove it. Given any such configuration, let's begin by just righting any lights we can right immediately. When that's done, any remaining wrong lights are odd (meaning they have an odd number of wrong neighbours). That is, they have either one wrong neighbour or three.

Suppose our configuration contains a wrong light with three wrong neighbours, and (as above) all wrong lights odd. That means the following configuration:

$\begin{array}x&o&\\o&o&o\\&.& \end{array}$

where a dot indicates a definitely-right light, an $o$ indicates a definitely-wrong light with an odd number of wrong neighbours, an $e$ (not seen yet) indicates a definitely-wrong light with an even number of wrong neighbours, and an empty space indicates a light whose state we don't know. Then we can transform it as follows:

[EDITED to add: oops, there is about to be a stupid mistake...]

$\begin{array}x&o&\\o&o&o\\&.& \end{array} \rightarrow \begin{array}x&o&\\o&e&o\\&x& \end{array} \rightarrow \begin{array}x&e&\\e&.&e\\&\bar{x}& \end{array} \rightarrow \begin{array}x&.&\\.&.&.\\&\bar{x}& \end{array}$

[EDITED to add: the stupid mistake is in the first step there, which may not be possible. Until such time as this is fixed, this answer is entirely invalid.]

where $x$ is either $o$ or $e$ but we don't know which, and $\bar{x}$ is the other one. What we've found is that whenever there is a wrong light with three wrong neighbours we can reduce the number of wrong lights by 3. Hence, a not-all-right configuration that can't be reduced (either there is one of these, or all configurations with finitely many wrong lights can be completely righted) must have exactly one wrong neighbour for each wrong light. In other words, it's a collection of adjacent pairs.

OK. Now let's find the "top left" wrong light. By this I mean: find the top row with any wrong lights in, and then take the leftmost light in its row. We have one of these two configurations:

$\begin{array}x.&.&.&.&.&.&.\\.&.&.&.&.&.&.\\.&.&.&.&.&.&.\\.&.&\bullet&\bullet&.&&\\&&.&.&&& \end{array}\quad\quad\quad\quad \begin{array}x.&.&.&.&.&.&.&.\\.&.&.&.&.&.&.&.\\.&.&.&\bullet&.&&&\\&&.&\bullet&.&&&\\&&&.&&&& \end{array}$

which we may transform as follows (I'm combining multiple steps to save space; I hope it's not too hard to figure out the details):

$\begin{array}x.&.&.&.&.&.&.\\.&.&.&.&.&.&.\\.&\bullet&\bullet&.&.&.&.\\.&.&\bullet&\bullet&.&&\\&&.&.&&& \end{array}\quad\quad\quad\quad \begin{array}x.&.&.&.&.&.&.&.\\.&.&\bullet&.&.&.&.&.\\.&.&\bullet&\bullet&.&&&\\&&.&\bullet&.&&&\\&&&.&&&& \end{array}$

then

$\begin{array}x.&.&.&.&.&.&.\\.&.&.&.&.&.&.\\.&\bullet&\bullet&\bullet&.&.&.\\.&.&\bullet&.&.&&\\&&.&.&&& \end{array}\quad\quad\quad\quad \begin{array}x.&.&.&.&.&.&.&.\\.&.&.&\bullet&.&.&.&.\\.&.&\bullet&\bullet&.&&&\\&&.&\bullet&.&&&\\&&&.&&&& \end{array}$

after which, as I described above, we can reduce the number of wrong lights by at least 3. We now have fewer wrong lights than we started with.

What we have found after all this work is this: Given any configuration with a nonzero finite number of wrong lights, we can reduce the number of wrong lights. Therefore, by doing this repeatedly, given any such configuration we can eventually correct all the wrong lights.

Or, answering the question as actually posed: Yes, I can characterize all the ultimately-fixable patterns of finitely many wrong lights: it's all of them.