[bonanova]

In my kitchen there are 3 ceiling lights and 4 wall switches.

Here's the deal:

1. Each switch controls 1 and only 1 light.
2. Each light is controlled by at least one switch.
3. When you enter the kitchen [you might not want to open the fridge] you find the switches positioned randomly up or down.
4. Your mission, should you choose to accept it, is to determine how the lights and switches are connected.
5. You may [repeatedly, but using the same value of n each time] simultaneously change any n [0 < n < 4] of the switches and note what happens.

If you want to minimize the number of times you execute Step 5 above, is there a preferred value of n?

You might want to think of the lights as A, B and C; the switches as 1, 2, 3 and 4.

[Guest]

n=2 can get it in 3 every time.

Call the switches 1,2,3 and 4

First toggle 1 and 2 and then toggle 3 and 4. One of 3 things will happen:

Scenario A:

Both attempts, 2 lights changed. Call the light that changed only on the first attempt A, the light that changed only on the second attempt B and the light that changed on both attempts C.

Now toggle 2 and 3. One of 3 things will happen:

Scenario A1: A and C change. Then 1=C, 2=A, 3=C, 4=B

Scenario A2: B and C change. Then 1=A, 2=C, 3=B, 4=C

Scenario A2: Nothing changes. Then 1=A, 2=C, 3=C, 4=B

Scenario B:

The first attempt, nothing happened and the second attempt 2 lights changed. Call the lights that changed A and B and the light that never changed C.

Now toggle 2 and 3. One of 2 things will happen:

Scenario B1: A and C change. Then 1=C, 2=C, 3=A, 4=B

Scenario B2: B and C change. Then 1=C, 2=C, 3=B, 4=A

Scenario C:

The first attempt, 2 lights changed and the second attempt nothing happened. Call the lights that changed A and B and the light that never changed C.

Now toggle 2 and 3. One of 2 things will happen:

Scenario C1: A and C change. Then 1=B, 2=A, 3=C, 4=C

Scenario C2: B and C change. Then 1=A, 2=B, 3=C, 4=C

[Guest]

Operating 2 or 3 switches at a time, we can know which switch controls which light in 3 tries in each case.

[Guest]

In my kitchen there are 3 ceiling lights and 4 wall switches.

Here's the deal:

1. Each switch controls 1 and only 1 light.
2. Each light is controlled by at least one switch.
3. When you enter the kitchen [you might not want to open the fridge] you find the switches positioned randomly up or down.
4. Your mission, should you choose to accept it, is to determine how the lights and switches are connected.
5. You may [repeatedly, but using the same value of n each time] simultaneously change any n [0 < n < 4] of the switches and note what happens.

If you want to minimize the number of times you execute Step 5 above, is there a preferred value of n?

You might want to think of the lights as A, B and C; the switches as 1, 2, 3 and 4.

[Guest]

if each switch only switches on one light, that would mean that 2 of the 4 switches flip on the same light and the other 2 switches turn on one light individually. i would say that the number of switches that need to be flipped would at most be 4. flip each switch until all the lights are on and mark each one as the lights come on. this will either be 3 or 4 flips if one of the switches is a 2-way and turns one of the lights back off. mark which switch turns on which light. if the first three switches turned on a light, then flip the fourth to see what light goes off and mark that one...let me know what you thing

[Guest]

Taking an answer from a simliar riddle: you can also use the fact that when a light is left on for a while and then turned off, you can know that it was on by touching the light and feeling the heat.

[Izzy]

Alright, so all the switches and lights are up and down, on and off randomly, but regardless of how they start, my method works, so for simplicity's sake, let's pretend they're all down and the lights are all off.

Aside from this scenario: You walk in, all lights are off, and one switch is up. For n = 1, you can get it in two turns for sures. There's a 25% chance of this, but it would work 100% of the time. Otherwise, this method sort of sucks, because it can take between 3 and 4 tries to get it right.

Now, skipping some stuff I was mulling over in my mind, n = 2 and n = 3 can also get it in two flips each, as long as the best possibly scenario occurs.

For n = 2, if we flip two switches that turn on two lights first, no matter what, we can get it in two turns. Just leave one switch, flip another one, and you'll know which light every switch controls. This involves not flipping the switch that does nothing first go. You're guaranteed to flip at least one switch that works, so 3 switches are left. 66% chance of it going the way you want.

For n = 3, the best possible scenario would be this: You flip two switches that work, and one that doesn't. So let's say lights A and B are lit up, and switches 1, 2, and 3 have been used. Flip 1 and 3 down, and 4 up. (Pretend 1 controls A, 2 controls B, and 3 is the blank one.) If you managed to use the blank switch again, you can get it in two.

For the first time, you have a 50% chance of flipping the switch you want (you get two on switches for sures, and you want one of the remaining switches). Getting again is another 50% chance. Multiply. 25% chance of doing this.

N = 2 is your best bet.

Welcome back btw! ;D

Edited March 4, 2010 by Izzy

[bonanova]

Thanks for the WB

It's OK to assume you find the switches all down.

But, you know nothing initially about their connections.

So you won't get the answer by assuming favorable

outcomes to your first flip.

You want to minimize the required number of flips

[that implies worst-case analysis] with respect to n.

Is there a preferred value [singular] for n?

1. Yes; n=1
2. Yes; n=2
3. Yes; n=3
4. No

[Izzy]

[spoiler=Alright, let's try this again. ]Worst case scenarios:

For n = 1, it will take a maximum of three flips.

n = 2, again I think a maximum of three. I couldn't figure out any combination that would require four flips. Actually, hold up. I think I can do it in two every time. Flip two switches. (Oh, change in light from initial position = "on".)

Either one light is on and one is off or two lights are on. Flip down one of the switches you originally switched and flip one of the remaining switches.

In the first scenario, there are two possibilities. You have already flipped the blank switch to get to this point. You can either flip the blank switch and a remaining switch (letting you know which one controls the original light because it stayed on, which switch controlled the light that just turned on, and which one is blank, leaving you with the third switch.) Or you flip the non-blank switch and still another switch. So the light that changes for the second time is the switch you've switched twice so far, the other switch is the blank switch, and the switch you switched again in round two controls the light you've seen change this round.

In the second scenario, you have two lights on after the initial round of flipping. Flip two more (one of the ones you've already flipped + another). If you get the blank, it's obvious which one is which. If you get the third light, again, obvious, because one of the other lights turned "off".

Unless I'm missing something? Then n = 3 for this one.

n = 3.. doesn't matter at this point. I don't think. I can do it in three every time.

..So n = 2. Unless I'm wrong about that. In which case.. it doesn't matter.

[bonanova]

Partial, but not the complete, answer so far.

Suppose we flip n switches at a time.

It will require f_n flips to guarantee [this means worst case] learning how the lights are connected.

The problem asks us to find f₁, f₂ and f₃ and see whether one of them is less than the other two.

It's not a hard problem.

I mused for a day or two without using paper before posting it.

Full disclosure, I needed paper.

[Guest]

Operating 2 or 3 switches at a time, we can know which switch controls which light in 3 tries in each case.

I'm not convinced that n=3 can do it in 3 consistently. Care to elaborate?

I'm gonna stick with Yes, n=2

[Guest]

Partial, but not the complete, answer so far.

Well, there are 36 possible cases.

When n=1, flipping a switch can only have one of 3 outcomes. Best case scenario, each flip splits up the cases evenly. 1st flip, 12 cases left. 2nd flip, 4 cases left. 3rd flip can only discern between 3 cases so we need a 4th. So in theory and at best n=1 does it in at most 4.

I've already shown how n=2 can do it in at most 3.

When n=3, there are 4 outcomes. Either only one light switches (3 outcomes) or all the lights switch (1 outcome). On the first flip, the single outcome of all the lights switching accounts for a full half of the possibilities (18). Once this outcome has happened it cannot happen again unless we flip the same 3 switches. So after this we are down to 3 outcomes. From here, best case scenario, each flip splits up the cases evenly. 2nd flip , 6 cases left. 3rd flip, 2 cases left. We'd also need a 4th try here. So again, in theory and at best n=3 does it in at most 4.

So n=2 is best.

Edited March 5, 2010 by Tuckleton

[bonanova]

Yeah, what Tuckleton said.

[plainglazed]

I think depending on how you define the OP and what minimizing the number of tries is (with certainty each time or on average), you might still make a case for DeeGee's 3. Suppose you throw swithches 1,2,3 and only A toggles then throw 1,2,4 and only B toggles. This defines B<>4, A<>3 and C<>1&2 in only two tries. But conversely, if you throw 1,2,3 and A,B,C toggle you could get the same outcome, Tuck, by throwing 1,2,4 (again toggling A,B,C) thus defining 3&4 as the switches that throw the same light but it will take two more throws to define which lights. Both of these cases occur with the same probability averaging out to three tries for throwing three switches; the same as if throwing two switches.

[Izzy]

Well, there are 36 possible cases.

When n=1, flipping a switch can only have one of 3 outcomes. Best case scenario, each flip splits up the cases evenly. 1st flip, 12 cases left. 2nd flip, 4 cases left. 3rd flip can only discern between 3 cases so we need a 4th. So in theory and at best n=1 does it in at most 4.

I've already shown how n=2 can do it in at most 3.

When n=3, there are 4 outcomes. Either only one light switches (3 outcomes) or all the lights switch (1 outcome). On the first flip, the single outcome of all the lights switching accounts for a full half of the possibilities (18). Once this outcome has happened it cannot happen again unless we flip the same 3 switches. So after this we are down to 3 outcomes. From here, best case scenario, each flip splits up the cases evenly. 2nd flip , 6 cases left. 3rd flip, 2 cases left. We'd also need a 4th try here. So again, in theory and at best n=3 does it in at most 4.

So n=2 is best.

Couldn't you at least make the logical deduction (with n=1, and I guess the others), that if you've flipped three of the switches and one of the lights hasn't come on, that the remaining switch controls it? So it would never take four flips for n=1, and likewise with n=2, it would never take three. (I'm gonna be honest, I got lazy and never really worked out the logistics of n=3. )

[bonanova]

Couldn't you at least make the logical deduction (with n=1, and I guess the others), that if you've flipped three of the switches and one of the lights hasn't come on, that the remaining switch controls it? So it would never take four flips for n=1, and likewise with n=2, it would never take three. (I'm gonna be honest, I got lazy and never really worked out the logistics of n=3. )

If the first 3 flips don't include both 2-way switches, it takes four flips

Call the bulb S1 changes bulb A

S1 changes A

S2 changes A

S3 changes B: A12 B3 C4 [three flips do it]

S1 changes A

S2 changes B

S3 changes B: A1 B23 C4 [three flips do it]

S1 changes A

S2 changes B

S3 changes C: A14 B2 C3 / A1 B24 C3 / A1 B2 C34 [unresolved after 3 flips]

S4 is needed to identify the two-way light

Flipping 2 switches changes 0 or 2 bulbs

If S1 S2 change two bulbs, label them A B

In all cases, three flips suffice.

S1 S2 change A B

S3 S4 change nothing: either [A1 B2 C34] or [A2 B1 C34]

S1 S3 change C A --> A1 B2 C34 [three flips do it]

C B --> A2 B1 C34 [three flips do it]

S1 S2 change A B

S3 S4 change A C [label the bulb that changes both times A; it's the 2-way bulb]

S1 S3 change B C ------> A24 B1 C3 [three flips do it]

A C ------> A14 B2 C3 [three flips do it]

A B ------> A23 B1 C4 [three flips do it]

nothing --> A13 B2 C4 [three flips do it]

S1 S2 change nothing: they are the 2-way switches.

S1 S3 change A B: either A3 B12 C4 or A12 B3 C4

S3 S4 change the two 1-way bulbs [either A C or B C], resolving the two cases above. [three flips do it]

Suppose S1 S2 S3 change only one bulb - label it A

Suppose S1 S2 S4 change only one bulb [it will be a different one of course] label it B

Then S1 S2 are the 2-way switches, and they must control the third bulb; label it C.

A3 B4 C12! we're done in two flips.

Again, suppose S1 S2 S3 change only one bulb - label it A,

and label the others B and C in some order.

But now suppose S1 S2 S4 change all three bulbs.

We then have four cases: [A1 or A2] and [b4 or C4]:

A1 B4 C23 / A1 B23 C4 / A2 B4 C13 / A2 B13 C4

We've tried flipping all but S4 and all but S3.

What remains is to flip either all but S2 or all but S1.

A1 B4 C23 -> S1 S3 S4 change A B C [unresolved]

A2 B4 C13 -> S1 S3 S4 change B

A1 B23 C4 -> S1 S3 S4 change A B C [unresolved]

A2 B13 C4 -> S1 S3 S4 change C

A1 B4 C23 -> S2 S3 S4 change B

A2 B4 C13 -> S2 S3 S4 change A B C [unresolved]

A1 B23 C4 -> S2 S3 S4 change C

A2 B13 C4 -> S2 S3 S4 change A B C [unresolved]

Both of these third-flip choices leave two indistinguishable cases,

where A is associated with its unique [1-way] switch,

but B and C are not identified with their switches.

So here is a case where a fourth flip is required.

[bonanova]

I think depending on how you define the OP and what minimizing the number of tries is (with certainty each time or on average), you might still make a case for DeeGee's 3. Suppose you throw swithches 1,2,3 and only A toggles then throw 1,2,4 and only B toggles. This defines B<>4, A<>3 and C<>1&2 in only two tries. But conversely, if you throw 1,2,3 and A,B,C toggle you could get the same outcome, Tuck, by throwing 1,2,4 (again toggling A,B,C) thus defining 3&4 as the switches that throw the same light but it will take two more throws to define which lights. Both of these cases occur with the same probability averaging out to three tries for throwing three switches; the same as if throwing two switches.

Edit: The OP suggests that it's only the worst case we want to optimize, not the average;

but it falls a little short of being explicit on that point ... my bad.

- bn

DeeGee is correct for n=2 but not for n=3.

The OP asks whether there is a preferred value of n.

The answer is Yes: n=2 gets you there in no more than 3 flips.

For other values of n, 4 flips might be needed.

Edited March 7, 2010 by bonanova
Comment on Average vs. Worst Case

[Izzy]

I thought one of the switches did nothing instead of two controlling the same light. >_>