The electrician problem

868.2K Views

You’re an electrician working at a mountain.  There are N wires running from one side of the mountain to the other.  The problem is that the wires are not labeled, so you just see N wire ends on each side of the mountain.  Your job is to match these ends (say, by labeling the two ends of each
wire in the same way).

In order to figure out the matching, you can twist together wire ends, thus electrically connecting the wires.  You can twist as many wire ends as you want, into as many clusters as you want, at the side of the mountain where you happen to be at the time.  You can also untwist the wire ends at the side of the mountain where you’re at.  You are equipped with an Ohm meter, which lets you test the connectivity of any pair of wires.  (Actually, it’s an abstract Ohm meter, in that it only tells you whether or not two things are connected, not the exact resistance.)

You are not charged [no pun intended] for twisting, untwisting, and using the Ohm meter.  You are only charged for each helicopter ride you make from one side of the mountain to the other.  What is the best way to match the wires?  (Oh, N>2, for there is no solution when N=2.)

Share
ronret45 Expert Asked on 1st August 2015 in Microsoft Interview Puzzles.
Add Comment

  • 1 Answer(s)

    Suppose that there are N wires.

    If N is even: At the first end, connect pairs of wires together,
    leaving two wires unconnected. Go to the other end. Find a pair of
    connected wires, and number them #2 and #3. Find another pair and
    label them #4 and #5. Repeat for all of the pairs, with the last pair
    labeled #N-2 and #N-1. There remains two wires that are not connected
    to each other. Label one of these #1 and the other #N. Connect #1 to
    #2, #3 to #4, etc, leaving #N-1 and #N unconnected. Go back to the
    first end. One of the originally unconnected wires still is
    unconnected. Label it #N and label the other originally unconnected
    wire #1. Now find the wire connected to #1 and label it #2. The wire
    that originally was connected with new wire #2 can be labeled #3. The
    wire that is now connected to the newly labeled #3 is #4. In this way,
    all of the wires
    can be identified on both ends in two trips (one round trip).

    If N is odd: At the first end, connect pairs of wires together,
    leaving one wire unconnected. Label it #1. Go to the other end. Find a
    pair of connected wires, and number them #2 and #3. Find another pair
    and label them #4 and #5. Repeat for all of the pairs, with the last
    pair labeled #N-1 and #N. There remains one wire that is not connected
    to any other wire. Label it #1. Connect #1 to #2, #3 to #4, etc,
    leaving #N unconnected. Go back to the first end. Find the wire
    connected to #1 and label it #2. The wire that originally was
    connected with new wire #2 can be labeled #3. The wire that is now
    connected to the newly labeled #3 is #4. In this way, all of the wires
    can be identified on both ends in two trips (one round trip).

    ronit Guru Answered on 5th August 2015.
    Add Comment
  • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.
  • More puzzles to try-