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

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.


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.