[bushindo]

This is inspired by bonanova's light switch problem.

Suppose that there are 32 light switches in room A, which corresponds to 32 light bulbs in room B. Let's say that each switch can either be set in an "Up" or "Down" position. Which position corresponds to the "On" status in the next room is unknown for every switch. The game consists of the following terms. At each turn, you are allowed to set all 32 switches in any configuration you pick. You can not see the light bulbs in room B, but an official will tell you how many light bulbs are on at the end of every turn. The game ends when you can turn all 32 lights on.

1) Suppose that on your first turn, all the switches were in a random up down configuration, and the official tells you that 3 lights are on. What is the minimum number of turns required to turn all the lights on, even in the worst case ?

2) Suppose that the switches are set in random positions. What is the minimum number of turns required before you are guaranteed to win?

[Guest]

1. 35 (3 + 32)

2. 63 (31 + 32)

[Guest]

1. 31 turns. Simply flip each switch in turn and note whether or not the number of lit lights increases or decreases. The last switch is known when you know all of the others.

2. 32 turns. Since the problem doesn’t provide the number of lit lights in Room B you must use an additional turn to get this starting state information.

[Guest]

Solutions and Descriptions

For #1:

22

By testing in groups of 8, get at least 11 (3+8) light bulbs on in 4 moves; Then, test half of each of the remaining groups (1 turn). If, worst case, the test is inconclusive (not all originally off), reset and switch remaining half (+ 1 turn = 2 turns total). Repeat this for each subsequent half of the unknown switches (so, for groups of 4,2, and 1). Worst case, you will guess the wrong half every time and require 2 moves per group per level. With 3 groups per level (assuming every initally-on switch is separated from the others) and 3 levels, this results in 2 moves * 3 groups * 3 levels = 18 moves. Add the initial 4 moves for testing the groups of 8: 18+4 = 22 moves.

In the event that there are multiple initially-on switches under a single group, a larger number of switches will be eliminated in a single bisection, reducing the number of turns required. Therefore, 22 moves is the minimum number moves required to guarantee a solution in the worst case scenario

For #2:

32

In the worst case, there would be 16 light bulbs on initially, with the controlling switches distributed evenly, but randomly (i.e. no patterns or grouping).

If there are 15 or fewer switches on initially, the method from #1 can be used, starting at the appropriate level (0-1: 16;; 2-3: 8;; 4-7: 4;; 8-15: 2), and using a fewer number of switches.

For 16 switches however, we must step to the next level, by ones. Where we had 4 groups of 8 before, we now have 32 groups of 1, and just like we were able to determine the groups containing initially-on switches and those without for the groups of 8 in 4 moves (== # groups), we would need 32 moves to determine the state of the 32 groups of ones.

If there are initially over 16 switches on, determine your groups based on the number of light bulbs off instead of on (so, for 27 bulbs initially on, start with 8 groups of 4), and then use the same elimination process.

Working on a "proof" using a recursive program in Ruby. I'll post it when I get it finished

[Guest]

For the first scenario, it can be done in as little as 18 turns guaranteed. If you switch 3 switches at a time, you learn either that all 3 of the switches are controlling lights other than the originals, or 1,2,or all 3 of the originals. If there is only one of the original 'on' lights in the group, you may have to use up to 2 more turns to determine which one, if there are 2 lights from the original 'on' group in there, you may have to use up to 2 turns to determine which switch does not control them. If all three control them, it makes it ver simple. After each turn, return all lights to off before trying the next group of 3. After at most 17 turns, you will have all the lights off, then you can turn them all on for your 18th turn....actually, if you keep all lights on, it'll only take 17 turns.

Edited June 22, 2009 by perk8504

[Guest]

*note, got the same results using 4 instead of 3

[Guest]

first flip 16 switches.

AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBB

then based on the number, you can know how you are doing.

if you have 15 lights on then you know you turned off 2 lights, and the third light is in the other half.

flip 4 switches in the A half, and 8 switches in the B half.

AAAAAAAAAAAACCCCBBBBBBBBDDDDDDDD

if you now have 9 lights on, then you know you have 1 in group C and 2 in group B.

the worst case would be13, signifying you have one in group A, B and D.

in the worst case, flip 6 in A, four in B, and three in D.

AAAAAAEEEEEECCCCBBBBFFFFDDDDDGGG

based on what you get you can again deduce what groups the lights are in.

if you get 18 for example, then the three lights are in group A, B and D.

etc.

6 turns max.

[Guest]

Solution for bonanova's light switch problem #1.

For those of you that have ever played the "higher/lower" pricing game on "The Price is Right" then this should make perfect sense.

You must take the shortest path to discover which switches are already on. With 32 switches and 3 bulbs lit, divide the switches in half and instantly you know which half of the light switches control how many of the already on lights.

3 lights already on + 16 switch moves will = 16, 17, 18 or 19 light on. If it is 16 then your task will be even easier since you know that all 3 lights that were originally on are controlled within the first 16 switches that were manipulated. Otherwise, with any other number of lights on, you will have to test the other 16 switches but not the original 16 if 19 lights came on. The test methodology continues to cut the number of switches tested in half. After all the tests you will need to return all the lights to the on postion. Worst case scenario, this can be solved in 15 steps. It can also be solved in less with some luck. The testing will look like this:

Keep in mind that any time the net total of 'lights on or off' increases by the exact number of 'switches flipped', no longer test that branch but shift to the next branch in the heirarchy. Only test down the branch that the number of switch flips does NOT equal the number of lights that change state.

Flip the first 16 switches:

If 16 'lights on' then 3 went out and first 3 are controlled by (1-16). Test only this side.

If 19 'lights on' then 3 went on and first 3 are controlled by (17-32). Test only this side.

If 17 or 18 'lights on' then test both branches.

Solution = 15 moves

This is the worst case test:

Branch 1

16 (1-16)

8 (1-8)

4 (1-4)

2 (1-2)

1 (1)

Branch 2

8 (17-24)

4 (17-20)

2 (17-18)

1 (17)

Branch 3

4 (25-28)

2 (25-26)

1 (25)

Branch 4

2 (29-30)

1 (29)

ON

[Guest]

Correcting errors in my original post:

Solution for bonanova's light switch problem #1.

For those of you that have ever played the "higher/lower" pricing game on "The Price is Right" then this should make perfect sense.

You must take the shortest path to discover which switches are already on. With 32 switches and 3 bulbs lit, divide the switches in half and instantly you know which half of the light switches control how many of the already on lights.

3 lights already on + 16 switch moves will = 13, 15, 17 or 19 light on. If it is 13 then your task will be even easier since you know that all 3 lights that were originally on are controlled within the first 16 switches that were manipulated. Otherwise, with any other number of lights on, you will have to test the other 16 switches but not the original 16 if 19 lights came on. The test methodology continues to cut the number of switches tested in half. After all the tests you will need to return all the lights to the on postion. Worst case scenario, this can be solved in 13 steps. It can also be solved in less with some luck. The testing will look like this:

Keep in mind that any time the net total of 'lights on or off' increases by the exact number of 'switches flipped', no longer test that branch but shift to the next branch in the heirarchy. Only test down the branch that the number of switch flips does NOT equal the number of lights that change state.

Flip the first 16 switches:

If 13 'lights on' then 3 went out and first 3 are controlled by (1-16). Test only this side.

If 19 'lights on' then 3 went on and first 3 are controlled by (17-32). Test only this side.

If 15 or 17 'lights on' then test both branches.

Solution = 13 moves

This is the worst case test:

Branch 1

16 (1-16)

8 (1-8)

4 (1-4)

2 (1-2)

1 (1)

Branch 2

8 (17-24)

4 (17-20)

2 (17-18)

1 (17)

Branch 3

4 (25-28)

2 (25-26)

1 (25)

ON

Edited June 23, 2009 by TopShelfDave

[bushindo]

Correcting errors in my original post:

Solution for bonanova's light switch problem #1.

For those of you that have ever played the "higher/lower" pricing game on "The Price is Right" then this should make perfect sense.

You must take the shortest path to discover which switches are already on. With 32 switches and 3 bulbs lit, divide the switches in half and instantly you know which half of the light switches control how many of the already on lights.

3 lights already on + 16 switch moves will = 13, 15, 17 or 19 light on. If it is 13 then your task will be even easier since you know that all 3 lights that were originally on are controlled within the first 16 switches that were manipulated. Otherwise, with any other number of lights on, you will have to test the other 16 switches but not the original 16 if 19 lights came on. The test methodology continues to cut the number of switches tested in half. After all the tests you will need to return all the lights to the on postion. Worst case scenario, this can be solved in 13 steps. It can also be solved in less with some luck. The testing will look like this:

Keep in mind that any time the net total of 'lights on or off' increases by the exact number of 'switches flipped', no longer test that branch but shift to the next branch in the heirarchy. Only test down the branch that the number of switch flips does NOT equal the number of lights that change state.

Flip the first 16 switches:

If 13 'lights on' then 3 went out and first 3 are controlled by (1-16). Test only this side.

If 19 'lights on' then 3 went on and first 3 are controlled by (17-32). Test only this side.

If 15 or 17 'lights on' then test both branches.

Solution = 13 moves

This is the worst case test:

Branch 1

16 (1-16)

8 (1-8)

4 (1-4)

2 (1-2)

1 (1)

Branch 2

8 (17-24)

4 (17-20)

2 (17-18)

1 (17)

Branch 3

4 (25-28)

2 (25-26)

1 (25)

ON

I'm seeing some interesting solutions here. The issue is that most of these solutions require way more turns than necessary. Can you find a solution to part I in less than 8 turns? I think 8 turn is not the minimum required, it may be even less. I'll get back to you on that. phillip1882's post is interesting. I'll need to take a longer look before I'm convinced.

Edited June 23, 2009 by bushindo

[bushindo]

I'm seeing some interesting solutions here. The issue is that most of these solutions require way more turns than necessary. Can you find a solution to part I in less than 8 turns? I think 8 turn is not the minimum required, it may be even less. I'll get back to you on that. phillip1882's post is interesting. I'll need to take a longer look before I'm convinced.

Can you find the solution to part I in 6 turns or less? phillip1882's method is a good point to start but needs refinement.

For part II, it is possible to win in less than 32 turns.

[Guest]

I'm seeing some interesting solutions here. The issue is that most of these solutions require way more turns than necessary. Can you find a solution to part I in less than 8 turns? I think 8 turn is not the minimum required, it may be even less. I'll get back to you on that. phillip1882's post is interesting. I'll need to take a longer look before I'm convinced.

I think the number of turns is directly related to the number of lights that need to be discovered. One light could forseeably be found with one turn 1/32 of the time but this is luck. At a minimum, it would take 5 turns to discover a single switch plus one to set all the lights to the on position(6). To find 2 bulbs, it takes an additional 4 turns(10). To find 3 bulbs, it takes an additional 3 turns(13) and to find 4 bulbs it takes an additional 2 turns(15). Granted you could find 3 bulbs in 1 turn if you were extremely lucky, but the minimum required to guarantee success for 3 bulbs is 13.

You can try this with playing cards. Start with all number cards, and 3 aces signifing the 3 lights. Turn all the faces down except the first 3 aces. Since you know where the aces are, purposely do not pick them to simulate the worst case scenario.

I'm pretty positive this is the solution since I did it like 5 times yesterday.

[Guest]

first flip 16 switches.

AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBB

then based on the number, you can know how you are doing.

if you have 15 lights on then you know you turned off 2 lights, and the third light is in the other half.

flip 4 switches in the A half, and 8 switches in the B half.

AAAAAAAAAAAACCCCBBBBBBBBDDDDDDDD

if you now have 9 lights on, then you know you have 1 in group C and 2 in group B.

the worst case would be13, signifying you have one in group A, B and D.

in the worst case, flip 6 in A, four in B, and three in D.

AAAAAAEEEEEECCCCBBBBFFFFDDDDDGGG

based on what you get you can again deduce what groups the lights are in.

if you get 18 for example, then the three lights are in group A, B and D.

etc.

6 turns max.

If you change multiple variables at the same time, you cant possibly know which one actually affected the state of the lights. I guarantee you can not do this in 6 turns.

[CaptainEd]

Can you find the solution to part I in 6 turns or less? phillip1882's method is a good point to start but needs refinement.

For part II, it is possible to win in less than 32 turns.

Suppose you have part I with a simplified regime: all switches are OFF, count = 3:

I'll number the lights 0-31,

1) Put 0-15 ON, count of 13

2) Put 0-7 ON (rest OFF), count of 5

How do we spend only 4 turns finding the 3 that are backward?

I don't know whether the process is to simply select by bit address, but I spent 5 queries just accessing all the bits, and it was not conclusive.

* 1,3,5,7 ON, count 2

* 2,3,6,7 ON, count 3

* 4,5,6,7 ON, count 2

There are still 4 sets of three numbers each that agree with these queries:

750, 741, 543, 651

Clearly, I don't grok the method. Accessing all the bit planes seems like it would be valuable, but I'm in agreement that it seems impossible to find them all in just 6. I look forward eagerly to the 6-solution!

[bushindo]

Suppose you have part I with a simplified regime: all switches are OFF, count = 3:

I'll number the lights 0-31,

1) Put 0-15 ON, count of 13

2) Put 0-7 ON (rest OFF), count of 5

How do we spend only 4 turns finding the 3 that are backward?

I don't know whether the process is to simply select by bit address, but I spent 5 queries just accessing all the bits, and it was not conclusive.

* 1,3,5,7 ON, count 2

* 2,3,6,7 ON, count 3

* 4,5,6,7 ON, count 2

There are still 4 sets of three numbers each that agree with these queries:

750, 741, 543, 651

Clearly, I don't grok the method. Accessing all the bit planes seems like it would be valuable, but I'm in agreement that it seems impossible to find them all in just 6. I look forward eagerly to the 6-solution!

It'll be a cold day in hell when I can one-up CaptainEd. Anyways, I made a mistake earlier when computing the possible number of ways to distribute 3 right switches among 32. For some reason, I entered Combination( 15,3) into my computer. Don't ask where the mental disconnect comes in. Anyways, I'm revising the estimate. 9 turns, and possibly even 8, is required to solve part I.

[Guest]

It'll be a cold day in hell when I can one-up CaptainEd. Anyways, I made a mistake earlier when computing the possible number of ways to distribute 3 right switches among 32. For some reason, I entered Combination( 15,3) into my computer. Don't ask where the mental disconnect comes in. Anyways, I'm revising the estimate. 9 turns, and possibly even 8, is required to solve part I.

I thought so too....IIRC, in order to correct 3 bits, you have a minimum hamming distance of 7. In problem I's case, we need one more flip to make them all on (instead of correcting to on we'll be correcting to "off" and reversing the value). Although, after thinking about it, you could incorporate the knowledge gained about the last switch from the first flip into one of the other flips...

e.g:

First flip, flip all but last switch. If result > 29 - you know that you don't need to flip the last switch any more, it was already on, so you know the first 31 switches had 2 on. Otherwise, the result < 29, so you know that the last swtich needed to be flipped, so you are looking for 3 lights in the first 31 switches. Your next flip should incorporate that last flip if needed.

I'm thinking now that the rest of the flips should be some sort of hamming pattern (i.e. flip swtiches 15-31...etc) and find out how many of the lights are lit on each flip. There's going to be at least 5 more flips (one for each bit pattern) plus one more flip to get to the final code...So regardless, our minimum bound is 7, maybe 8 flips...

I don't quite know what the pattern should be, I really don't have time to work it out (since i just looked this over at lunch).

[Guest]

captian ed, i think you mean...

1) 0-15 ON, 13 response. so you know all three bulbs are in the 16.

2) 8-15 OFF, 5 response. so you know that the three bulbs are in 0-7.

you have 8 lights and four turns to know which the three are the original.

first turn OFF 4 lights. there are three possibilities, either you get:

...case 1: you get 1 light or 7 lights, then all three bulbs are in one or other group, and solving is fairly simple.

...case 2: you get 5 lights. then two is in the group you turned off, and one light is in the other group.

...case 3: you get 3 lights. then 1 is in the group you turned off and the other has 2.

since case 2 and 3 are essentially the same, lets label the 2 bulb group A and the 1 bulb group B, for clarity sake, i'll assume case 3.

you have three turns left.

flip 2 bulbs in group A, and 1 in group B.

here you have four cases.

case 1: 0 lights. you turned off the original light in group B, and both of the non original ones in group A. done.

case 2: 2 lights. you turned off two of the non original bulbs in group A, and turn on one of the non original in group B. so you know two of the bulbs, and have two turns left to find the third bulb out of three.

case 3: 4 lights. you either turned on both original bulbs in group A, and off the original light in group B, or turn on one light off one light in group A, and on one non original light in group B.

case 4: 6 lights. you turned on both original lights in group A, and one of the non original ones in group B. once again you can find the third bulb fairly straight forwardly.

obviously case 3 will be the hardest.

do you see a way to solve case 3 in 2 turns?