## Puzzle : A better solution to colour coding cables

Well,

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