Cable with mixed wires

Question

Let's say you have a cable that has n wires. Each wire on the left side corresponds to one wire on the right side. However you cannot distinguish between the wires and you want to know which wire corresponds to another.

You can only use these three operations:

1. Power on a wire on the left side
2. Power off a wire on the left side
3. Check if there is a power on a wire on the right side.

Try to minimize operations that are needed for you to distinguish all n wires..

One straight forward solution would be:

• Power on a wire on the left side, check all n wires on the right to find matching one.
• Power on another wire, now check n - 1 wires on the right
• ... Which would lead to n + (n - 1) + ... + 1 = $\frac{n*(n-1)}{2}$ operations to check wires on the right and $n-1$ operations to power on wires on the left. Resulting in $\frac{n*(n-1)}{2} + (n-1)$ operations

Answer 1

Asymptotic result

Lower bound

As there are n! ways the wire ends could be paired we need by Stirling's approximation order of magnitude n log n bits of information and therefore at least as many operations.

Upper bound

O(n log n) operations are sufficient: Switch on half the wires and check them all. This splits the wires into two groups of half the size. Recursively solve each half. This will terminate after O(log n) recursion steps each costing (summed over the breadth of the recursion tree) O(n) operations.