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?

The answer is 19 trips.

Logic is as follows:

Mark two wires 1 and 2. Then connect both to the battery. Go up to the attic and find out which two wires turn the light on and label them 1 and two (this may take some time but it doesn't matter which one you label one and two). Then return back down stairs (trip two) and - keeping number 1 connected to the battery - attach a thrid wire (labeled 3) to the battery as well. Go up stairs and figure out which is wire three (thrid trip). By doing this, you will have determined which is wire 1 and which is wire 2. Go back downstairs (fourth trip) and attach wire four (labeled 4) to the battery. Then return upstairs (fifth trip) and repeat this process until you have the eleventh wire identified. That would be trip 6 - 19

Now you will have all twelve wires correctly identified in 19 trips

Posted by Ryan on 2004-10-20 04:55:41