15 wires

Logic Level 3

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?

×

Problem Loading...

Note Loading...

Set Loading...