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
Best Answer
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.