There are twelve wires that run from your cellar to your roof. Unfortunately on their journey they could be randomly mixed up, so you can't tell which cellar wire-end corresponds to which roof wire-end. You have a battery and a light bulb, and you can temporarily twist wires together. You can also travel from the cellar to the roof and back again any number of times. Thus you can construct circuits and test the wires at either end in order to deduce what is going on. But it’s a long way to the roof. So, starting at the bottom, what is the minimum number of journeys you have to make, in order to work out exactly which wire-end in the cellar corresponds with which wire-end on the roof?

Three to five trips depending on whether you count the initial trip to the attic or the final exit from the cellar.

Label the wires in the attic A through L.

Tie together the attic ends of A and B.  Likewise connect the top ends of C, D and E all together, and group F, G and H likewise.  Finally tie together the top ends of I, J, K and L.

In the basement use your battery and bulb to test which two ends connect only to each other, label the ends 2x and 2y.  Similarly find a set of four that mutually all connect and label these ends 4w, 4x, 4y and 4z.  Also find two sets of three that mutually connect and label one set 3Ax, 3Ay and 3Az, and the other set 3Bx, 3By and 3Bz.

Still in the basement, connect (tie together) 2y to 3Ax and 3Ay. Connect 3Bx and 3By.  Also connect 4w with 4x.

Back in the attic:
Untie what you had tied before and start testing with your battery and bulb:

Of A and B, one will not connect to anything--that's the one that corresponds to 2x; the other corresponds to 2y.

The one of A and B that does connect will connect to two from C,D and E or two from F, G and H.  The other from the given group of three corresponds to 3Az.  The ones that do match in that group of three correspond to 3Ax and 3Ay, but we don't know yet which is which.

The other group of three at the attic end corresponds to 3Bx, 3By and 3Bz, and in particular, the one that doesn't connect up with anything corresponds to 3Bz. The ones that do match in that group of three (they connect to each other) correspond to 3Bx and 3By, but we don't know yet which is which.

The two in the group I,J,K,L that connect to each other correspond to 4w and 4x, but we don't know the order; the other two correspond to 4y and 4z and again we don't know the order.

So far we've matched up 4 (the ones that correspond to 2x, 2y, 3Az and 3Bz), and have four pairs (two of C,D,E; two of F,G,H; two pairs from I,J,K,L) that we've matched up with identified pairs in the cellar. Connect four ends together, one from each pair: say the earlier in the alphabet of each.

Then go down to the basement:
Remove the previous tyings.

Use the battery and bulb to see which four connect.  They are the ones that correspond to the earlier one in the alphabet in the attic, from each previously identified pair.

You have now identified all the matching ends, after having done work in the attic, the cellar, the attic and the cellar.  This counts as anywhere from 3 to 5 trips depending on whether you count the initial trek to the attic and/or the final exit from the cellar.

Posted by Charlie on 2004-06-30 14:47:50