[bushindo]

Suppose that you are in a room with 16 light switches, which are arranged in a line on the wall. Each light switch is connected to a unique lightbulb in another room. However, some of the 16 lightbulbs are burned out, which means that the 16 light switches you see consist of functional and non-functional switches. The light switches are currently all set in the OFF positions. It is also known that the 16 switches are arranged in such a manner that within any 7 consecutive light switches, there are an odd number of functional switches. Assume that setting a functional switch to the ON position will turn on the corresponding lightbulbs, and similarly setting it to OFF will turn off the bulb. Turning any switch connected to a burned-out bulb to ON, of course, will have no effect on the bulb.

You are allowed to take 'turns' to deduce the position of the functional switches. During a turn, you can set the 16 light switches to any ON/OFF configuration you wish, and someone from the room with the lightbulbs will tell you how many lightbulbs are on.

Determine a strategy that is guaranteed to identify all the functional light switches using only 5 turns.

Edited November 30, 2010 by bushindo

[Guest]

wow... this is gonna be a confusing one... Nice Job!!! Can't wait to see how many tries it actually gets!!!!

[Akriti]

Can I know how many are burned out? Just to know when I am done (in the process).

Thank You

[Guest]

Since the OP says, any 7 consecutive bulbs have ODD number of fuctional bulbs, this makes the task a lot easier!

Now, each set of 7 bulbs have either 1,3,5 or 7 functional bulbs.

These sets are 1 to 7, 2 to 8 .... 10 to 16

A quick simulation of possibilites, will show that for 1 functional bulb per 7, there are in total 2 or 3 functional bulbs needed.

For 3 bulbs functionaing, there are either 6,7 or 8 total functional bulbs needed

For 5, there are 10,11 or 12 functional bulbs needed and for 7, all 16 bulbs should be functioning.

So, the first step would be to switch on all the switches to see how many bulbs are functioning. This would in case of 16, the answer is pretty much straight forward.

In case of 2 bulbs functioning, you know that switches 1 to 7 have 1 bulb functioning, 8 to 14 have 1 bulb functioning. If there are 3 total functioning bulbs, you know 1 to 7 have 1 bulb functioning, 8 to 14 have 1 bulb functioning and either of 15 or 16 has a functioning bulb.

In the next 4 tries, you can find out the right combinations (I'm too lazy to detail those )

In case of 6/7/8 bulbs functioning, again you can find out the options for bulbs functioning but looking at the various possibilities and cchekcing them out in the next 4 tries. Similarly for 10/11 or 12 bulbs functioning.

The Key in finding out these possibilities is to list down what all possibilities exist and checking for some specific switches only to see if the bulbs go on or not. Again, I'm too lazy to list them all but if no one else has a better idea, I might list it out

[k-man]

Indeed, every 7 consecutive light switches having an odd number of working light bulbs is a big help. It basically narrows down the problem to the first 7 switches and the total number of 16 becomes irrelevant. It could be a total of 2000 switches and it wouldn't change the problem. The pattern of the first 7 switches will repeat indefinitely.

For every working switch x, the switch x+7 is working too and for every broker switch y, switch y+7 is broken too. This comes from the fact that 7 consecutive switches starting with x have an odd number of working switches. For the number of working switches to remain odd when we move to the 7 switches starting with x+1 the x and x+7 must be the same. So now we only need to figure out how to determine which of the first 7 switches are working from 5 tries. That will be in my next post, unless someone beats me to it.

[araver]

Unless I'm missing something, it can be done in less turns.

First of all denote a_i=1 if switch i is connected to a functional lightbulb and 0 if connected to a burned-out lightbulb. i=1..16.

Now since within any 7 consecutive light switches, there are an odd number of functional switches, our mission is much easier than it sounds:

a1+a2+a3+a4+a5+a6+a7=1(mod2) (odd)

a2+a3+a4+a5+a6+a7+a8=1(mod2) (odd)

therefore

a1-a8=1-1(mod2)

i.e. a1=a8(mod2)

Shifting the 7-consecutive window shows that a_i=a_(i+7), i=1..9. So, there are only 7 unknowns that I'll re-note as a,b,c,d,e,f,g in 0..1. The relations above mean that the line of a_i's can be written as:

abcdefgabcdefgab

We know g=a+b+c+d+e+f+1 (mod2), so there are only 6 independent unknowns. Each try would give us an equation over these unknowns, so we have 5 equations (that can be chosen adaptively). If the rules were different and we had only known after each try if an ODD or EVEN number of bulbs are on, then a 5 equation system (over boolean ring) could not have given all 6 boolean unknowns. So we must exploit the fact that the system is actually in integers and not booleans. We can use 2 copies of each unknown and 3 copies for a and b. Round 1 - We try S1 = 3*a + c (switches 1, 8, 15=3a and switch 3 for c) Now if S1>=3 then a=1 else a=0 (crucial here are the 3 copies). Knowing S1 and a means we know c. Round 2 - We try S2 = 3*b + d (switches 2, 9, 16=3b and switch 4 for d) Again, same reasoning, if S2>=3 then b=1 else b=0. Knowing S2 and b means we know d as well. Round 3 - We try S3 = e (switch 5) Round 4 - We try S4 = f (switch 6) So, only 4 turns needed to know all 6 independent unknowns, g can be computed from g=a+b+c+d+e+f+1 (mod2). All 16 of the switches are known replacing abcdefg in this schematic:

abcdefgabcdefgab

[k-man]

See my previous post for the starting argument for why we only need to figure out switches 1-7 to solve the problem.

To figure out the first 7 switches we only need to know 1-6. The 7th switch can be deduced from the fact that the number of working switches is odd.

Step 1: Turn on switches 1 and 2. If we get 0 or 2 lights we know the status of the first 2 switches. The worst scenario is we get 1 light on. Move on to the next 2 switches...

Step 2: Turn on switches 3 and 4. If we get 0 or 2 lights we know the status of these 2 switches too. The worst scenario is we get 1 light on. Move on to the next 2 switches...

Step 3: Repeat with switches 5 and 6. If we get 0 or 2 lights we know the status of these 2 switches. The worst scenario is we get 1 light on.

Now, if we had any zeros or 2s then we just need to test the pairs that had 1. Flip one of the switches in the pair(s) that had 1 and determine which one it is. We will need at most 2 steps to do that as there are at most 2 pairs with 1. Done in 5 steps.

If all thress pairs had 1 working switch then we proceed with:

Step 4: Turn on switches 2 and 3. If 0 or 2 lights are on we know what switches in 1-4 are working. Use step 5 to test the remaining pair 5-6. Done in 5 steps.

If in step 4 we had 1 light working then it could be that the lights 1 and 3 are working or the lights 2 and 4 are working.

Step 5: Turn on lights 1, 3 and 5.

If we have 0, then the working lights are 2,4 and 6.

If we have 1, then the working lights are 2,4 and 5.

If we have 2, then the working lights are 1,3 and 6.

If we have 3, then the working lights are 1,3 and 5.

Done in 5 steps.

[k-man]

Building on top of my previous posts and araver's post.

Step 1: Turn on lights 1,3,5,8,10,15. Note that 1,8 and 15 will have the same status. So will 3 and 10. Here are the possiblities:

6 on - all 6 working

5 on - 5 is not working

4 on - 3 and 10 are not working

3 on - 3, 5, 10 not working

0 on - none working

We determined the status of lights 1-3 in step 1.

Step 2: Turn on lights 2,4,6,9,11,16. Same as before, 2,9 and 16 will have the same status. So will 4 and 11. Using the same logic we can figure out the status of 2,4 and 6.

[araver]

Building on top of my previous posts and araver's post.

Step 1: Turn on lights 1,3,5,8,10,15. Note that 1,8 and 15 will have the same status. So will 3 and 10. Here are the possiblities:

6 on - all 6 working

5 on - 5 is not working

4 on - 3 and 10 are not working

3 on - 3, 5, 10 not working

0 on - none working

We determined the status of lights 1-3 in step 1.

Step 2: Turn on lights 2,4,6,9,11,16. Same as before, 2,9 and 16 will have the same status. So will 4 and 11. Using the same logic we can figure out the status of 2,4 and 6.

It's a nice thought and I had it too before posting. But you are missing something.

However, based on your idea I can modify my idea to do it in 3 steps:

When you say: "Step 1: Turn on lights 1,3,5,8,10,15. Note that 1,8 and 15 will have the same status. So will 3 and 10. "

From my terminology your step 1 means 3*a+2*c+e=S.

All results yield an unique arrangement except for S=3 (this is because you got 8 possibilities for (a,c,e) and only 7 possible S results 0,1,2,3,4,5,6).

S=6=> a=1,c=1,e=1

S=5=> a=1,c=1,e=0

S=4=> a=1,c=0,e=1

S=2=> a=0,c=1,e=0

S=1=> a=0,c=0,e=1

S=0=> a=0,c=0,e=0

However you can get S=3 in two different ways a=0, c=1, e=1 or a=1, c=0, e=0.

Same goes for step 2 asking 3*b+2*d+e.

However, a solution with your first steps can be continued to reach a nice 3-step solution

- If in no step you got 3 you know all, case closed after 2 steps.

- If in only one step you got 3, then you can just retry a single bulb from that case to determine for sure (since it's either 011 or 100).

- If in both steps a and b you get 3 as a result, there are four different possibilities all depending on a and b.

So you just ask 2*a+b (switch 1, 8 and 2):

If 2*a+b >=2 then a=1 else a=0. Knowing a means you know c and e from step 1.

Knowing a and 2*a+b means you know b and d from step 2.

If we had more lights - at least 21+2=23 bulbs, then we would have 4 copies of a and b and a 2-step solution would work since:

S=4*a+2*c+e yields unique results (because a, c and e would be the digits of the binary representation of S).

Edited November 30, 2010 by araver

[k-man]

It's a nice thought and I had it too before posting. But you are missing something.

However, based on your idea I can modify my idea to do it in 3 steps:

When you say: "Step 1: Turn on lights 1,3,5,8,10,15. Note that 1,8 and 15 will have the same status. So will 3 and 10. "

From my terminology your step 1 means 3*a+2*c+e=S.

All results yield an unique arrangement except for S=3 (this is because you got 8 possibilities for (a,c,e) and only 7 possible S results 0,1,2,3,4,5,6).

S=6=> a=1,c=1,e=1

S=5=> a=1,c=1,e=0

S=4=> a=1,c=0,e=1

S=2=> a=0,c=1,e=0

S=1=> a=0,c=0,e=1

S=0=> a=0,c=0,e=0

However you can get S=3 in two different ways a=0, c=1, e=1 or a=1, c=0, e=0.

Same goes for step 2 asking 3*b+2*d+e.

However, a solution with your first steps can be continued to reach a nice 3-step solution

- If in no step you got 3 you know all, case closed after 2 steps.

- If in only one step you got 3, then you can just retry a single bulb from that case to determine for sure (since it's either 011 or 100).

- If in both steps a and b you get 3 as a result, there are four different possibilities all depending on a and b.

So you just ask 2*a+b (switch 1, 8 and 2):

If 2*a+b >=2 then a=1 else a=0. Knowing a means you know c and e from step 1.

Knowing a and 2*a+b means you know b and d from step 2.

If we had more lights - at least 21+2=23 bulbs, then we would have 4 copies of a and b and a 2-step solution would work since:

S=4*a+2*c+e yields unique results (because a, c and e would be the digits of the binary representation of S).

I agree. As always, you are correct!

Good one, Bushindo!

[bushindo]

I agree. As always, you are correct!

Good one, Bushindo!

Good work, k-man and araver. As usual, araver contributed beyond the requirement of the OP and taught me something new. I have another puzzle up that you both probably will enjoy.

Edited November 30, 2010 by bushindo

[Guest]

Good work, k-man and araver. As usual, araver contributed beyond the requirement of the OP and taught me something new. I have another puzzle up that you both probably will enjoy.

Thanks Bushindo. I really enjoyed this one and agree with the answer of 3.

An interesting question would be how many switches, with all the same conditions other than the number of switches, would be the minimum needed to allow you to answer the question with 1 test? Don't have the answer, but I'm going to work on it.

[bushindo]

Thanks Bushindo. I really enjoyed this one and agree with the answer of 3.

An interesting question would be how many switches, with all the same conditions other than the number of switches, would be the minimum needed to allow you to answer the question with 1 test? Don't have the answer, but I'm going to work on it.

Interesting question indeed. I would say that a preliminary guess is 217, just enough so that the first switch will have 31 copies. But 217 seems to be rather inefficient, however. I'll have to think about other ways to improve upon that.

Edited December 6, 2010 by bushindo

[Guest]

Interesting question indeed. I would say that a preliminary guess is 217, just enough so that the first switch will have 31 copies. But 217 seems to be rather inefficient, however. I'll have to think about other ways to improve upon that.

I think you are close.

I think the test has to look like:

one switch with 1 copy

one switch with 2 copies

one switch with 4 copies

one switch with 8 copies

one switch with 16 copies

and one switch with 32 copies

So you need 31*7+1=218 switches

[Guest]

Interesting question indeed. I would say that a preliminary guess is 217, just enough so that the first switch will have 31 copies. But 217 seems to be rather inefficient, however. I'll have to think about other ways to improve upon that.

I just came up a more elegant approach to the original problem, that still yields an answer of 3 tests. But using this approach, you can solve for fewer switches than 16 in 3 tests.

My new question is, what is the minimum number switches you can have that will allow you to solve in 3 tests?

[k-man]

I just came up a more elegant approach to the original problem, that still yields an answer of 3 tests. But using this approach, you can solve for fewer switches than 16 in 3 tests.

My new question is, what is the minimum number switches you can have that will allow you to solve in 3 tests?

You can do it in 3 tests with 10 switches. You can flip 1, 4 and 8 to figure out state of 1 and 4. Repeat with 2, 5 and 9. And then again with 3, 6 and 10.

But of course 3 switches is the TRUE minimum

Edited December 6, 2010 by k-man