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.
|
|
Submitted by Praneeth
|
|
Rating: 4.0000 (2 votes)
|
|
|
Solution:
|
(Hide)
|
Minimum no. of trials: 10
Maximum no. of trials: 14
Best Case:
Number the bulbs from 1 to 10.
Consider the following scenario:
If you are lucky to turn ON the switches corresponding to bulbs as following:
TrialNumber Room1 Room2
1 1 2
2 2 3
3 3 4
4 4 5
5 5 6
6 6 7
7 7 8
8 8 9
9 9 10
Now you don't need to test turn ON the last two switches corresponding to bulbs 1 and 10.
trial10 =>9 1
The switch you turned ON, which is OUTSIDE room1 in the last 2 trials correspond to bulb 9.
The switch you turned ON, which is OUTSIDE room2 in the last trial correspond to bulb 1.
Now you can find all the bulbs if you follow each trial in the reverse as they all linked to each other.
Worst Case:
Let the switches outside rooom1 be A1,A2,....,A10 and those outside room2 be B1,B2,...,B10.
trial1 => A1 B1
The worst case is that they correspond to the same bulb.
trial2 => A1 B2
trial3 => A1 B3
After these trials, you can successfully find bulbs corresponding to A1,B1,B2 and B3.
In 3 trials, you can find label 4 switches.
to label 20(=4*5), you need 15(=3*5) trials??
No, we need only 14 trials.
label 16 switches using above method.
So, we need 4*3 = 12 trials.
To label last 4 switches {let them be A9 A10 B9 B10} and these switches correspond to only 2 bulbs (one in room1 and the other in room2)
trial13 A9 B9
Case(1): They correspond to the same bulb
so, A10 B10 correspond to same bulb
Case(2): They correspond to different bulbs
trial14 A9 B8
B8 is already known, you will find A9
and B9 as well as A10 and B10
So, 14 trials are enough. |
