Let's suppose that you are adding a circuit to a breaker box: you have a long conduit that you have pulled some wires through, and are going to connect each end of eacn one to some device: a breaker, outlet, panel, whatever. The problem is that the wires are all the same color, and you can't tell them apart.
You have a multimeter, and the wires are all continuous, so you can identify which is which with the meter in continuity-detector mode: the leads on the meter are much shorter than the ends of the conduits are apart, but, you discover a trick: twist a pair of wires together at one end, and you can test at the other end to identify those wires.
And therein is the obvious puzzle: what is the most efficient way, in tests and walks, to identify each wire, for n wires?
Well, you can't. If you only have two wires, you can't tell them apart: there are only two states, connected or not, and if they're connected, there's no way to distinguish one end from the other. In order to identify anything you need a third wire:
With a third wire we can figure some things out, and define some terms. We'll call our wires A, B, and C, and start by connecting A and B:
(A B) C
Walking to the other end, we are faced with three indistinguishable wires: all we can do is pick two and test them. That test will be either positive (the ends are connected) or negative (they are discontinuous).
Positive: The two ends we tested are A and B, although we do not yet know which is which, and the third end must be C.
Negative: One of the two ends we're testing must be C, but again, we can't know which. So we perform another test, with the third wire against one of ours.
If the second test is positive: the wire we swapped out must have been C. If it's negative, the wire in both tests is C.
Either way, we have now identified C, and need only to distinguish A and B. So we walk a second time and make a second configuration:
A (B C)
Now, a single test distinguishes A from B:
If testing C against one of the other wires is positive, the other wire is B; if it's negative then it must be A.
At most three tests and two walks. At miminum two tests and two walks.
But, adding a fourth wire makes things much more complex:
To start with, we'll just put the wires in two pairs:
(A B) (C D)
From this, we can't actually identify any wires for sure, or even narrow them down. But we can relate them to each other, so that now identifying any wire gives us at least one more. To do that, we need either one or two tests:
The second configuration will break one pair and join it with the other:
(A B C) D
Two tests here, starting with one of the pairs we identified earlier will tell us a lot:
Unfortunately there's no way around needing a third configuration, but almost any third configuration will tell us what we need in one test. This is essentially the same problem as the second configuration of n=3; we have two wires, one known, and need to identify which is which. Connecting things like this:
(A C) B D
will allow us to test C (known) against either of the either-A-or-B wires and solve it in one test.
So, the maximum and minimum for n=4 are at most five tests and three walks with the minimum being three tests and three walks.
I guess at this point we're wiring three-phase power or something. Don't question it, it's just a math puzzle.
Our first configuration should split the five conductors into pairs as much as possible:
(A B) (C D) E
The best case for this is that we do two tests and identify both pairs, and the leftover wire, of course. But the worst case is a little harder to nail down.
At any point, a positive test tells us more than a negative one, so the worst case will be that we get all negative tests. The most negative tests we can get from one wire is for that wire to be E: testing E against each of the four others will result in four negative tests, but it's the only wire like that.
Any other wire, we would first test (for example) A+C, then A+D, and A+E, and the fourth test would have to be A+B, positive. So if we do four tests with the same wire, we're guaranteed to either identify E, or identify a pair.
Either of these leads us to one of the previous cases: if we identified E, then we need two more tests to get the pairs; if we found a pair, we need two more tests to get the other pair and E. Regardless, at the end of this, we've identified two pairs and a single, but not the polarity of those pairs or which is which.
However, having the single means we're in a better state than we were after the first round of n=4. We can now do this configuration:
A (B C) (D E)
This is now enough to fully solve the problem. We start by testing one from each previously-identified pair: best case is that we test B+C first, get a positive result, and need one more test (E+x, where x is a wire that was paired with one of those in configuration 1) to solve everything.
The worst case is, again, more tricky: a negative result might mean that we're testing A+C or A+D, or it might mean that we're testing C+A, D+A, or D+B. At most three more tests will get us to B+C though, for five total.
Why does this second configuration solve everything? Because unlike n=4, knowing E makes it possible to ensure that no wire looks identical in this state to how it looked in state one: we can tell which pair was which by seeing which one is newly connected to E, and "connected to E" vs "connected to nothing" distinguishes A and D.
Having five wires frees us from the symmetry problem we had with n=4.
I don't yet have a general algorithm, but I can identify some recurring ideas:
Anyway, it's an interesting problem I think.