6
$\begingroup$

Variant of: Labeling wires in a bundle

At a remote location, you just finished trenching a data cable across a large plot of land. The cable has 64 individual wires that are not color-coded or labeled.

You have a wire stripper, a simple electrical continuity tester, and a label maker. There is sufficient excess at either end to allow connecting and reconnecting the individual wire ends in whatever combinations you wish.

Your boss, who is long gone for the day, calls you with some bad news. During installation, the cable got damaged, and some of the wires may be broken. You are instructed to determine how many wires in the cable are still good and also individually label them. If it happens that more than 50% were broken and you can prove this, you need not proceed further.

It's a long walk and you are tired. What is the fewest number of trips from one end of the cable to the other required to find and uniquely label each individual intact wire in the cable? enter image description here

  • The continuity tester is a sealed unit. You can't pull the battery out and leave it behind.
  • It's not necessary to make a final trip after the wires are labeled just to clean up. If they are all labeled at both ends, the job is done.
  • If there are $n$ good wires, their ends must wind up with matched labels from 1 to $n$
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Anon, if you see this a half year later, any chance of loosening the labeling restriction a bit? Perhaps: good ends must wind up with unique labels that are matched in a list. Reasons: (i) the presently-required 1-through-$n$ labeling reduces this puzzle to your previous version plus 1 trip; (ii) the looser labeling restriction interestingly allows for fewer trips in some cases; (iii) no solutions posted yet for 1-through-$n$ labeling; (iv) perhaps you unintentionally overstated the 1-through-$n$ qualification, originally in a comment below. $\endgroup$
    – humn
    Feb 1, 2016 at 22:05

2 Answers 2

Reset to default
3
$\begingroup$

2 trips. Shorten one end by connecting all edges. Check continuity in pairs in the other end - mark them as not broken. If less than 50%, 32, done. Shorten the good ones at that end and make a second trip to the other end - disconnect and check for continuity - mark the ones connected. Done!

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Technically, the fewest number is 1, but that will require at least 50% to be toast. $\endgroup$
    – Ian MacDonald
    Jun 10, 2015 at 21:50
  • 1
    $\begingroup$ @IanMacDonald Well, SUPER technically, the fewest number is 0--you find a more sensible job. ;) $\endgroup$
    – Conor O'Brien
    Jun 10, 2015 at 21:56
  • 2
    $\begingroup$ The puzzle requires more than marking wires as "good" or "bad". They also need to be identified on both ends. $\endgroup$
    – Anon
    Jun 11, 2015 at 13:53
  • $\begingroup$ I.e. If there are n good wires, each end of the cable must have them uniquely labeled from 1 to n $\endgroup$
    – Anon
    Jun 11, 2015 at 14:04
  • $\begingroup$ You need to be specific in your question that you want to identify both ends of a good wire. $\endgroup$
    – Moti
    Jun 12, 2015 at 2:38
2
$\begingroup$

Either (a)

1 Trip

Or (b)

3 Trips

Depending one whether 50% of the wires or more were dead.

In (a) you do what @Anon suggests which is simply short all wires at end A together, then go to end B and check each wire to identify which are dead (this is done by first finding any pair of cables that there is continuity on, and then checking every other cable for continuity with one from that pair). Label them. If there are more than 50% dead give up and go have a cup of tea.

In (b) we assume <50% are dead, in which case having done (a) you are at end B where you were testing you now can ignore all the dead cables (cut them off so they never get used for example), and simply follow the steps from the 'undamaged' identification question to identify the working bundles but exclude the dead ones in the groups (also while your are at A during that process you can label the dead ones as they are the ones which are left unlabelled during that step). The number of required journeys for that is already known, so add on (a) to that number and you get (b).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.