6
$\begingroup$

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
$\endgroup$
7
  • $\begingroup$ It's not $n!$ operations in the worst case on the right in your example but $n+(n+1)+...+1=n(n+1)/2$. $\endgroup$ May 10, 2023 at 19:16
  • $\begingroup$ 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!. $\endgroup$ May 10, 2023 at 19:21
  • $\begingroup$ 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. $\endgroup$ May 10, 2023 at 19:29
  • $\begingroup$ 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. $\endgroup$
    – popcorn
    May 10, 2023 at 19:32
  • $\begingroup$ I reckon it is $\sum_{i=1}^{n-1}$ $\endgroup$ May 10, 2023 at 19:34

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Yep, essentially this gives each wire on the right a sequence of log n bits, which we can match with the unique wire on the left based on the sequence of on/off $\endgroup$
    – justhalf
    May 10, 2023 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.