Number of travels required to find corresponding wire beginnings and endings using certain actions

Question

A professor of mine gave us a problem to think about during the holidays if we want to and I'm not sure about the right approach to solve it.

The problem is the following: We have N wires (1 ≤ N ≤ 10^6) which are going from point A to point B but it is not known which wire ending corresponds to which wire beginning. There are three ways to figure this out:

• Travel between point A and B
• Connect wires. (This means that you take a subset of wires and connect them so you can use their endings as one single ending)
• Test if wires are connected. (you can imagine this as power cables: e.g. if some wires are connected at point A and you power one of these connected cables at point B you can see which cables are connected because they will also be powered)

The goal is to calculate the minimal number of required travels between A and B.

E.g. for 3 wires we need 2 travels: We connect two wires and call the third one A. Then we travel to the other point and test which wire is not connected to any of the other two wires. This must then be wire A. Then we connect A with another wire, call it B and travel back. Now we have to find the cable which is connected to A, this must be B and the third one must be C.

Unfortunately for some N it is not possible to figure out which wire is which, e.g. for N = 2. (I'm pretty sure N = 2 is the only one). N = 1 means zero travels.

Any advice on how to cope with this problem is very much appreciated.

Answer 1

So happened I have solved similar puzzle before.

For N > 2, you can always identify the wires by 2 travels.

---

For odd number of wire (I use 5 as example)

A  B  C  D  E
|  |  |  |  |

|  |  |  |  |
1  2  3  4  5

(Assuming you are on the "number" side now)

First connect wire like this:

A  B  C  D  E
|  |  |  |  |

|__|  |__|  |
1  2  3  4  5

Then travel to the "Alphabet" side. There should be one wire you will find that is not connected to any other end (test by conductivity with other ends). Assume that's A. Then you know A corresponds to 5

Then find pairs of end that are connected. Assume you find B-C, and D-E are connected. Then connect A-B, C-D. This will give you one long wire which travels from 5 to E.

A__B  C__D  E
|  |  |  |  |
\__________    
           \
|__|  |__|  |
1  2  3  4  5

Go back to the "Number" side. Disconnect all on this side

A__B  C__D  E
|  |  |  |  |
\__________    
           \
|  |  |  |  |
1  2  3  4  5

Then test which wire conducts with 5. Assume it is 3, then you know 3 corresponds to B. Given 3-4 was originally connected and B-C was a pair, you know 4 corresponds to C. Connect 3-4 again.

A__B  C__D  E
|  |  |  |  |
\___\__\___    
     \  \  \
|  |  |__|  |
1  2  3  4  5

See which of 1 or 2 conduct with 5, then you know which corresponds to D, and hence the other for E.

You can use this approach to identify whatever number of odd wires.

---

For Even number of wire, it is similar to odd number:

Step 1, do the same thing, but leave 2 wire unconnected

A  B  C  D  E  F
|  |  |  |  |  |

|__|  |__|  |  |
1  2  3  4  5  6

Travel to Alphabet side, this time, you should find 2 wires not conducting to any other wire (assuming A and F). Leave one of them untouched (assuming F). Connect A to E as described in odd-number method.

Go back to Number side. You will find one of 5 or 6 is not conducting with any other wire (Assume 6), you know it corresponds to F.

A__B  C__D  E  F
|  |  |  |  |  |
\__________    |
           \   |
|__|  |__|  |  |
1  2  3  4  5  6

So, you identified 6-F, and 5-A. The rest is simply the odd-number case described above.

---

And yes, for N = 2, there seems to be no way to identify them unless you are allowed to bring 1 more wire, or at least, a diode with you :P