Technician from IIT
This puzzle was asked to me last year by Manish Agarwal. He said that the answer was 20km.
A 120 wire cable has been laid firmly underground between two telephone exchanges located 10km apart.
Unfortunately after the cable was laid it was discovered to be the wrong type, the problem is the individual wires are not labeled. There is no visual way of knowing which wire is which and thus connections at either end is not immediately possible.
You are a trainee technician and your boss has asked you to identify and label the wires at both ends without ripping it all up. You have no transport and only a battery and light bulb to test continuity. You do have tape and pen for labeling the wires.
What is the shortest distance in kilometers you will need to walk to correctly identify and label each wire?
Update (11/12/09) : Solution posted in comments!
A 120 wire cable has been laid firmly underground between two telephone exchanges located 10km apart.
Unfortunately after the cable was laid it was discovered to be the wrong type, the problem is the individual wires are not labeled. There is no visual way of knowing which wire is which and thus connections at either end is not immediately possible.
You are a trainee technician and your boss has asked you to identify and label the wires at both ends without ripping it all up. You have no transport and only a battery and light bulb to test continuity. You do have tape and pen for labeling the wires.
What is the shortest distance in kilometers you will need to walk to correctly identify and label each wire?
Update (11/12/09) : Solution posted in comments!
I have explained solution of this problem on gtalk to 2 people now. I don't want to do it again, hence posting the solution.
ReplyDeleteNote that 120 = k(k+1)/2
We can divide cables into groups of 1, 2, 3 …., k
In every group, all cables belonging to that group is shorted.
Now, we go down (first trip). Clearly, we will be able to identify different groups because for cables belonging to group i, continuity meter will show them connected with exactly i-1 other cables.
So we have determined following groups, 1, 2 , ... , k.
Now, we take one cable from each group (1_1, 2_1, 3_1, .. k_1) and short them. First group will be of size k, let us call the group as k’.
Similarly, second group will be of size k-1 ( because group 1 had only one cable, which was consumed in forming group k’)
The last group will have size 1.
Now we go up (second trip). Original group of size 1 was determined in the first trip itself. For group 2, if a cable is connected to k-1 other cables then it is 2_1, if it is connected to k-2 other cables then it is 2_2. Similarly we can identify every wire in every group.
:)
Hello Pratik, I am not getting exactly.
DeleteSlightly different way of solving it assuming we can identify the polarity of the wires using the bulb.
ReplyDeleteShort the wires into 2 groups of 60 each.
Connect each of the group to the two terminals of the battery.
Now, on the other side, we can identify the positive and negative groups by connecting the bulb to each pair of wires.
Now, number the positive wires from 1 to 60 and the negative from 61 to 120.
Short 1 to 120; 2 to 120, 119; 3 to 120, 119, 118 and so on.
Now, on the first side, if we unshort the two groups, then first positive wire is the one which is connected to exactly 1 negative wire, 2nd positive wire to 2 negative wires etc.
Similarly 120th negative wire is connected to 60 positive wires, 119th to 59 etc.