Tuesday, August 16, 2011

There is a bunch of 120 electrical cables laid under the ground

The cables are 10 KM in length and both ends of each wire are out in open. Label all the cables with minimum number of trips.

Solution.

The key intuition here is that you have 2 sources of information. Either the cables are connected or they are disconnected ;-). so you can connect all of them but leave two of disconnected or connect just two of them. if you leave 3 disconnected than you have an ambiguity and you need a round trip for solving this for just 3 cables. That's a lot

Let's try to leave just 2 connected. You need 1 round trip to identify the pair and so a total of 60 trips. That's a lot.

Let's try to connect all of them but leave 2 disconnected marking them red and blue. In one trip you find the disconnected pair and can name them #1 and #120 (any number works here provided that you remember it for the next step). All the other cables will be numbered from #2 to #119.  Here you can encode another information just by leveraging the order. You assign to a cable #2 and to the one connected to it #3. Then you assign to another cable #4 and to the one connected to it #5, and so on and so forth (*).


Now Let's try to connect again all of them and leave 2 disconnected. This time we will split the disconnect pair and connect one cable of them. So assume we connect (#1, #2 ) (#3, #4)    (#118, #119) and leave #120 disconnected (**)

Return to base. We have red and blue. But we know that one of them must be disconnected and we know that the disconnected one has number #120, while the other one must be #1. That' why we broke the pair because we wanted to solve the ambiguity a (disconnection is not ambiguous when there is just one disconnected). So now we know what is #1 and what is #120. 

Surprisingly enough we are done! because we know that  the other side has (#1, #2 ) so we know #2  is the one connected to #1 and we can test what is connected to #1.  But when we know the #2 then we know the #3 because of the naming convention adopted here (*), and if we know the #3 then we know the #4 because of the choice taken here (**).

Talking about encoding information.

1 comment:

  1. http://tech-queries.blogspot.com/2011/04/wire-identification-problem.html

    ReplyDelete