The Wire Identification Problem

The Wire Identification Problem: Try to label the wires on the right with labels corresponding to those on the left

A bunch of n wires have been labeled at one end with alphabetic codes A, B… The wire identification problem asks for an efficient procedure to mark the other end of the bunch with the corresponding labels. The wires run underground so you can’t track them individually and any wire is visibly indistinguishable from any other (except for the labeling).

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 — this would give some partial labeling information. The process may have to be repeated many times before a complete labeling can be constructed. And since each such step involves walking across the distance of the wires, we wish to solve the problem with the least number of trips.

Small Cases

It should be easy to convince oneself that this problem cannot be solved when n = 2 — there’s really nothing we can use to break the symmetry of the situation.

Solution to the wire identification problem of 3 wires with just two trips

For n = 3, we can use the following simple procedure (see the illustration on the right):

  • Step 1: Connect the A and B wires at the labeled end, walk up to the unlabeled end, and test for conductivity. The pair that conducts electricity would be a and b, although we cannot determine exactly which is a or b at this point, and the remaining wire is uniquely identified as c. For notation, we use lowercase letters for the labelings that we discover, versus uppercase letters for the given labeling.

  • Step 2: Connect the newly identified wire c with any one of the wires a/b (recall, we don’t know which is a or b individually, only that one is a and the other b). Now walk back to the labeled side and test for conductivity of C with the remaining wires. If we find that CB is conducting, then the a/b wire we hooked up on the other side was really b, otherwise it was a.

The case n = 4 can be solved similarly with just two trip: Hook up AB on one side and then run conductivity tests on the other side to partition the wires into two groups ab and cd; then hook up one from each of the two groups together etc.

So the question is: Can the problem be solved for all n with just two trips?

The General Case

The wire identification problem is one of those puzzles that is deceptively simple in its description, whose small cases are easy enough to solve in the head, and yet a fair amount of math goes into proving the general result.

I first read about this fascinating problem in the Don Knuth’s Selected Papers on Discrete Mathematics book — in a short 5-page paper titled The Knowlton–Graham partition problem (arXiv link).

Knuth states the following idea, attributed to Kenneth Knowlton, to solve the general problem:

Partition \{1,\ldots,n\} into disjoint sets in two ways A_1,\ldots,A_p and B_1,\ldots,B_q, subject to the condition that at most one element appears in A-set of cardinality j and a B-set of cardinality k, for each j and k. We can then use the coordinates (j,k) to identify each element.

By a theorem of Ronald Graham, a solution involving just two trip always exists for n wires unless n is 2, 5, or 9 (On partitions of a finite set [PDF]).

Knuth in his paper translates the problem of Knowlton-Graham partitions in terms of 0/1-matrices. Lemma 1 in that paper states: Knowlton-Graham partitions exist for n iff there’s a 0/1-matrix having row sums (r_1,\ldots,r_m) and column sums (c_1,\ldots,c_m) such that r_j and c_j are multiples of j and \sum r_j = \sum c_j = n.

Let’s use this lemma to label a set of 6 wires (A\ldots F). Since we can write 6 = 1 + 2 + 3, a rather obvious matrix satisfying the conditions of the lemma is:

\left(\begin{array}{ccc}0 & 0 & 1\\ 0 & 1 & 1\\ 1 & 1 & 1\end{array}\right)\quad, corresponding to the assignment \left(\begin{array}{ccc}0 & 0 & A\\ 0 & B & C\\ D & E & F\end{array}\right)

Guided by this matrix, here’s our two-trip identification procedure:

  • On the labeled side, hook up wires in the following groups: \{A\}, \{B,C\}, and \{D,E,F\}.
  • Walk over to the unlabeled side, run the conductivity tests, and make the corresponding groups \{a\}, \{b,c\}, and \{d,e,f\}.
  • Still on the unlabeled side, hook up the wires in the groups \{d/e/f\}, \{b/c, d/e/f\}, and \{a, b/c, d/e/f\}. Note that we still don’t know exactly which wire is, say, b; but we do know the two wires of which one if b and the other c.
  • Walk over to the labeled side, unhook the connection we had made in the first step, and check for conductivity. The sole wire here, say, F would correspond to the the sole wire from the d/e/f group on the other side. Similarly, the connected-pair of B/CD/E/F corresponds to the pair \{b/c, d/e/f\} on the other side. etc.

Extensions

Navin Goyal, Sachin Lodha, and S. Muthukrishnan consider some variants & generalizations of the wire identification problem in their paper The Graham-Knowlton Problem Revisited. In particular, they consider the restrictions to just hooking up pairs in the identification process (in our examples above, we were free to hook, say, 3 wires).

8 thoughts on “The Wire Identification Problem

  1. Nick

    Another interesting related, but different (I think) problem arises if you let the wires be optical fibers capable of representing two states (on and off or whathaveyou).

    The two-wire situation is now obvious. Besides that I’ve only looked at the five wore situation which can be solved in three steps as follows:

    For wires A,B,C,D, and E, light up A, B, and C and mark that group somehow. Then light up A, and D. This will give you A (lit up both times), D (lit up once), and E (never lit up). Now you have the two wire situation (B and C) and so one more step will do it.

    Not sure if it can be done in two steps, nor do I have an inkling towards the general solution.

    Is anyone aware if this is a solved problem? Please don’t tell me Erdös solved it :).

  2. Ashutosh Post author

    That’s an interesting problem, Nick!

    For 5 wires, by working out all possible two-step solutions, it looks clear to me that a three-step solution is the best possible.

    In general, a Ceiling[Log[2,n]]-step solution is easy: Number the wires {0,1,…,n-1}. In the kth step, turn on the lights of wires the binary representation of which have kth bit ON. On the other end, keep building the IDs of each wire, a bit at each step.

    Now the question is: Could some clever scheme do better than Ceiling[Log[2,n]]-steps?

  3. Nick

    Ashutosh –

    I think your Ceiling[Log[2,n]]-step assertion is correct, but I’m confused about your method. For eight wires are you saying you should light in the following pattern?
    00000001
    00000010
    00000011
    00000100
    00000101
    00000110
    00000111
    00001000

    Most of those are redundant and you still wouldn’t know four of them. I’m either misunderstanding you and/or you meant something like this:
    11110000
    11001100
    10101010

    This is such a simple method, I wonder if there isn’t some more complexity lying within this problem once n gets bigger…

    I’m starting to be convinced that there is not. Any initial n-splitting with k “on” wires, no matter how complex, is essentially “isomorphic” to an (n-k)k split, that is, 11001100 ~= 11110000 ~= 10101010. Then it essentially becomes two problems – (n-k) and k. Just judging from our small samples clearly it is better when k = n/2, or as close as possible if n is odd. If k = n/2 is the ideal split, then Ceiling[Log[2,n]] should be correct, no?

    For example if instead of splitting 8 into 4-4 we split into 6-2 we’d end up taking four steps instead of three, since we have the initial split and 6 takes three steps.

    hmm…

  4. Ashutosh Post author

    Ceiling[Log[2,n]]-step method is for your modified problem description (where each optical fiber can be ON/OFF). For eight wires labeled {000,001,…,111} in binary, you’ll need 3 steps:
    1. Turn on the just wires 1,3,5,7 on end A. On end B, label the wires — the ON and OFF groups will be {xx0, xx1}, each with 4 wires.
    2. Next turn on just the wires 2,3,6,7. On end B, the two group classifications will be re-classified as {x00, x01, x10, x11}.
    3. Next turn on just 4,5,6,7. End B will now have 8 “groups”: {000, 001, …, 111}.

    And yes, n/2 splitting (for this modified problem) _should_ be optimal as it transmits maximum information. And I think the _proof_ should be obvious from some information theoretic point-of-view.

    So, I think this modified optic-fiber problem turns out to be easy after all; compared to the original copper-wire problem that involved more interesting math. And that deeper problem always (when n != 2,5,9) has a 2-step solution compared to the best Log[2,n]-step solution of the simpler problem!

  5. Dave Dodson

    @Ashutosh
    What is wrong with this for n = 5:
    At the first end, connect pairs of wires, leaving one wire unconnected. Label the unconnected wire #1.

    At the other end, find a pair of connected wires. Label one of them #2 and the other #3. Find the second pair of connected wires. Label one of them #4 and the other #5. The remaining unconnected wire can be labelled #1. Now connect #1 to #2, #3 to #4, and leave #5 unconnected.

    Back at the first end, disconnect the previous connections, but keep track of the pairings. Find the wire now connected to #1 at
    the other end. Label it #2. The wire that was connected to #2 at this end can be labelled #3. The wire now connected to #3 at the other end is #4, and the wire that was connected to #4 at this end is #5.

    We have made two trips and have labelled each wire with the same number at both ends.

    Dave

  6. Ashutosh Post author

    @Dave: I think you solution is a good one, and it works for all odd n (including n=9).

    Just that it doesn’t use the Knowlton-Graham partition. If you look at Graham’s original paper http://www.math.ucsd.edu/~ronspubs/66_01_finite_set.pdf, there is one constraint that your solution doesn’t meet: When arriving back on the starting end, he disconnects all wires, does conductivity tests, and from the cardinality of the connected set alone identifies the labeling. In your solution, you have to keep a little memory of which wire the wire #2 was connected to (on the original side), so that you can “reason backwards” etc.

    That said, it looks like a perfectly good practical solution.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>