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.
Looks like the problem boils down to the problem of finding the worst case scenario. The rest can be figured out by hand-tracing and some common sense (which can be a serious issue with me... but that's my personal thing!).
I think the worst case scenario would be whatever strategy we chose, wherever possible, for each trial both the switches correspond to the same bulb and hence requiring further trial(s) to identify those two switches according to which bulb they belong to.
As an example, consider the following. My strategy is to go for AS1 (room A's 1st switch) + BS1 in the first turn. If two different bulbs light up then I will continue with AS2 + BS2 as the second turn. Again if two bulbs light up I will continue with AS3 + BS3 as third turn and so on.
However, if in i-th turn (i.e. ASi +BSi) no bulb is lit then I will go for ASi + BS(i+1) as (i+1)-th turn. Here i is sufficiently far from 10 (total number of switches for one room) so that it is not possible to identify the remaining switches by elimination.
The worst case for this strategy will be that every pair of switches I use for each trial will correspond to the same bulb. Thus when I start with AS1+BS1, both correspond to a single bulb. Therefore I go for AS1+BS2 in the next trial. This will give me which bulb AS1, BS1 and BS2 belong to. So now the third trial will be AS2+BS3. Again if no bulb lights up in this trial (meaning AS2 and BS3 correspond to the same bulb) I will go AS2+BS4. This trial will yield AS2, BS3 and BS4.
If however, on the third trial in the above paragraph (i.e. AS2+BS3), two bulbs light up then I know AS2 and BS3. Hence my fourth trial will be AS3+BS4.
Edited on January 16, 2009, 5:39 am
Edited on January 17, 2009, 1:20 am
Worst case scenario (part 1)
