## Puzzle : Colour coding cables

Well, this page reminded of me a similar puzzle which I read long back. Copying the problem text below.

Problem :

This is ancient lore – from the time Empire State Building was being built. They had raised the structure successfully, had made all the floors, had built the elevator shaft. They had laid cable inside the elevator shaft. However, just before installing the elevator, they found out the blunder – the cables were not color coded.

They contracted this one electrician and asked him to color code all the wires.

There was a set of N=25 wires running from the top of Empire State Building to the bottom through a cable sheath. The electrician can assume that the wires are all insulated, and the cable sheath is conductive (although this is not necessary for a solution). The only equipment that the electrician has is a continuity meter. He knows how to connect and disconnect wires and how to use the continuity meter.

• How will the electrician color code all the cables? Needless to say, the electrician has to do it in as few climbing-ups and climbing-downs as he can, and as few connections-disconnections (although, this does not carry as much weight) as possible.

A continuity meter is a voltage source in series with a light bulb. If both ends of a continuous wire are connected to the two ends of the continuity meter, the bulb switches on. If the wire is not continuous, the bulb remains off.

• Once you have a solution, extend it to arbitrary N. (both, N odd, N even.)

Well, this puzzle also goes by other names like cable-car, ropeway cables etc. Here this guy has used cables inside elevator shaft.

Anyways, color coding is needed to identify two ends of a very long cable.

Solution : Well, I am trying to describe the solution with a very small example, but you might need a pen and paper to actually understand it.

I will first prove that we need total 3 trips ( or 1.5 trips if you consider a to and fro journey as a trip ) to determine which end belongs to which wire. You might need an additional trip to actually disconnect wires and color code them. We need 3 trips in case the number of cables are even and greater than 2. I will prove that 2 trips will suffice in case of odd number of cables ( greater than 1 of course, as we don’t need any colour code if there is only 1 cable ).

With given resources, I believe it is impossible to colour code if there are exactly 2 wires.

Anyways, me and my friend Deepanjan both came up with solution. However, his solution is a bit involved so I will describe only my solution here.

Let me give you example with 6 cables. Let A1 to A6 be ends of cables at the top of the building and B1 to B6 be ends of cables at the bottom. Let correspondence between them is A1-B1, A4-B2, A2-B3, A3-B4, A5-B5, A6-B6. The problem is to find this correspondence.

Assume that we start from the top of the building. We will short A1-A4, A2-A3, A5-A6. The labels here are just to verify the correctness. When we actually start we will make pairs by shorting any two wires at a time. So for N wires, we will have N/2 pairs.

Now, we come down ( 1st trip ) and using continuity meter can find three pairs. We will call them B1-B2, B3-B4 and B5-B6. At this point, we have no idea, which pair corresponds to which pair at the top. What we will do now is disconnect all the wires. Now we will short every B(2i) with B(2i+1), so in this case, we will short B2-B3 and B4-B5. B1 and B6 will remain disconnected.

Let us go back up ( 2nd trip ). Again disconnect all connections. We will find two wires ( A1 and A6 ) to be disconnected using continuity meter as they does not form a close loop when the meter is connected between them and any other cable. So A1 = ( B1 or B6 ) and A6 = ( B1 or B6 ). Because A1 = ( B1 or B6 ) we can deduce that A4 ( which was paired with A1 earlier ) must be either B2 or B5. We will find that A4 is connected with A2. So A2 can be either (B4 or B3). Similarly we can deduce following facts :

A1 = ( B1 or B6 )

A4 = ( B2 or B5 )

A2 = ( B3 or B4 )

A3  = ( B4 or B3)

A5 = ( B5 or B2)

A6 = ( B6 or B1 )

We need to only resolve now whether A1 is ( B6 or B1 ). If we can do that, rest all can be determined. So now, we will short A1 with any other wire except A6 ( as it is also having the same possibilities ). Let us say, we short A1-A2.

We will go back down ( 3rd trip ). After disconnecting all connections. We will find that B1 and B3 are connected and rest all are disconnected. That will ensure that A1 was indeed B1. Thus we have correctly determined which end belongs to which wire.

In case, of odd wires things become a bit simpler. Because of odd number, we can only form (N-1)/2 pairs by shorting and one wire will remain loose ( call it A1). When we come down ( first trip ), we will name the loose wire as B1 and rest of the pairs as B2-B3, B4-B5 and so on. Now, we will short B1-B2, B3-B4 and so on. Bn will remain loose.

In the second trip back up, we already know which wire corresponds to B1 ( A1 is the corresponding end in this case ). Now  a cable connected to B1 ( A1 ) will be B2 ( say Ai). Cable which was paired up earlier with Ai will be B3 and so on.

Thus, we need only two trips in case we have odd number of cables.

— Saurabh Joshi