Switch off all the n bulbs, (n-1) at a time. A parity-based puzzle?

Question

So, here is a puzzle-like problem:

You have n light bulbs. Each one is connected to a special switch that flips the state of all the other n-1 bulbs except the bulb it is connected to.

If you start with all the bulbs turned on, can you switch all the lights off?

In my opinion, you can switch off all the bulbs iif n is an even number. Otherwise you can’t.

Some observations:

• At any state (ie a given number of n bulbs off and n-1 on), pressing any switch connected to any on (or any off) bulb leads to the same state.
• If you press a switch of a turned -on or -off light twice in a row, you come back to the initial state.

A strategy to switch off all the light is pressing alternately a switch connected to an on, and then to an off bulb, until you switch off them all.

I’m wondering if there is a more general and elegant solution to such a problem

Answer 1

Flipping a switch a second time cancels the effect of the first flip regardless of when it happens, so any solution will require at most one flip of any switch. Without loss of generality, suppose each switch can only be flipped once or not flipped.

A light will be off at the end if and only if the parity of the number of flipped switches attached to other bulbs is odd.

Now let's suppose we flip $k$ switches, where $0 < k < n.$ There is at least one bulb attached to a flipped switch, where the number of flipped switches attached to other bulbs is $k - 1,$ and one bulb attached to an unflipped switch, where the number of flipped switches attached to other bulbs is $k.$ Since $k$ and $k - 1$ have opposite parity, one of these bulbs will be on after the $k$ flips.

Obviously, if we flip $0$ switches then all bulbs remain on.

So there cannot be a solution with fewer than $n$ switches flipped.

If we flip all $n$ switches, all bulbs are off if $n$ is even and all bulbs are on if $n$ is odd. So there is no solution for $n$ odd, and a solution for $n$ even is to flip every switch once.

Answer 2

Well, you have already dealt with case N is odd: each press on a button doesn't change the parity of the number of on lights. Because you change the state of N-1 lights. And changing the state of 1 light change the parity. So changing the state of N-1 lights, change the parity N-1 times. And if N-1 is even, then it leads to the same parity. So, if N-1 is even, that is if N is odd, you are doomed to have a odd number of lights on. And since 0 is even, 0 is unreachable.

Now, if N is even:

Note that in a given state, with k lights on you can either

• Switch a "on" light (which means k>0). So, there are N-k lights off that become on. The k-1 other lights become off. And the one you have just switched stays on. So, all together, you now have N-k+1 "on" lights.
• Switch a "off" light (which means k<N). So, there are N-k-1 other "off" lights that become "on", and all the rest become or stay off. So you have now N-k-1 "on" lights.

If, k being even, k>0, you switch first a "on" light, leading to N-k+1 "on". Note that k being both even and >0, so k≥2 ⇒ k' = N-k+1 < N. So you can now switch a "off" light, since we are in the case k'<N. And we then have k'' = N-k'-1 "on" lights. That is k'' = N-(N-k+1)-1 = k-2 "on" lights.

So, each time you have an even number k>0 of lights on, you can always switch a "on" then a "off", and you go to a state with k''=k-2, also even, number of lights "on".

So if you start with all N lights on, all you have to do is alternatively trigger N switches, one "on", one "off", one "on", one "off", ... to reach 0.

Not only that is a sure path to switch all the lights off.

But you can even easily (from your own remarks), prove that this is the shortest path.

Since your remark (clicking twice the same switch goes back to the same state — and when we say "the same switch", in fact in means "a switch in the same state", since the state doesn't need to discriminate switchs other than from their "on", and "off" state. I mean, state of the world is entirely described by the number of "on" lights) means that doing something else that strictly alternating switches (click on a "on" one, then a "off") is a waste of time. Clicking twice in a row on a "on" or on a "off" is just adding 2 useless clicks to our path.

So, the shortest path has to be one that alternates "on" and "off" switches. And since at first we can obviously only click on a "on" one, the "on"-"off"-"on"-"off"-... is the optimal strategy. And we have seen that its length is N.

Note: in this answer, I call "on" switch, a switch associated to a "on" light.

2nd note: I am not 100% sure that you weren't aware of all that already. But since I don't know what you meant by "is there a more general solution"... and since your post does not really prove that the strategy works, just that it has to be the strategy. But well, I wouldn't say it is "elegant" demonstration; but I can't see how it could be more.