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?

(In reply to solution in... by Charlie)

If, in the basement for the first time in my solution, instead of connecting 4w and 4x together, you tie 4w with 2y (as well as the 3Ax and 3Ay to which 2y already was connected), and tie 4x with the 3Bx and 3By already stated, and tie 4y with 2x, then when you get to the attic, the one of the group I,J,K,L that doesn't match anything will correspond to 4z.

Also the identification of A and B with 2x and 2y will change.  The one that connects with two of a group of 3 is 2y and whichever if I,J,K,L also connects is 4w, while the one that matches only one of I,J,K,L is 2x, and the one it matches with is 4y.  The one of I,J,K,L that matches with one of a group of 3 but not with A or B is 4x.

This way it's 3 locations of work, and thus 2 through 4 trips depending on whether you count the first entry and last exit.

Also, I see it's the roof, not the attic.  So rather than substitute roof for attic, actually substitute roof for cellar and cellar for attic.  That way,there's work in the cellar, the roof and then the cellar again, so there's only one trip to the roof and back, which is presumably harder to get to than the cellar.

Posted by Charlie on 2004-06-30 15:27:53