Sunday, May 11, 2014

Wire Connections

Problem

There are 66 wires connecting from the top floor to the ground floor. You can see the ends of the wires but you don't know which one on the ground floor connects to which one on the top floor. You can tie the ends of several wires together and test the connections at the other end by using a bulb and battery. For example, if you first tie wires A, B, and C together at the ground floor and then go up to the top floor, you will figure out that the bulb will light if you put it between A and B, A and C, or B and C. You can do the reverse thing by tying the ends at the top floor and test on the ground. Assume you start at ground floor with none of the wire tied, what's the minimum number of trips up and down you need to make before you can figure out all the connections from the ends on the top floor to the ends on the ground floor, which is a one-to-one mapping between them?

What happens if the number of wires is 67......

0 comments:

Post a Comment