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?
It’s impossible to untangle the wires when $N=2$ because the circuit detector can’t tell us whether the wires are crossed or not. So at first glance, it may seem like this puzzle is unsolvable. Surely it can’t get easier as we add more wires, can it?
It can! In fact, for any $N \ge 3$, the wires can be untangled using exactly two trips. I will illustrate the solution via an example. Let’s assume $N$ is odd, and take the case $N=7$ with the wires tangled as shown below. Label the wires $\{1,2,\dots,7\}$ at the top and $\{A,B,\dots,G\}$ at the bottom.
On our first trip, we connect the wires in pairs as shown in purple. On our second trip, we connect the wires in pairs again, but shifted by one, as shown in dark blue. Here are the lists of connected pairs observed at the top of the tower when we use the circuit detector.
\begin{align}
\text{First trip:}&\quad\{(A,B), (C,D), (E,F)\}\mapsto\{(2,4),(1,6),(5,7)\} \\
\text{Second trip:}&\quad\{(B,C), (D,E), (F,G)\}\mapsto\{(4,6),(1,5),(3,7)\}
\end{align}Of course, we don’t know which pairs correspond to which wires. Consider the results of the first trip, for example. We know that $(A,B)$ corresponds to $(2,4)$ or $(1,6)$ or $(5,7)$, but not which one. Even if we knew that $(A,B)$ corresponded to $(2,4)$, we wouldn’t know whether $A=2$ and $B=4$ or vice versa. Nevertheless, the information we learned is useful because if we knew for example that $E=6$, then we could deduce that $F=1$ because $E$ and $F$ are connected and $1$ and $6$ form a pair.
In both trips combined, every wire was connected twice except $A$ and $G$, which were each connected once. Examining occurrences of numbers in both lists above, we see that $2$ and $3$ only appear once. These numbers therefore correspond to $A$ and $G$ in some order. We connected $A$ in our first trip, and this is the list where $2$ occurs, therefore $A = 2$. We can reconstruct the entire pattern by following the links:
- $A=2$ and $(2,4)$ is in the first list, where we used $(A,B)$. So $B=4$.
- $B=4$ and $(4,6)$ is in the second list, where we used $(B,C)$. So $C=6$.
- $C=6$ and $(1,6)$ is in the first list, where we used $(C,D)$. So $D=1$.
- $D=1$ and $(1,5)$ is in the second list, where we used $(D,E)$. So $E=5$.
- $E=5$ and $(5,7)$ is in the first list, where we used $(E,F)$. So $F=7$.
- $F=7$ and $(3,7)$ is in the second list, where we used $(F,G)$. So $G=3$.
This reconstruction works because the two endpoints $A$ and $G$ are visited on separate trips, and it’s clear how we would extend this to the case where $N$ is any odd number. If $N$ is even, the two endpoints will be visited on the same trip and we won’t be able to distinguish them. To remedy this situation, simply leave one wire unconnected and follow the procedure with the remaining wires. The wire that was never connected will then by elimination be associated with the number $\{1,\dots,N\}$ that never occurred.
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.
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.
thank you both for your insights!
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.
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!
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.