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.
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.
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.
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!
