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.

The problem asks for both a minimum and maximum number of trials. Let's start with the minimum, which is also the "best case".

If I get very lucky and pick on each trial the two switches that correspond to the same light, then in each trial I will definitively know the functions of two more switches. After nine trials, I'll know all of the switches since the last one on each side can be found by process of elimination. So I believe 9 trials is the minium -- no strategy can discover information faster than 2 switches per trial.

Now imagine a sequence of two trials: 1A + 1B and 2A + 1B (where "1A" means the first switch on the "A" side and so on.) Since 1A and 2A can't operate the same light (both being on the A side), the patterns of lights must be different for these two trials. There are two possibilities: one trial has no lights lit or both trials have a common light lit that corresponds to 1B. Either way, after these trials we definitively know all three switchs' corresponding lights. If there's a "no light" then 1B operates the same light as one of the A's and the other is the second light in the other trial. If both trials show lights then 1B is the light in common, and the A lights are the other ones in each trial.

We can use this strategy a total of 6 times (12 trials) to learn the operation of 18 switches. If we alternate which side (A or B) gets the repeated switch in each of the 6 double-trials, then these 18 switches will be split 9 each on A and B. Since there are only 10 switches on each side, we'll then know the 10th on each side by process of elimination. Thus, it's always possible to determine all of the switch-light associations with 12 trials, which is the maximum.

Note that in the "real world", this strategy may be slightly improved if the first trial in a pair gives no lights at all. Since this determines two switches outright, it's better to mark those and start a NEW pair. If this should happen enough times, then the 10th through 12th trials may be all or partly unnecessary. Also, we can make increasingly more intelligent judgments about which switch is which. For example, it may be that of the two lights turned on in a trial, one switch has already been found that controls one of these lights. In this case, the trial is equivalent to a "no lights" in that we learn the identity of both switches in one trial -- and we approach the ideal minimum of 9 trials needed.

Posted by Paul on 2009-01-12 19:05:12