Tangled wires

This Riddler puzzle is about tangled wires. Can you figure out how to untangle them?

There are N wires leading from the top of a bell tower down to the ground floor. But as wires tend to do, these have become hopelessly tangled. Good thing the wires on the top floor are all labeled, from 1 to N. The wires on the bottom, however, are not. (In retrospect, somebody probably should have anticipated a tangle or two.)

You need to figure out which ground-floor wire’s end corresponds to which top-floor wire’s end. (The bulk of the wiring is hidden behind a wall, so you can’t simply untangle them.) On the ground floor, you can tie two wire ends together, and you can tie as many of these pairs as you like. You can then walk to the top floor and use a circuit detector to check whether any two of the wires at the top of the tower are connected or not. What is the smallest number of trips to the top of the tower you need to take in order to correctly label all the wires on the bottom?

Here is my solution.
[Show Solution]

6 thoughts on “Tangled wires”

  1. I like your explanation, but it could benefit from pointing out one thing:
    Another way of thinking about why two trips is enough is to count the total amount of information you obtain in a single measurement. For N=2M+1 odd, this is
    N(N-2)(N-4)..1 = N!/(2^M M!)
    (N for the number of possible unmatched wires; (N-2) for the number which might connect to the first matched wire, (N-4) for …)
    which is smaller than N!, the total amount of information we need, but larger than Sqrt[N!] and therefore two trips could be enough if we do things cleverly.
    For N=2M even, the information if we connect all wires would be the number of ways of pairing N objects, which is
    (N-1)(N-3)…1 which is too little to solve the problem in 2 tries.
    But by leaving two wires unconnected, there is one pair which is special — the pair of unmatched wires — giving us an extra factor of (N/2). Then the number of possibilities is more than Sqrt[N!] and two trips could be enough if we are clever.

    1. Just one other way to look at the problem:
      Think of the ends on the bottom as vertices of a graph (empty in the beginning), but you don’t know their labels yet. For each trip to the top you can add arbitrary disjoint edges to your graph that all have a single new color. If your edge-colored graph now only has one (color preserving) isomorphism (the identity) then all vertices are found/can be labeled uniquely. In other words: you are looking for a properly edge-colored graph on N vertices that uses as few colors as possible while only having one isomorphism. The obvious solution is to take a path with all (or all but one if N even) vertices with edges colored 1 and 2 alternatingly + a single vertex if N even. This directly corresponds to the wirings you have described above.

  2. I think it can be done in only one trip. The method is to pair and connect all but one wire if n is odd or two if n is even on the ground floor. Then when you go upstairs you have at least one wire to start that does not complete a circuit with any other wire. Call that f(1). Pair with any wire. Call it f(2). It completes a circuit via the downstairs pairing with a third wire. Call it f(3). Pair f(3) with any other wire. Call it f(4). Etc. The process will end at f(n) if n is odd and f(n-1) if n is even. In the latter case pair it with the second wire that did not complete a circuit which. Call that wire f(n). Now connect all the paired wires.
    Return to the ground floor. Disconnect the pairs of wires but keep them paired. For example the members of pair could be colored the same color but each pair’s color would be different. The original unconnected wire which now completes a circuit should be labeled 1. Call the wire that completes a circuit with it, 2. Call the wire paired with 2 (with the same color as 2), 3. Call the wire that completes the circuit with 3, 4. Etc.
    In this way we have created a permutation f from the now numbered wires on the ground floor, to the wires on the top.

    1. This solution works, but you are making assumptions that were not part of the original problem specification. The problem says that you may connect wires at the bottom and test connectivity at the top. It does not say that wires may be connected at the top or that connectivity may be tested at the bottom. Moreover, when you’re done and you return to the bottom, you’ve left wires connected at the top, which may be undesirable.

      It’s a nice solution, but I think you’re solving a (slightly) different problem!

      1. Laurent, thanks for trying to explain O. R. ‘s reasoning. However, the problem as originally stated (not as rewritten a week later) doesn’t say you can connect wires only at the bottom or test for complete circuits only at the top; it just gives them as examples of what is possible and easy to do. And it says nothing about leaving the wires unconnected when done.

        I think that if O. R. uses these legalistic sounding excuses rather than just admitting he made a mistake in his solution or in stating the problem, then he is just being defensive which is understandable but unfortunate. In any case I enjoy trying the problems and they give me ideas for other problems.

        For example, suppose there are three locations with two tangled wires going between each pair of locations. Thus we have four wire ends at each location but we don’t know which wires in one location go to which wires in the other locations; we don’t even know which locations they go to. What is the smallest number of trips between locations to untangle the wires by using connections or testing circuit completions within a location, if it can be done at all.

Leave a Reply

Your email address will not be published.