3
$\begingroup$

You have probably encountered the mini puzzle in various games where you have a set of switches and a set of lights (or other triggers), such that each switch "flips" the states of one or more lights ("on" becomes "off" and vice versa). You normally proceed through the puzzle by turning on all the lights. Both the switches and the lights have an initial state that's often a mixture of "on" and "off", and that it's not necessarily that turning off all the switches also turns off all the lights. You don't know which switch controls which set of lights at the beginning.

While the minigames you've seen often consist of 3 to 5 switches and lights, this time it's a generalized question. There are $S$ switches and $L$ lights in front of you, under a mixed state of "on" and "off". You have been told that there exists a combination of switches that could turn on all the lights (the solution is not necessarily unique). How many steps (flips of switches) do you need for some $S$ and $L$, to guarantee that you can turn on all lights (reach the "solved" state, not just finding the solution)?

$\endgroup$
  • $\begingroup$ "Guarantee that you can" and "guarantee that you know how to" mean two different things. The initial answer addresses the latter wording. If that's your intention, I recommend editing the wording. $\endgroup$ – Greg Martin Oct 17 at 18:37
  • $\begingroup$ @GregMartin The answer seems to have covered both meanings, read it thoroughly. Despite, I've updated the description for clarification. $\endgroup$ – iBug Oct 17 at 18:49
8
$\begingroup$

You need

at most S + min(S,L) - 1 flips.

First, an important thing to know:

flips are commutative: flipping switch 1, then switch 2, is exactly the same as flipping switch 2, then switch 1. So the only thing that matters is which switches are on and off, not what order you flip them in.

And you also only need to flip each switch at most once -- if you flip it twice, it's the same as not flipping it at all.

If S≤L:

Number the switches by the order the player tries them in. (If the player tries them in a different order, you can just renumber the switches.) If S≤L, it might be the case that: - the first switch you try controls light 1
- the second switch you try controls light 2
- the third switch you try controls light 3
- [...] - the (S-1)th switch you try controls light S-1
- the last switch you try controls all the lights.
Then, only switch $S$ must be flipped. You then must flip at least 2S-1 switches, no matter your strategy: you'll need to turn on all of them before you find the one that will solve it for you, and then you'll need to go back and turn off the other ones.

And you can always solve it in 2S-1 flips: flip all of them on, record which ones affect what, and then flip all of the ones you need to flip off. (Since there is a solvable configuration, you can do it in at most S flips; and you won't need to flip all of them off, because then it would've been solved at the start.)

If S≥L:

it's possible that the same thing happens -- but this time, the first (S-L) switches you try do nothing, and the remaining L switches are set up as before. So you need to flip all S switches to find the one you need, then turn off L-1 switches.

This shows that it's possible to have a switch configuration that forces S+L-1 moves -- but can we be forced to do more? The answer is no: all configurations will require at most L moves to get to the goal situation, once you figure out what the switches do and flip all of them. (This is explainable using linear algebra over 𝔽₂; I will try to explain for people who don't have any mathematical background. If you already know what "linear algebra over 𝔽₂" means, you can skip to the block labelled "So, what does this tell us?".).

Time for some math!

The setup:

Make a big chart of which switches affect which lights. For instance, you might have this situation, with 8 switches and 5 lights.

enter image description here

I've written to the right a goal for each light, either "even" or "odd". All that matters is whether the light is in the right state at the start: if it's in the right state, we want to switch it an even number of times. If it's in the wrong state, we want to switch it an odd number of times. We don't care whether it's on and we want it on, or it's off and we want it off -- both of those are "flip an even number of times".

So, a 'victory' comes from picking some of the columns to activate -- that is, some of the switches to flip -- so that the total count of Xs in each row matches the goal.

enter image description here

Here's one example victory: we've switched lights 1, 2, 4, and 5. The number of Xs in each of those rows matches the condition on the right, and so we've won. L₁ has one flip, which is odd; L₂ has two flips, which is even; and so on...

(It happens to be the case that all the 'odd's were 1 and all the 'even's were 2, but this isn't necessary. They can be any even or odd numbers.)

The Important Thing:

Now let's look at a set of switches. There's an interesting question we can ask: if we just had those switches, how many configurations could we reach?

Your first thought might be is "if we have n switches, we can always reach 2ⁿ configurations". But this isn't true: say we just had access to switches 2, 3, and 8.
enter image description here
Flipping 2 and 3 together would be the same as flipping 8! Both of the results would turn on just lights 3 and 4.

Likewise, flipping 2 and 8 together would be the same as flipping 3, flipping 3 and 8 would be the same as flipping 2, and flipping all three would be the same as doing nothing at all.

So, even though it looks like we have access to 3 switches, we effectively only have access to 2. We can take one of these switches out without changing what we can accomplish.

We say that a set of switches is independent if there are no redundancies like this. The rank of a certain set is the "effective" number of switches we have.

Now, the important fact: The rank of a set of switches can never be more than the number of lights they affect. (Convince yourself of this using the example: If you could find 6 different switches from this set that all worked independently, then you would be able to get 64 different configurations of lights from just those switches -- but there are only 5 lights, so you can only get 32 configurations total!)


So, what does this tell us?

We only have L "effective" switches at most. This means that there is some set of L switches that can give us the same combinations that all of the switches can give us. (You might not need L switches, because the switches might not give you all 2^L possible patterns. But you can just add extra useless switches to make a set of L that will give you every possible combination.) Let's call this a "spanning set".

Say we've flipped all but the last switch. There are two options:
- If we can get to the solution with just the switches we have, we can do that. We'll only need to flip at most L switches. So, after our initial run of S-1 flips, we need at most L more.
- If we cannot get to the solution with just the switches we have, that means that we haven't found a spanning set. So the last switch must be in all possible spanning sets! Once we flip the last switch, we'll be able to find a spanning set: it will include the last switch and L-1 other switches. We won't need to reflip the last switch, or we would've already been able to find a solution before we flipped it the first time. So we only need to worry about the L-1 others. So, after our initial run of S flips, we need at most L-1 more.

And either way, we can do it in S+L-1 flips total!

| improve this answer | |
$\endgroup$
  • $\begingroup$ Typo: you first deal with the case $S\leq L$ and then with $S\geq L$ (the Ifs outside the spoiler boxes are reversed) $\endgroup$ – eru-cs Oct 17 at 9:34
  • $\begingroup$ Superb answer!!! $\endgroup$ – Dmitry Kamenetsky Oct 17 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.