The algorithm to find the required switches to turn on a light blub

Question

Assume you are in a room with N switches, and there's a light bulb in the next room. The light bulb is glowing only when some specified switches are all turned on.

Set

• switches = the set of all switches. |switches| = N.
• required = the switches which need to be turned on to make the bulb glowing.

The non-required switches doesn't matter.

You can only check whether the bulb is glowing only if you enter the next room. You can turn some switches on or off, go to the next room to check the bulb, and repeat this process. Let's call this one ATTEMPT.

Assume there is N switches, in WORST CASE, what's the minimum number of attempts needed to find out the set of required switches (using optimized strategy)?

---

For example,

• switches = { 1, 2, 3 }
• required = { 1, 2 }

Let's try with an naive approach:

• Turn on { 1, 2 }, the light is glowing. (Ensure switch 3 is not required)
• Turn on { 1, 3 }, the light is not glowing. (Ensure switch 2 is required)
• Turn on { 2, 3 }, the light is not glowing. (Ensure switch 1 is required)

Thus with 3 attempts, we can ensure required = { 1, 2 }.

What's the optimized algorithm for this problem?

Let worst(N) be the minimum attempt considering N switches in worst case. Could you find out worst(N)

UPDATE: If you think worst(N) = N, could you provide a formal proof?

Answer 1

Proof that worst case requires at least N attempts

If there are N switches, there can be 2^N possible sets of 'required' as each switch can either be in or out of the 'required' set.

To differentiate between the 2^N possible sets, you can think of it as we will need to obtain at least N bits worth of information by fiddling with the switches. If not, there is a possibility that there are more than 1 set that can both fit the information we know so far.

Lets assume that there are 8 possible configurations (N = 3) and we can select a subset of configurations and query whether the 'required' configuration is in the selected subset. The best way to do this would be akin to binary search, achieving a complexity of log(2^N) which is just N attempts. If we use less than 3 attempts, we will be left with at least 2 configurations that we cannot decide which is correct as each attempt will eliminate half of the possible configurations.

Coming back to the original problem, lets assume we use K attempts so far where K < N. Since each attempt will provide 1 bit of information (Yes, it lights up /No, it doesnt light up), each attempt can eliminate half the possible number of configurations, we will be left with 2^(N-K) possible configurations after K attempts.

To get to only 1 distinct possible configuration of the 'required' set, we will need K = N which will give us 2^(N-N) = 2^0 = 1 possible configuration.

This gives us the lower bound for this problem as each attempt will provide 1 bit of information (Yes, it lights up /No, it doesnt light up). Hence we will require at least N attempts.

Possible solution that uses not more than N attempts

Since the 'non required switches does not matter', if I interpret it correctly, it means that if switches outside of the 'required' set are turn on, in addition to those in the 'required' set, the light will still be on. As we have N attempts to utilize (and still make it optimal), we can afford to use the following solution: For each switch (in sequential order), turn on all other switches except for this switch. Check if light is switched off. If it is switched off, the only switch that remains off will be in the 'required' set.

This solution will use exactly N attempts (even in worse case) and it is one of the optimal solution (as proven earlier).

Answer 2

Assume there is N switches, in WORST CASE, what's the minimum number of attempts needed to find out the set of required switches (using optimized strategy)?

The brute force way, checking all possible combinations of switches until the light goes on, which would be O(2^N) (although we might get lucky and have the light switch on after our first try).

With more optimised searches, the set of required switches can be found in worst case O(N) attempts. Here is one way that is always O(N):

• Flip all N switches on: we know that the light will be on.

• Turn switch 1 off. If the light goes off, switch 1 is required so turn it back on. If the light stays on, leave switch 1 off because it's not required. (One attempt used).

• Turn switch 2 off: If the light goes off, switch 2 is required so turn it back on. If the light stays on, leave switch 2 off because it's not required. (Two attempts used).

• Repeat this check for each of the remaining switches. (N attempts used).

• After N attempts, we're left with the set of the required switches in the on position.

As noted in other answers/comments, it's also possible that the set of required switches can be found in best case O(log(N)) and worst case O(N):

• Flip all N switches on: we know that the light will be on.

• Flip the first N/2 switches off. In the light stays on, none of these switches were required, so we can leave the switches turned off. Move to the set of N/2 switches which are still on and repeat this step...

• If however the light went off, at least one of these N/2 switches was required: flip the switches back on, split the set in half and repeat the previous step...

This algorithm is worst case O(N) because we might have to check each switch individually (e.g. if there are 10 switches and the required configuration is 0101010101).