The Wire Identification Problem

There is a bunch of 120 electrical cables laid under the ground. The cables are 10 KM in length and both ends of each wire are out in open.




We need to identify and label the cables 1-120. All you have is a circuit completion detector bulb.(i.e. if you join same side ends of any two cables and then on the other side apply the bulb to corresponding 2 ends then bulb will light up, but to detect this way you have to make a 10 KM trip)

How would you identify each cable in minimum number of trips.

Solution

We need to identify and label the cables 1-120. As you might have guessed, the only way to gain information in this setup is to connect some set of wires at one end, walk up to the other end, and test for conductivity. The process may have to be repeated many times before a complete labeling can be constructed. And since each such step involves walking across 10 KM, we wish to solve the problem with the least number of trips.

How would you identify each cable in minimum number of trips?

Answer:
Boundary Condition: If we have just 2 wires, there’s really nothing we can use to break the symmetry of the situation.

Solution: At the first end, connect pairs of wires together, leaving two wires unconnected. Go to the other end. Find a pair of connected wires, andnumber them #2 and #3. Find another pair and label them #4 and #5. Repeat for all of the pairs, with the last pair labeled #118 and #119. There remain two wires that are not connected to each other. Label one of these #1 and the other #120.

Now at second end, connect #1 to #2, #3 to #4, etc, leaving #119 and 120 unconnected. Go back to the first end. One of the originally unconnected wires still is unconnected. Label it #120 and label the other originally connected wire #1. Now find the wire connected to #1 and label it #2. The wire that originally was connected with new wire #2 can be labeled #3. The wire that is now connected to the newly labeled #3 is #4. In this way, all of the wires can be identified on both ends in two trips (one round trip). If it is necessary to disconnect the connections at the other end, a third trip is necessary.

Below is an execution diagram for 6 wires. We have to label wires from 1-6.





Source

http://ashutoshmehra.net/blog/2009/09/wire-identification-problem/