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?

4 tests suffice. Connect the 12th wire permanently to the - terminal of the battery.  Test 1: connect the 1st, 3rd, ..., 11th wires to +. Test 2: connect the 1st,2nd,5th,6th,...,9th,10th to +. Test 3: connect the 1st,2nd,3rd,4th,9th,10th,11th to +. For the last test, connect the first 8 to +. The 12th wire is identified in the first test, so only the other 11 need to be identified. Each of the first 11 has a unique 4-tuple of test results, with, for example, (0,1,1,1) indicating the wire connected to + on the second, third and fourth tests and not on the first test (i. e., the 2nd wire).

Posted by Richard on 2004-06-30 14:42:15