Something different on my blog now, my submission for this week’s Riddler Classic challenge from Fivethirtyeight.com. If you don’t like math or puzzles, feel free to scroll down and ignore this. 

The challenge is as follows: 

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. Tying two wire ends together and using the circuit detector are both very quick and easy, but this is an old tower and there is no elevator. So, bring your pedometer.

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?

I assume that the circuit breaker works as follows: We connect it to two wires at the top, and it tells us, yes or no, if the two are connected. Since it’s such a quick thing to do, we can always see for all pairs of wires which are connected whenever we’re at the top floor. 

My solution is that it only requires two trips to the top of the tower to match the wires. The way to do this is as follows:

Let us label the wires at the top as T1, T2,… , TN, and the wires at the bottom as B1, B2, … ,BN. For an example, let us say N = 8, and the wires are matched as follows: 

T1 - B7 
T2 - B4
T3 - B3
T4 - B1
T5 - B2
T6 - B5
T7 - B8
T8 - B6 

We start by matching the wires at the bottom, the B-wires, in the first round as follows: We connect B1 to B2, B3 to B4, B5 to B6, etc. If N is odd, the last wire is not connected. If N is even we do not match the last two wires. Here is an example

 

. 

(Yes, my pictures were made in Microsoft Paint. It was convenient)

Now we run upstairs, and see which T-wires are connected to which other T-wires, and draw a graph of it, as follows for our example: 

 

 We run downstairs again, and disconnect all the wires. Next, we connect the wires as follows: We leave B1 disconnected, and connect B2 to B3, B4 to B5, etc. If N is odd, we connect B{N-1) to BN, and if N is even, we again leave BN unconnected. In the following picture, the connections in the first round are marked blue, and the connections in the second round as red. 

 

Now we run upstairs and use the circuit breaker on all the wires again, and draw the result in our graph: 

 

 

 Notice we have created a chain or path of sorts. It starts with the wire B1 that was only connected during the first round (blue) and ends with the wire that was only connected during the second round (BN or B{N-1}, depending on if N was odd or even). If N was even, BN and thus, its corresponding T wire, will never be connected, so we can match them. If we ‘untangle’ the chain on our graph, we will get a similar picture as the B wires, and can thus match the wires:

This works for any N larger than 2. If N is odd, the last, unconnected wire simply disappears without impacting the matching of the other wires.