Nov 10, 2009

Bulbs-Switches matching problem

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.

2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Number the switches from 1 to 1000. Thus, each switch is also represented by a 10 digit binary number.
    1 : 0000000001
    2 : 0000000010
    .
    .
    .
    1000 : 1111101000
    Now, stick a piece of paper to each bulb.
    Switch on only those switches who have 1 as their most significant bit.
    Now, go into the room and write 1 on the paper for all the bulbs that are on and write 0 for all the bulbs that are off.
    Repeat this from the most significant bit to the least significant bit, i.e. 10 trys in total.
    The paper attached to each bulb will tell its switch number in binary. Eg, a paper with 0000000100, will correspond to switch 4.

    ReplyDelete