Fog Creek Software
Discussion Board




puzzle with bulbs!

question:
There are 1000 bulbs in a room & the switches for these are in another room arranged in a random fashion.You have to find an optimum strategy to match the bulbs to corresponding switches so that the number of times u enter into the room to look at the bulbs is minimum.

let me know if somebody finds this!

vijayakumar b
Sunday, January 04, 2004

Strategy: Turn ON first 500 switches and turn OFF next 500. Go to the room and note down the state of bulbs. We know which 500 switches correspond to which 500 bulbs.

Now the problem gets divided into *two* smaller problems of finding bulb-switch mapping for 500 bulbs.
Apply the same strategy for 500 bulb-problem as for 1000 bulb-problem.

Note that we are dividing the original problem into smaller ones and solving them in parallel, i.e. on each visit, we are proceeding on all the sub-problems.
(This strategy is known as Divide-and-Conquer in computer science text books).

Mathematically,
Let T(n) = Number of times one has to enter into room to look at the bulbs.
We want to find out T(1000).

  T(n) = T(n/2) + 1 (Since we reduced the problem of size n into two sub-problems of size n/2 which will be solved in parallel and it took us one visit to do so)
      = {T(n/4) + 1} + 1 = T(n/4) + 2
      = T(n/8) + 3
      ...
      = T(n/2^(k-1)) + (k-1)
      where  k = log n (base 2)
      and T(2) = 1
  So,
  T(n) = T(2) + (k-1)
      = 1 + (k-1)
      = k
      = log n (base 2)
  T(1000) = 10

VikasRana
Thursday, January 08, 2004

I dont know how log n (base 2) is going to work. If there are say 4 lights A B C D corresponding to switches 1 2 3 4, then if we want to establish which switch corresponds to which light, we need (n-1) visits, which is 3 for the above case.

Lets say that A B C D are the bulbs and 1 2 3 4 are switches corresponding to them(in no particular order). First we switch on two and switch off the other two bulbs. So, say A B are switched on and C D are switched off. Then, we visit the room to figure out that A B(or C D or A C or B C)  are 1 2 lights are switched on(say). Now, from our first visit, we are able to establish that A B correspond to 1 2 (may or maynot be respectively). Now, we turn on A(or B) and turn off B(or A), and then we establish which switch(1 or 2) corresponds with which light ( A or B). We repeat the process for 3 and 4 bulbs.,

Now, if we have 8 bulbs, we need a visit to figure out which half of bulbs(4) correspond to which switches. Then, out of 4 bulbs, we need one more visit to figure out which 2 bulbs correspond to which switches, and then finally one more visit to associate one bulb to one switch(total being 3 visits). Then we repeat this process for the second half of 4 bulbs and need 1 more visit to figure out that. Simialarly for the other half(4 bulbs).

A total of (n-1) 8-1=7 visits.

Naveen
Thursday, January 08, 2004


Sorry, my mistake - I know I don't write great; I should have explained it with an example.

4 bulbs example
---------------

Lets say that A B C D are the bulbs and 1 2 3 4 are switches (in no particular order).

First, switch ON 1 & 2 and switch OFF 3 & 4.

1: ON
2: ON
3: OFF
4: OFF

Then, visit the room (visit #1) to find out

A: ON
B: ON
C: OFF
D: OFF

From this we infer

1,2  ==> A,B
3,4  ==> C,D

Now, we change the state of switches

1: ON
2: OFF
3: ON
4: OFF

Then, visit the room again (visit #2) to find out

A: OFF
B: ON
C: ON
D: OFF

From this we infer

1  ==> B
2  ==> A
3  ==> C
4  ==> D

Total Number of visits = 2 = log 4 (base 2)

Note that the key to the solution is fact that we are working on the sub-problems in parallel - When we visit second time, we are not only progressing on first sub-problem but also on the second sub-problem.

8-bulb problem can be worked on similar lines.
(On the first visit, we can reduce it into two 4-bulb problem which can be solved in 2 visits as described above. So total visits = 3)

VikasRana
Friday, January 09, 2004

The above answer is correct. but,i have another answer which i think would be practically more possible than the above which include more parallel processing.my answer:
number the switches with binary numbers- u need 10 bits for 1023 bulbs. now, switch on all the switches with 1st bit as '1'. visit the room and mark '1' for the 1st bit in  the bulbs that are glowing. continue for all the 10 bit's. and u can match all the switches with corresponding bulbs.
this is similar to the problem of king with 1000 bottles of wine, one containing poison.

waiting for comments and more puzzles...
vijay.

vijayakumar b
Saturday, January 10, 2004

It reminds me a puzzle. You got 3 light bulbs in a room and 3 switches outside the room. You can exit the room and re-enter once. How can you match up the switches to the bulbs.

I suppose if you know the trick for the above puzzle, then you can optimize your answer even more. 

Just a thought.

May Bee
Saturday, January 10, 2004

this one works on the heat energy . tweaking it to the bulbs that are not reachable makes the problem same as above.

lovey

lovey
Friday, February 06, 2004

*  Recent Topics

*  Fog Creek Home