0809.3: Wires


Puzzle #3: Wires (January 2009)

Once upon a time, the electricity on the north and south sides of campus was completely unconnected. In those days, there was an enormous mountain, Thompson Peak, where College Hill Road is now. Travel between the two sides of campus took weeks, and many brave students lost their lives traversing the great range. In those days, each student had to come to campus with his or her own work-mule to carry supplies for the great trek between the library on the north side of campus and the dorms on the south.

Before Thompson peak was leveled, then-president Johanne Chamberlain declared that the electricity on the two sides of campus should be connected. The heroic men and women of physical plant took two years to dig a small conduit, and inserted 501 identical wires between the two sides. Unfortunately, they neglected to leave any indication of which wire ends on the north side corresponded to which ends on the south side. The mountain settled on top of the tunnel, and there was no way to remove the wires. A new tunnel would take another two years to dig. And, since this was in the days before telephones or helicopters, the only way to figure out which south-side ends corresponded to which north-side ends was to send an electrical signal through wires on one side, and then travel to the other side to see which wires were live on the other end.

Your challenge is to travel back in time to help the workers identify the ends of the wires on each side. You must minimize the number of trips required across Thompson peak in order to label each wire, from 1 to 501, with matching numbers on each side. You are permitted to connect wires on one side or the other. Connected wires will conduct electricity through the connection. But, you have only one voltage source. You can connect or disconnect as many wires, and as often, as you please. Solutions must contain complete instructions and the minimum number of trips.

Bonus question: What would the minimum number of trips be if there were 502 wires?