Strategy to find out how wires are connected

Question

There is a tube with $100$ electrical wires that are not labeled. At side $A$ of the tube, the terminal ends of the $100$ electrical wires can be connected. It is possible to connect more than $2$ terminal ends together.

For one measurement, all terminal ends can be connected at side $A$ in different nodes and one can measure the resistance (open circuit or short circuit) amongst all $100$ terminal ends at side $B$. Measuring all connectivities at side $B$ for $1$ constellation at side $A$ counts for just $1$ measurement.

How many measurements are necessary to know which terminal end at side $A$ corresponds to which terminal end at side $A$? What is the strategy to follow?

Answer 1

You can do this in seven measurements. Label the wires in A from 0 to 99 iusing binary numbers. Then for your first measurement, tie together all the A wires with a 1 in bit 0 (the odd wires). Your measurement tells you which of the wires in B are connected to some odd wire in A. (Because any wire in B that is connected to an odd wire in A will show a short on 49 of its tests, while any that is not will shhow open circuits on all of its tests.)

For your second measurement tie together the wires in A having bit 1 of there number equal to 1: wires 2,3,6,7, and so forth. Again you find out which wires in B have bit one of their partners equal to one.

Each of the wires has a 7-bit number so after measurements you now the number of the A-partner of each of the B wires.

Information theory, however, notes that each 50-tied-wires measurement gives information about which 50 B-wires are connected to one of those A-wires. That provides $\binom{100}{50}$ possibilities, or about 96 bits of information. Since there are $100!$ possible interconnection patterns (525 bits) one might hope there is a solution using only 6 measurements. (The above proves that there is no solution using 5 or fewer). But the problem is, it wil take 7 measurements to determine the connection of any individual B wires, because each measurement olny gives you the answer to "is it in this set"?

So the minimum number is indeed seven measurements.

Answer 2

Label the wires on one end (say end $A$) using labels $1$ to $100$. Now, select (arbitrarily) a wire (call it $x$) on end $B$. The goal is to be able to which label on side $A$ does $x$ correspond to.

Connect half the wires (1 to 50) to a node. Then you can tell if $x$ belongs to $1-50$ or $51-100$. Proceed like this (with a bisection search) till you find the matching label for $x$. This will take $\log_{2}100$ measurements.

Repeat for another wire at end $B$.