Question: 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. 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, and number 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.

This solution can be extended to any number of wires greater than 2.

PS: Think about the solution is wires are already labeled at one end.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.