# Cable with mixed wires

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
• It's not $n!$ operations in the worst case on the right in your example but $n+(n+1)+...+1=n(n+1)/2$. Commented May 10, 2023 at 19:16
• If you know that all the wires have one-to-one correspondence, you don't need to check the one remaining option, which can be inferred. If there are 3 wires, you need 2 tests for the first wire, 1 for the second wire: 3 tests not 3!. Commented May 10, 2023 at 19:21
• A flaw in your reasoning is the assumption that you need to "check all n wires on the right to find matching one". You can stop at the first match, or when there is only one option left. Commented May 10, 2023 at 19:29
• You are right, I messed that up with another version of the puzzle. I've fixed that. Well, we always count for worst possible scenario, and that would be, check all remaining wires - 1 to find the correct one. Commented May 10, 2023 at 19:32
• I reckon it is $\sum_{i=1}^{n-1}$ Commented May 10, 2023 at 19:34

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