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 best case would be that with each trial we find 2 switches, i.e. in each trial the two switches correspond to two different bulbs.
Consider the following strategy (same to the one discussed in previous two posts on Worst case scenario).
Trial No Trial Status of Knowns 1 AS1+BS1 AS1,BS1
2 AS2+BS2 AS2,BS2
3 AS3+BS3 AS3,BS3
. . .
. . .
. . .
10 AS10+BS10 AS10, BS10
This can happen when for example each switch for room A corresponds some bulb in room A only. Same for switches in room B. Also each bulb has at least one switch associated.
The minimum number of trials required is 10 here.
Best case scenario
