Puzzle : A better solution to colour coding cables


It turns out that there exist a better solution for puzzle related to colour coding of cables.

Once again my brilliant friend Deepanjan came to the rescue and provided a better solution to the above mentioned puzzle.

In the earlier post along the same line, for even number of cables 3 trips were needed where as for odd number of cables 2 trips were needed.

In this solution, I will describe a method to always determine in only 2 trips that which ends belongs to which cable.

Solution : I suggest readers to have a pen and paper handy to comprehend the solution easily.

One assumption made for this solution is that more than two cable ends can be electrically shorted. In which case, if you put continuity meter between any two cable of the bunch, it will show them as connected.

Let us say we have N > 2 cables.

case 1 : N = k(k+1)/2

This case is easy to understand.
We can divide cables into groups of 1, 2, 3 …., k

In every group, all cables belonging to that group is shorted.

Now, we go down ( first trip ). Clearly, we will be able to identify different groups because for cables belonging to group i, continuity meter will show them connected with exactly i-1 other cables.

So we have determined following groups, 1, 2 , …. , k.

Now, we take one cable from each group( 1_1, 2_1, 3_1 …k_1) and short them. First group will be of size k, let us call the group as k’.

Similarly, second group will be of size k-1 ( because group 1 had only one cable, which was consumed in forming group k’)

The last group will have size 1.

Now we go up ( second trip ). Original group of size 1 was determined in the first trip itself. For group 2, if a cable is connected to k-1 other cables then it is 2_1, if it is connected to k-2 other cables then it is 2_2. Similarly we can identify every wire in every group.

case 2 : N = k(k+1)/2 + r where 1 \leq r \leq k

In this case, we will form groups g_1, g_2 \dots g_k, g_r of size 1,2,…,k,r respectively.

Short all cables in their respective groups. For this example, let us say r = 5. So now, there will be two groups of size 5.

We go down ( first trip ) and identify g_1, g_2,\dots,g_5,g'_5,\dots g_k. We will see two groups of size 5. Somehow, we need to be able to distinguish between them. Without, loss of generality we will put g'_5 aside.

From rest of the groups, we will again form a group of size k ( call it h_k ) by taking one cable from each group, as described in case 1.

So we will form groups h_k, h_{k-1},\dots h_1 and one remaining group g'_5. From g'_5, we will keep one cable loose g'^1 _5. For the rest of the cable, we will start adding one cable (g'^2 _5) to h_k, one cable(g'^3 _5) to h_{k-1} and so on. If r=k then it can go only upto h_2.

Now, we will go up ( second trip ). We will find two wires loose ( not connected to any other wire ). But one wire would be from original g_k and one from g_r. So we have identified g'^1 _5. Now, from original group g_r if a wire is connected to k different wires then it would be g'^2 _5. Similalry we can identify each cable from group g_r depending upon how many other wire it is connected to.

Once, each cable from group g_r is identified, we can proceed to identify cables of other groups as already specified. So, for example, from g_k if a wire is connected to 3 other wires in which one of the wires belong to g_r. We know that, it belongs to h_3. We had added only one wire from g_k in h_i so we will be able to identify the cables. Similarly, for other groups.

This solution is undoubtedly correct with the given assumption. If you do not follow the description easily, work out a small example on pen and paper using above method.

— Saurabh Joshi



One Response to “Puzzle : A better solution to colour coding cables”

  1. Peter Says:

    Congratulations Joshi!

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: