The Wire Identification Problem

A conduit carries 50 identical wires under a river, but their ends have not been labeled — you don’t know which ends on the west bank correspond to which on the east bank. To identify them, you can tie together the wires in pairs on the west bank, then row across the river and test the wires on the east bank to discover which pairs close a circuit and are thus connected.

Testing wires is easy, but rowing is hard. How can you plan the work to minimize your trips across the river?

	Select Click for Answer
Suppose the wires are labeled W₁, W₂, etc., on the west bank and E₁, E₂, etc. on the east bank. Start by tying W₁ to W₂, W₃ to W₄, and so on, leaving W₄₉ and W₅₀ untied. Now row across the river and test the wires to see which are connected. We might find that E₁₆ is tied E₃₇, E₁₁ is tied E₂₆, E₇ is tied E₄₁, and E₁₉ and E₂₇ are unconnected. Row back to the west bank, untie the wires, and now connect W₂ to W₃, W₄ to W₅, and so on, leaving W₁ and W₅₀ unconnected. Now return to the east bank and test again. We might learn that E₄₁ is tied E₁₉, E₂₆ is tied E₇, E₃₇ is tied E₁₁, and E₁₆ and E₂₇ are unconnected. Happily, we can now deduce all the connections. There will be one wire that had been paired in our first test but not in our second — here that’s E₁₆. That wire corresponds to W₁. The wire that E₁₆ had been paired with in our first test, E₃₇, must then correspond to W₂. And E₃₇ is now connected to E₁₁, so E₁₁ must be W₃. And so on: We can work down the list from W₁, alternately consulting the current connections and our memory of the first connections to reveal each wire in succession. So only three rowings are necessary. From Roland Sprague, Recreation in Mathematics, 1963. Sort of related: There’s a light bulb in the attic, and you’re downstairs facing three on-off switches. How can you tell which switch controls the light with only a single trip to the attic? Turn on Switch 1, leave it on for a minute, then turn it off, turn on Switch 2, and run upstairs. If the bulb is on, then Switch 2 controls it. If the bulb is off and warm (ha!), then Switch 1 controls it. Otherwise it’s Switch 3.

Click for Answer