15 wires
You have a cable running from your bedroom to the roof, and inside the cable, you have 15 identical-looking insulated black wires, but you don't know which is which.
You would like to figure out which of the 15 wires in your bedroom belongs to which of the 15 wires on the roof, but it's dangerous climbing out on the roof. So you would like to minimize the number of times you have to do that.
You are armed with
- an infinite supply of shorting devices which can short together as many cables as you like on either end of the cable,
- a potentiometer which can determine whether two wires connect.
So, for example, if you connect two wires together in your bedroom and climb up on the roof, your potentiometer will be able to detect which two wires you connected.
What is the fewest number of trips you'll need to make (that is, "round trips" to the roof and back to your bedroom) to identify all the wires correctly, i.e. which wire in your bedroom connects to which wire on the roof?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
You can do it in one trip as follows...
In your bedroom, short the wires together in five groups:
Then climb up on your roof.
Now, you can identify the five groups since there are a different number in each group, so label the wires accordingly: A1-A5, B1-B4, C1-C3, D1-D2, and E1, and short together the following groups:
Now, when you return to your room, you know the letter of each wire (by how they are currently shorted in your bedroom, and you can determine the group by how they are now shorted on the roof, so you label them all accordingly, and wallah... Only 1 trip required.