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 re: Solution by Charlie)

I was thinking of having the battery in the basement and the bulb on the roof.  The bulb will only light between a wire connected to + and the 12th wire which is connected "permanently" to -. Since there is more than one wire connected to + in the 1st test, the wire that lights the bulb when the bulb is connected to it and to two different other wires must be the 12th wire.

I do not have my comment available for view as I am writing this, but if my recollection of it does not fail me (or my 5 years of study in electrical engineering), and barring some silly misprint, I think the bulb will light when connected between the 12th wire and any other wire connected at the other end to + on the battery. You do need the means to mark the wires with the test results, something the problem does not explicitly provide.

As far as counting trips goes, it takes four upward trips and three downward for my scheme.

Posted by Richard on 2004-06-30 16:20:08