An interesting wire-tying problem to match wire ends in as few trips as possible

Question

You have $N$ wires that all extend from one location to a second distant location. The wire ends at both locations are unlabeled, and the goal is to label them all (on both ends) with distinct labels $1,2,\ldots, N$ so that the two ends of the same wire have the same label for every wire. I.e., the goal is to match every pair of wire ends.

The operations you can perform (on either end) are as follows: You can tie or untie any subset of wires together, and you can use a connectivity detector to tell if two wires are tied together on the other end. While on one of the two locations of wire ends, you can tie, untie, and test connectivity as much as you want. However, the goal is to minimize the number of trips between the two locations so that you can guarantee that you can label all the wire ends.

It seems like perhaps considering the case of even $N$ and odd $N$ separately may be a good idea, but still, is there an easy-to-describe strategy to minimize the number of trips? And prove the solution is optimal? If it helps, especially to prove optimality, we might assume that you only tie/untie wires at the starting location, and only test connectivity at the second location.

Answer 1

I have found a provably optimal solution for odd $N$ if we assume that you can only test connectivity at the second location, and only tie/untie at the first location. First label the wires $1$ to $N$ at the first location.

Then tie together wires in pairs in consecutive order, i.e. $(1,2)$,$(3,4)$, and so on, and leave wire $N$ untied. Then travel to the second location and determine all pairs of wires that are connected, by testing all pairs, and also likewise determine the wire $N$ that isn't tied to anything.

Then travel back, untie everything, and now tie together in consecutive pairs $(2,3)$,$(4,5)$, etc., up to $(N-1,N)$, leaving wire 1 untied. Travel to the second location and determine all pairs that are connected along with the wire 1 that isn't tied to anything.

Now, we know which wire is wire 1, but then by the first round of tying we know which wire is wire 2, and then by the second round of tying we know which wire is wire 3, and then by the first round of tying we know which wire is wire 4, etc. And clearly you have to tie wires and test connectivity at least twice, so this solution is optimal, at least when you can only tie at the first location and test at the second location.

However in terms of one-way trips, this takes 3 trips and if we are allowed to tie wires at the 2nd location and test connectivity at the first location I can't prove that we can't do it all in 2 one-way trips.

Also, I don't have a similar solution for even $N$ unless we use 5 one-way trips, and I think it's probably possible to get it down to 3 one-way trips for even $N$ too.

Answer 2

For $N=1$ You need no trips. For $N=2$ the operations are not enough to solve the problem in any way. For $N\geq3$, at least two one-way trips are necessary, because in the first trip, you can't distinguish a wire from the one(s) connected to it without separating them later. It can be shown that two one-way trips are sufficient to identify all the wire ends (but if you really need to "label" the wire ends, it's sufficient to travel once more, similar to $N=1$. It's easy to see that this "extra" trip is necessary too).

Let's first assume that $N$ is odd. Label the wires $1$ to $N$ at the first location. tie together wires in pairs: $(2,3),(4,5),\dots$. Travel to the other side. Determine all the pairs (call them twins) and identify wire $1$. Tie wire $1$ and another wire (call it $a$) together, Tie $a$'s twin and another wire (call it $b$) together, Tie $b$'s twin and another wire together, and so on. Travel back and separate the tied pairs. Check which wire is connected to wire $1$, that would be $a$; Then $a$'s twin is identified and $b$ will be the one connected to it, and so on.

Now assume that $N$ is even. Tie together wires in pairs: $(2,3),(4,5),\dots$, so wires $1$ and $N$ are not connected to any other wire. Travel to the other side. Determine all pairs and the two lonely ones. Let one of the lonely ones alone again and use the other one in the same way as the odd case. Travel back and identify the wire that was alone in both trips, and then identify the other wires similar to the odd case.

Answer 3

This can be done in $\log_2n$ trips.

When you start out you label one of the wires $1$ and tie the other $n-1$ wires together. Go to the other side and label the unconnected wire $1$ and choose another wire and label it $2$. Tie this wire to wire $1$. Go back to the first side and untie all wires and test for connectivity. You'll now have wires $1$ and $2$.

Since you have two wires, you can tie one remaining wire to $1$ and label it $3$ and tie another wire to $2$ and label it $4$. Proceed to the other side and untie all wires. Testing for connectivity will give you $3$ and $4$.

Having labeled wires $1 .. k$, tie an unlabeled wire to $1$ and label it $k+1$, a wire to $2$ labeled $k+2$ up to a wire tied to $k$ labeled $2k$. Go to the other side, untie all wires and test for connectivity. You now have $2k$ wires labeled.

Since you double the number of wires you label on each trip, you label all wires in $\log_2n$ trips.

Answer 4

Tie cables in bunches of 1, 2, 3, 4,.....n i.e. greatest n such that (Z =) N - n(n+1)/2 >n and in the first trip itself Z is known

Now treating Z as the new N, repeat the above steps...

After a few recursions, the no. of steps would dramatically come very little i.e.

For N = 3,4,5,6,7,8,9,10 its respectively 2,3,3,3,4,4,4,5 For N = 100, its 6 only