Friday, April 22, 2011

120 G cables

Typical G. question. here 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.

We need to identify and label the cables 1-120. As you might have guessed, the only way to gain information in this setup is to connect some set of wires at one end, walk up to the other end, and test for conductivity. The process may have to be repeated many times before a complete labeling can be constructed. And since each such step involves walking across 10 KM, we wish to solve the problem with the least number of trips.

How would you identify each cable in minimum number of trips?

1 comment:

  1. I think the first thing one usually does when starting to solve this puzzle is to assume that "cable" and "wire" are just two different words for the same thing. The answer here is 2 trips and it doesn't depend on the number of cables, as long as it is not one.

    When one assumes that a cable has two or more wires, it becomes more fun. You don't even need the wires to have different colours. The answer is always 1 trip and it doesn't depend on the number of cables (again, greater than one).

    ReplyDelete