Damaged lights proof

Question

There are $n$ lights in a row. Some of the $n$ lights are on. I can damage any light that is on. If I damage a light, each light directly adjacent to the damaged light will be turned on if it is off, off if it is on. Damaged lights remain unchanged. Prove that I can damage all $n$ lights if and only if the number of lights that are initially on is odd.

Example: off, on, off

I damage the 2nd light

on, (damaged), on

My thoughts are to prove by contradiction, where assume the number of lights turned on is even. But I can't see what follows.

Answer 1

Nice puzzle.

To make the question more clear, it actually means the following:

If an initial status of the lights has an odd number of lights on, then there exists a way (i.e. one specific order) to damage all the lights. Otherwise, there is no way to damage all the lights, in whatever order.

Proof:

We prove by induction on the number of lights in the row.

If there is only $0$ or $1$ light, then everything is clear.

Assume we have proved the result for $< n$ lights.

Now for $n(\geq 2)$ lights in a row, we consider the two cases:

• If there are an odd number of lights on, then we may damage (say) the first light on the left which is on. This will break the row into two parts, which then don't interfere with each other from that point on, hence could be viewed as two separate rows of lights.

  Now it is easy to see that both parts have either $0$ light or an odd number of lights on. By our induction hypothesis, there is a way to damage both of them.

• Similarly, if there are an even number of lights on, then whichever light you damage, there is always one part which has more than $0$ light and an even number of lights on. Again by our induction hypothesis, it is impossible to damage all the lights.

Answer 2

Method 1: The meta:

Note, you don't have to know how to damage them. Just to know that you can if and on if an odd number are odd.

Let's suppose you have proven this for all $n$ up to $k$ and now you have a row of $k+1$ lights.

Lets say you can damage all on bulbs. So you damage one of the bulbs that is on.

The bulbs to the left (if any) are now a row of bulbs less than $n$ that we've already claimed can be all damaged. So there are an odd number that are on now. But that bulb directly to the left of the damaged one has changed. SO originally there was an even number of bulbs on to the left of the bulb we damaged (if any). Or there were none.

Same thing with the bulbs to the right.

So originally there were an even number of bulbs on to the left (or there were no bulbs at all to the left). And there were an even number of bulbs on to the right (or there were no bulbs at all to the right). And there was the bulb we damaged that was on. So that means there were a total odd number of bulbs on.

And if we were told that there were an odd number of bulbs on but we weren't told we can damage them all, we can look the on bulb furthest to the right. If there are any bulbs to the right of it, they are all off. If there are any bulbs to the left of it, an even number (maybe zero) of them are on. Damage the right must bulb. If there were any bulbs to the right one is on, and so all the bulbs can be damaged. If there were any bulbs to the left there is not an odd number on. So all can be damaged.

...

So just have to do base case. If there are $k=1$ bulbs you get only damage them all if you can damage one and you can only damage one (odd if it is on).