A Wired Mess
A cable consisting of 10 wires has been laid underground between two telephone exchanges located 10km apart. Unfortunately, after the cable has been laid, it was discovered that the individual wires were not labelled, and so it was impossible to tell which connections were linked up to each other.
You are assigned to identify and label the wires, without disturbing the laid cable. Your objective is to label the individual wires with the same label at both ends. You have 100 short wires, a device that tells you if a wire circuit is complete, and writing materials to label the wires.
What is the shortest distance (in km) that you will need to walk in order to correctly identify and label each wire?
(Assume that your starting position is at one of the telephone exchanges.)
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
There are many ways to do it in just 20 km, or 2 trips from one end to the other. Here is the relatively straightforward way I thought of to do it:
-At your starting station, wire together three groups. There should be a group with two wires, one with three, and one with four. Label the pair A, the triple C, and the quadruple E.
-Walk to the other end, and begin testing which wires form circuits. Once you have grouped them, label them as they were labeled at the other end.
-Regroup them as follows:
-taking a wire from A, one from C, one from E, and the unlabeled wire, wire a quadruple. Label these F.
-taking the other from A, another from C, and another from E, wire a triple and label it D.
-taking the last from C and another from E, form a pair and call it B.
-Now, return to the first station, remove the connections at this end, and test for circuits again.
-Once you have established the new groupings, label these as you labeled the other ends. You now have ten wires, labeled AD, AF, CB, CD, CF, EB, ED, EF, E, and F at both ends. Since all these labels are distinct, you are done.
To be thorough, we must also show that 10 km, or one trip, is insufficient. An informal proof of this follows.
To get any information out of a trip, you must set up the other end so that it is possible to form circuits. Any circuit of this sort necessarily involves at least two of the ten wires. When you go to the other end, the best you can do is identify which ones are in that pair, but you have no way to tell them apart. So, at least a second trip is necessary.