An old chestnut
goes like this:
An electrician has just drawn a bundle of 15 wires through a long conduit
in a large building, and only after he's finished does he realize that the
wires are unlabeled and look completely identical. The wires are useless
unless the two ends of each wire can be matched up.
The electrician has tags he can use to label the wires, and a
continuity tester, which he can hook up to any two wires to determine if
there is a closed circuit between them. He can also clip together ends
of wires temporarily for the purpose of testing them at the other end with
the continuity tester. However, it's a long walk to the other end of the
conduit, and the electrician wants to make as few trips as possible.
Using nothing else, how can the electrician put unique, matching labels on
each end of each wire while making the fewest trips across the building?