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?

Answer