100 Wires

From Raghu (raghu@diana.ics.uci.edu).

There is a very tall (say 150 storey) building, with no elevators.

In the ground floor, out of a hole in the wall, 100 copper wires are sticking out.

(picture of situation) In the top floor, out of a hole in the wall, the same 100 copper wires are sticking out. They are connected through some internal tubing hidden inside the construction of the wall.

Aim

You want to match the 100 ends on the ground floor with the 100 ends on the top floor. (Let us say you have adhesive tapes of 100 different colors to label the wires conveniently.)

Tools

You have a resistance meter which you can use as follows. Tie two or more wires on the ground (/top) floor together. Climb up(/down) the stairs to the top (/ground) floor. Measure the resistance between all pairs of wires there. Those wires which have a resistance of zero ohms may be inferred to be tied together at the other end. Those wires which have a resistance of infinity ohms may be inferred to be not tied (aka "open") at the other end. The resistance meter only gives a binary value - zero or infinity.

Aim (continued)

You have to minimize the number of trips up and down the stairs. Remember there are no elevators - you have to climb the stairs.

Think it over!

Then check the answer here.

Published in Njet Problem! collection 1996-05-29.