10
$\begingroup$

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.

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 identify and label each individual wire in the cable? enter image description here

Addenda:

  • 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.

Spoiler #1

Solve the puzzle for 2 wires and extrapolate from there.

Spoiler #2

Not all spoilers are helpful.

$\endgroup$
  • $\begingroup$ Is a wire stripper needed to use a continuity tester? i.e. strip the wire, connect one end of the continuity tester, strip the wire at the other and connect the other end of the continuity tester to the wire $\endgroup$ – DeeCeptor May 28 '15 at 20:45
10
$\begingroup$

The wires can be labelled using a total of

two trips.

We start by forming the 64 wires into 10 groups, of size 11, 10, 9, 8, 7, 6, 5, 4, 3, and 1. All the wires in each group are twisted together. We will attach a temporary label to each wire, recording the size of the group it is in.

Now, we walk to the other end. Using the continuity tester, we can determine precisely which pairs of wires are twisted together, so for each wire, we can determine the size of the group it is in, and therefore its temporary label.

Now, we will assemble the wires into 11 different groups, of varying sizes. The temporary labels of the wires in the groups will be \begin{gather*} \{11,7,6,5,4\},\{11,10\},\{11,10,9\},\{11,10,9,8\},\{11,10,9,8,7\},\{11,10,9,8,7,6\},\\\{11,10,9,8,7,6,5\},\{11,10,9,8,7,6,5,4\},\{11,10,9,8,7,6,5,4,3\},\{11,10,9,8,7,6,5,4,3,1\},\{11,10,9,8,3\}. \end{gather*} Note that no two groups are identical.

Each wire is then given a permanent label, and for each wire, we write down:

  • the wire's permanent label,
  • the wire's temporary label, and
  • the temporary labels the wires now grouped with that wire.

We make a trip back to the other end and separate the wires. Using the continuity tester, we can see which wires are connected to which others. For each wire, we can see its temporary label, as well as the temporary labels of all other wires attached to it. This is sufficient to determine the corresponding permanent label.

$\endgroup$
  • $\begingroup$ Yep, this was the other solution I knew of. I didn't get round to writing it up though, so +1 to you for getting there first. $\endgroup$ – Rand al'Thor May 28 '15 at 22:59
6
$\begingroup$

Two trips (there and back).

Strategy

First, tie the 64 wires together randomly in 32 pairs. Next, go to the far end, randomly label any wire 1, and connect your continuity tester to it. Test which other wire is tied to it at the starting end, and label that wire 2. Then pick another wire other than 1 or 2, label it 3, and tie it to 2, so now the continuity tester is connected to 1, which is tied to 2 at the other end, which is tied to 3 at the end you're at. Now test which wire is tied to 3 at the other end, and label that 4, etc.

What you will wind up with is all 64 wires tied to each other in a continuous sequence. Then go back to the end you started at, leaving the continuity tester behind, connected to wire 1. Before you untie all the wires at the starting point, label each wire so that you know which wire was paired with which. Now with all the wires untied at the starting point, test which wire is connected to the continuity tester and label that 1. Whichever wire was in the same pair as 1, label that 2, and then tie 1 and 2 back together. Now you can find 3, because it's tied to 2 on the far end. Once you find 3, label the wire it was tied to 4, etc.

(This assumes that the resistance of the wire is small enough that the battery will still light the bulb across 12,000 km of wire.)

$\endgroup$
  • 1
    $\begingroup$ +1 cool, and fast, but wouldn't you need to go back once more to untie the wires from the second side? or not, since you did "identify and label" which is what the question technically asked? $\endgroup$ – JLee May 28 '15 at 20:20
  • $\begingroup$ @JLee Hmm, good point. Let's see what the OP says. $\endgroup$ – Rand al'Thor May 28 '15 at 20:21
  • 2
    $\begingroup$ How do you "test which wire is connected to the continuity tester" when you've left the continuity tester behind? It sounds like you are assuming a separate battery and bulb. You don't have that in this puzzle. They are contained in a single device. $\endgroup$ – Anon May 28 '15 at 20:22
  • 3
    $\begingroup$ @Anon you lick wires until one zaps you, obviously. $\endgroup$ – Deacon May 28 '15 at 20:25
  • 2
    $\begingroup$ I think your solution still works if you tie 62 wires in 31 pairs and leave two untied. After the first trip, you can then build a continuous sequence of 63 wires with one odd man out, which can be trivially discovered after the second trip. In fact, this solution is scalable and works for any number of wires other than two, without the need for complex combinatorial stuffs. $\endgroup$ – João Mendes May 29 '15 at 10:58
1
$\begingroup$

Best attempt:

2 trips

Trying hard not to look at the other answers!

First attempt:

6 trips

First, label every wire at one end A1-64. Connect together all of A1-32, and do the same for A33-64. Write a 0 on labels A1-32, and a 1 on labels A33-64.

Walk to the other end (1)

Label up the wires at this end, B1-64. Test connectivity of B1 and B2, B1 and B3, etc. Label all the ones that connect to B1 with a 0, and the rest with a 1. Now connect half of the 0-labelled wires together with half of the 1-labelled wires, and then connect all the other wires together. Write down which ones you have connected up, and add a second digit of 0 after the first digit for all the wires now connected to B1, and a 1 for the wires in the other group.

Walk to the other end (2)

Repeat the tests, this time adding a 0 after the first digit for all those that connect to A1, and a 1 for all those that connect to the other group.

Each of these passes gives us 1 additional digit. 64 wires requires 6 bits, so we will need a further 4 passes. At the end, all the wires are labelled with a 6 bit code and we are done.


But I had an idea. During the second step where we are testing which wires are connected, we can use the information about how many wires are connected, as well as which wires they are connected to. So:

Second attempt.

2 trips

Label the wires A1-64. Connect together the following groups: A1-2, A3-5, A6-9, A10-14, A15-20, 21-27, 28-35, 36-44, 45-54, and 55-64 you can leave unconnected (I originally started with bundles of 64, 32 etc, because binary is always the answer to puzzles, but then realised that reduces the number of groups I can have). Label each wire in a group with its group number: 1 for A1-2, 2 for A3-5 etc.

Walk to the other end (1)

Now find those groups. The 2-group must be B1 and 2, the 3-group must be 3-5, etc, and the unconnected ones must be 55-64. There were 10 groups originally, and we can connect one of each group into a new group - so B1,B3,B6,B10,B15,B21,B28,B36,B45,B55. Since we only needed 1 bit of information to identify A1 vs A2, we can do the same for the next wire in the latter 9 groups, so B4, A7, A11... - continue until you have a new group of 9 wires, another of 8 wires etc. This will end at a group of 2, B54 and B64.

Walk to the other end (2)

Disconnect the wires. One of wires A1 and A2 will be connected to other wires - Relabel the one that is connected as B1, and the one that is not as B2. B1 is connected to 9 other wires; for each of the original A groups, find out which one and relabel it with the B number it must be connected to (B3, B6 etc). Continue through all of the groups. All your wires are now labelled.

Go home and sleep, your dreams will be full of numbers and tape.

$\endgroup$
0
$\begingroup$

Labeling ends North and South for easy writing.

It will take you

7 trips

How do you do it?

Start at the South end. Strip the end of each wire and tie two together. Label both of these 1 and 2.

Go North. Strip the ends of the wires and start checking pairs of wires with the continuity tester. When the tester indicates a continuous path, put a blank label on both of the wires, so you know which ones you found. Break the connection and tie one of them to a third wire. Label that wire as 3.

Go South. Start testing wires against 1 and 2 until you find your continuity again. Label the unlabeled wire 3 and note which wire 3 was attached to. For sake of easy writing, let's say it was 1. Tie a wire into each 1 2 and 3 and label these as 4 5 and 6.

Go North. Relabel the blank labeled wire tied to 3 as 1, break that connection, and the loose blank labeled wire as 2. Now, test continuity between unlabeled wires and 1. When you find it, call that '4'. Repeat for 2 and 5 and 3 and 6. Now, tie a new wire to each of the six labeled wires, and incremented labels to each.

Go South. break all the connections down here and test pairings for each labeled wire. Label accordingly. You should now have 12 labeled wires. Tie off pairs and label down here so you have 12 connections and 24 labeled wires on this end.

Go North. Repeat the previous step. You now have 24 connections and 48 labeled wires on this end.

Go South. Repeat the previous step, tying off the remaining 16 wires to 1-16. You now have 48 connections and all wires labeled on this end.

Go North. Check the pairs against 1-16, labeling accordingly. If you want to be nice and untie the wires at the other end, you could take another trip. But you're tired. Let the next shift deal with that.

$\endgroup$
0
$\begingroup$

3 trips (one way).

Make 8 groups of 8 wires. Tie the ends of each group together so they connect.

Cross (first time).

Identify which wires are connected to which others, one pairing at a time. Since there are only 8 groups, this will take an average of about 4 checks per wire. Label all these wires AA, AB, AC, ... HH with all the wires in each group having the same first letter, different second letter.

Connect the groups of wires at this end, based on the second letter. So AA connects to BA, CA, etc.

Cross (second time).

Disconnect all wires, but keep the groupings. Pick a group, label the wires in that group with 2-digits as 11 through 18. Pick a second group. Find the wire that connects to 11. Label that as 21. Label the rest as 22 through 28, based on which wire in the first group they connect to. Continue with all wires.

The sets of pairings is consistent, so all we have to do now is determine which first letter corresponds with which first digit and which second letter corresponds with which second digit.

Now connect 11 and 21.

Then connect 12, 33, 44.

Then connect 13, 55, 66, 77.

Then connect 51, 62, 73, 88, 84.

Cross (third time).

Disconnect all wires. Test. There will be four groups of wires that connect, and the groups will have sizes 2,3,4,5. There will be one wire in the group with 2 that has the same first letter as one of the wires in the group with 3. The one in the smaller group corresponds to 11, the other to 12. The other one in the smaller group is 21.

Wire 13 is the one in the group with 4 that has the same first letter as 11 and 12. Wire 33 is the one in the group with 3 that has the same second letter as wire 13. Wire 44 is the remaining one in the group with 4.

Wire 51 is the one in the group with 5 that has the same second letter as 11. Likewise 62 has the same second letter as 12, and 73 has the same second letter as 13.

You can now identify 55, 66, 77 as the remaining wires in the group with 4 that have the same first letters as 51, 62, 73, respectively. Wire 84 has the same second letter as 44, and 88 is the last wire in the group with five.

You have now identified which first letter is which number and which second letter is which number. Relabel all the wires with numbers.

You are done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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