A bunch of `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.

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

*Step 1*: Connect the and wires at the labeled end, walk up to the unlabeled end, and test for conductivity. The pair that conducts electricity would be and , although we cannot determine exactly which is or at this point, and the remaining wire is uniquely identified as . 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 with any one of the wires (recall, we don’t know which is or individually, only that one is and the other ). Now walk back to the labeled side and test for conductivity of with the remaining wires. If we find that — is conducting, then the wire we hooked up on the other side was really , otherwise it was .

The case `n = 4` can be solved similarly with just two trip: Hook up — on one side and then run conductivity tests on the other side to partition the wires into two groups — and —; 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 into disjoint sets in two ways and , subject to the condition that at most one element appears in -set of cardinality and a -set of cardinality , for each and . We can then use the coordinates to identify each element.

By a theorem of Ronald Graham, a solution involving just two trip always exists for wires unless 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 iff there’s a 0/1-matrix having row sums and column sums such that and are multiples of and *.

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

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

- On the labeled side, hook up wires in the following groups: , , and .
- Walk over to the unlabeled side, run the conductivity tests, and make the corresponding groups , , and .
- Still on the unlabeled side, hook up the wires in the groups , , and . Note that we still don’t know exactly which wire is, say, ; but we do know the two wires of which one if and the other .
- 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, would correspond to the the sole wire from the group on the other side. Similarly, the connected-pair of — corresponds to the pair 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).

NickAnother 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 :).

AshutoshPost authorThat’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?

NickAshutosh –

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…

AshutoshPost authorCeiling[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!

vhi,

you have got great credentials.. ever tried to work for google ?

AshutoshPost author@v: Never tried ;-)

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

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