untangling riddle

Boston1This week riddle is rather anticlimactic [my rewording]:

N wires lead from the top of a tower down to the ground floor. But they have become hopelessly tangled. The wires on the top floor are all labelled, from 1 to N. The wires on the bottom, however, are not.

You need to figure out which ground-floor wire’s end corresponds to which top-floor wire’s end. 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?

Indeed, first, if N=2, the wires cannot be identified, if N=3, they can be identified in 2 steps, and if N=4, they can also be identified in 2 steps (only pair two wires first, which gives their values and the values of the other two up to a permutation, then pair one of each group). Now, in general,  it seems that, by attaching the wires two by two, one can successively cut the number of wires by two at each trip. This is due to the identification of pairs: if wires a and b are connected in one step, identifying the other end of a will automatically determine the other end of b if one keeps track of all connected pairs at the top. Hence, if N=2^k, in (k-2) steps, we are down to 4 wires and it takes an extra 2 steps to identify those 4, hence all the other wires. Which leads to identification in N trips. If N is not a power of 2, things should go faster as “left over” wires in the binary division can be paired with set-aside wires and hence identify 3 wires on that trip, then further along the way… Which leads to a 2^{\lfloor \log_2(N) \rfloor} number of trips maybe (or even less).

However, when sitting in the taxi between Darjeeling and Bagdogra aiport, I thought about it further and realised there was a much faster version: if N is odd, create (N-1)/2 pairs at the bottom, leave one alone. Going up will link pairs of digits and identify the lone wire. Going down, link this lone wire to the one of the first pair, then the second of the first pair to the first of the second pair, and so on. (First, second, &tc., having of course no other meaning than simplifying the description!) When going up, the know wire will identify the one it is linked to, therefore the second of the original first pair, which in turn will identify the first of the second pair, and so on. Therefore the approach identifies all wires in two trips. If N is even, I cannot find a solution in less than three trips: first round is the same, except there is no lone wire. Then second round links firsts of first and second pairs only. This identifies the four wires in those two pairs, and the third round is the same as before. However, as solved on The Riddler today, there is a solution in two trips, which is based on leaving the last two wires unconnected for the first trip, meaning they are identified up to a permutation. Starting a chained sequence of pairs from one of those two then leads to a resolution in two trips!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s