There are two rooms A and B which are not connected and whose entrances are closed. Each of the rooms has 5 bulbs inside the room and 10 switches outside the room corresponding to bulbs of both the rooms.

Schematic of Rooms A and B
* * * * * A D • • • • • • • • • •	* * * * * B D • • • • • • • • • •
lights, switches and doors.

Two switches are ON corresponding to separate bulbs.

The entrances will stay opened if and only if exactly one of the switches outside A and one of the switches outside B are ON. If both the switches that are turned ON correspond to the same bulb then the bulb will be OFF.

You are asked to find the bulbs corresponding to each of the switches outside rooms A and B. Using optimal methods, find the minimum and maximum number of trials required to complete the task.

Note: A trial is defined as turning one of the switches outside A and one of the switches outside B ON and checking the bulbs in the rooms A and B. There is no way to find which bulbs are ON from outside the rooms. The bulbs are at a reasonable height so that you can't touch any of them. The same number switch in each room may not correspond to the same bulb.

Assuming that each bulb has at least one switch, consider following sequence of trials. [AS1 means 1st switch for room A.]

Trial No           Trial                Status of Knowns             

1                   AS1+BS1             0 (because both switches belong
                                                to same bulb)

2                   AS1+BS2               0
3                  AS1+BS3                0
.                     .                           .
.                     .                           .
.                     .                           .
10                 AS1+BS10              0
*11               AS2+BS1                AS1, AS2, BS1-BS10
12                 AS3+BS1               AS3
13                 AS4+BS1               AS4
.                     .                           .
.                     .                           .
.                     .                           .
18                AS9+BS1               AS9, AS10

* After 10 trials we know that BS1 to BS10 correspond to the same bulb and AS1 also corresponds to that bulb. If each bulb has at least one switch then we know that switches AS2-AS10 all correspond to 9 different bulbs. So from trial 11 onwards we will always find out the bulb of each A switch.

At 18th trial we know AS10 by elimination.

But now as I am typing in, it looks as if the worst case might be that all the 20 switches belong to the same bulb and the other 9 bulbs don't have any switch. In that case it will be impossible to find out which switch corresponds to which bulb!

Still working...

Posted by elementofsurprize on 2009-01-17 09:25:46