The Hamilton Puzzler The Continental Conundrum The Befuddled Blue
Solutions Page for Logic Puzzle #3: Wires
Click to go to:
The winners of the third logic puzzle contest are:
Matt Eichenfield '09 and Brendan Conway '09
The next puzzle will appear on February 13.
Puzzle #3 (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?
The Puzzler's solution:
1. Arbitrarily, we’ll start on the south side. Choose one wire, and label it #1. Pair up all other wires, leaving wire #1 unconnected. Label each pair, but not with numbers. Pairs of letters, e.g. AA, AB, AC...BA, BB, BC.... will provide enough labels.
2. Travel to the north side.
3. Determine the lone, unconnected wire by attaching the voltage source to each wire in turn, until you find one that does not electrify any other wire. Label it #1.
4. Pick any other wire, label it #2.
5. Find the wire to which #2 is connected. Label it #3.
6. Repeat steps 4 and 5, increasing the label numbers by twos, until all wires are numbered.
7. Connect #1 to #2, #3, to #4, and so on, leaving #501 unconnected. Notice that all the wires are now connected, so that if you send electricity through #1, it will pass through all the wires.
8. Travel to the south side.
9. Disconnect all connections, but leave the letter labels in place.
10. Send electricity through wire #1. Wire #2 will now be live. Label it #2.
11. Find the wire which had previously been paired with Wire #2. Label it #3.
12. Repeat steps 10 and 11, increasing label numbers by twos, until all wires are numbered.
Note, this solution only works for odd numbers of wires, since it requires us, at step 3, to determine the lone, unconnected wire. To use this method to label 502 wires, I would need an extra trip to determine a starting point.
Click here for Peter Rabinowitz's solution, which works in two trips, for both odd or even numbers.
Peter Rabinowitz's solution, which works for 502 wires as well as for 501:
I’ll do it in two trips--regardless of the number of wires. I begin by connecting pairs of wires on side A. If I have one extra wire, fine. I can label that with the last number, whatever it is.
I then go to side B. I can now reconstruct all the pairs, because I can send voltage through a wire and--assuming that I have the right kind of voltage detection equipment--see what other wire it comes through. (I can also figure out which is the wire that doesn’t have a connection at the other side). I now number all of my wires on side B. Arbitrarily choosing one wire as wire 1, I assign its pair number 2. I then aribitrarily choose a wire as 3 and assign its pair the number 4. And so on. I then connect 2 to 3 and 4 to 5. I now have, in effect, a single long wire (and perhaps a short wire that I know is the last, extra wire). I attach the voltage source to point 1 and go back to the other side.
On side A, I disconnect all the pairs (but remember how they were paired). There will now be evidence of an electrical charge only at the end of the first wire. When I find that wire (which I can now label 1), I reconnect it to its pair (which will be wire 2). I then see where the voltage is coming to, and that will be wire 3. I continue the process until I have found the entire route.
|