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 wireend corresponds to which roof wireend. 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 wireend in the cellar corresponds with which wireend on the roof?
Solution is two trips. Starting in the cellar, one trip up to the roof, and one trip back down.
In the cellar to start, twist the wires together in groups of 1, 2, 3, 4 and 2. Then lable them A, B1, B2, C1, C2, C3, D1, D2, D3, D4, E1, and E2 where the letters refer to wires which have been shorted together. Then go up to the roof.
On the roof, use the battery and bulb with all combinations of two wires to see which ones connect to which others down in the cellar. This will allow you to determine the five groups of 1, 2, 2, 3, and 4 connected in the cellar. Lable these wires A, G1, G2, H1, H2, I1, I2, I3, J1, J2, J3, and J4 respectively (note that wire "A" has now been identified in both locations). Now connect the wires up on the roof together in five groups of 2, 4, 3, 2 and 1 as follows:A+G1; G2+H1+I1+J1; H2+I2+J2; I3+J3; J4. Now go back down to the cellar.
Back in the cellar, disconnect all the junctions previously made. With the bulb and battery, find the wire that is shorted to A up on the roof  this wire must be G1 and will be labled in the "B" or "E" group in the cellar already ; for simplicity of discussion, lets assume it was B1. Now we can conclude that the other "B" group wire, B2, must connect to G2 on the roof. Now find the other three leads in the cellar that are shorted to B2(G2) on the roof. These will be one of the wires from each of the groups "E", "C" and "D", and will corespond to H1, I1 and J1 respectively; for simplicity of discussion, lets assume they were E1, C1, and D1. Now we can conclude that the remaining "E" group wire, E2, must connect to H2 on the roof. Now find the other two leads in the cellar that are shorted to E2(H2) on the roof. These will be one of the remaining wires from each of the groups "C" and "D", and will corespond to I2 and J2 respectively; for simplicity of discussion, lets assume they were C2 and D2. Now we can conclude that the remaining "C" group wire, C3, must connect to I3 up on the roof. Now find the other lead in the cellar that is shorted to C3(I3) on the roof. This will be one of the wires from the "D" group and will corespond to J3; for simplicity of discussion, lets assume it was D3. We can now conclude that D4 must connect to J4.
Now all connections between the cellar and roof are identified after only two trips. Of course they are still twisted together at the roof, so another trip may be required before plugging anything in...

Posted by stan
on 20040630 18:54:02 