Source

I got this problem from Rustan Leino, who learned about it from Greg Nelson, who phrased it in terms of a tall building and elevator rides. Rustan switched it to a mountain and helicopter rides, which is the way Lyle Ramshaw had heard the problem and which more forcefully emphasizes the price of each ride.

I solved it and wrote up my solution.

Problem

You're an electrician working at a mountain. There are $N$ wires, where $N > 2$, each of which runs from one side of the mountain to the other. The problem is that the wires are not labeled, so you just see $N$ wire ends on each side of the mountain. Your job is to match these ends. In other words, you need to label the two ends of each wire in the same way and use different labels for different wires.

To figure out the matching, you can twist together wire ends, thus electrically connecting the wires. You can twist as many wire ends as you want, into as many clusters as you want, at the side of the mountain where you happen to be at the time. You can also untwist the wire ends at the side of the mountain where you're at. You're equipped with an Ohm meter, which lets you test the connectivity of any pair of wires. However, it's only an abstract Ohm meter, in that it only tells you whether or not two things are connected, not the exact resistance.

You are not charged [no pun intended] for twisting, untwisting, labeling, and using the Ohm meter. You are only charged for each helicopter ride you make from one side of the mountain to the other. What's the best way to match the wires?

Hints

- There's a way to do it with just two helicopter rides.
- Start by figuring out a solution for when $N$ is odd. Then adapt it to even values of $N$.

Solution
Reveal

There are separate, though similar, solutions for when $N$ is odd and even. In either case, only two helicopter rides are required.

Label one of the wire ends $1$, then arbitrarily pair up the remaining wires and twist together each pair of wires. Then, take a helicopter ride to the other side of the mountain.

Once there, use the Ohm meter to find all pairs of wires that are connected with each other. Label the one unpaired wire $1$. Pick an arbitrary pair of connected wires, label them $2$ and $3$, and twist the $1$ wire to the $2$ wire. Then, pick another arbitrary pair of unlabeled connected wires, label them $4$ and $5$, and twist the $3$ wire to the $4$ wire. Continue this way until you pick the final pair of unlabeled connected wires, label them $N-1$ and $N$, and twist the $N-2$ wire to the $N-1$ wire. Leave the $N$ wire untwisted. Then, take a helicopter ride back to the original side of the mountain.

For each pair of twisted-together wires you see there, untwist them but keep them near each other so you can remember they used to be twisted together on this side. Thus, the only connections remaining between wires correspond to twists on the other side of the mountain. Use the Ohm meter to find all those connected pairs of wires, and label the one unpaired wire $N$.

Next, find the wire connected to the one labeled $1$, and label it $2$. Find the wire that used to be twisted together with $2$ on this side, and label it $3$. Fnd the wire currently connected to $3$ and label it $4$. Find the wire that used to be twisted together with $4$ on this side, and label it $5$. Continue this way until you've labeled all the wires.

Arbitrarily pair up all but two of the wires and twist together each pair of wires. Then, take a helicopter ride to the other side of the mountain.

Once there, use the Ohm meter to find all pairs of wires that are connected with each other. Label the two unpaired wires $1$ and $N$. Pick an arbitrary pair of connected wires, label them $2$ and $3$, and twist the $1$ wire to the $2$ wire. Then, pick another arbitrary pair of unlabeled connected wires, label them $4$ and $5$, and twist the $3$ wire to the $4$ wire. Continue doing this until you pick the final pair of unlabeled connected wires, label them $N-2$ and $N-1$, and twist the $N-3$ wire to the $N-2$ wire. Leave wires $N-1$ and $N$ untwisted. Then, take a helicopter ride back to the original side of the mountain.

For each pair of twisted-together wires you see, untwist them but keeps them near each other so you can remember they used to be twisted together on this side. Thus, the only connections remaining between wires correspond to twists on the other side of the mountain. Use the Ohm meter to find all those connected pairs of wires, and the two unconnected wires. One of those unconnected wires was never twisted with another wire on this side of the mountain; label that one $N$ and the other currently-unconnected wire $N-1$. There are two wires that were never twisted on this side of the mountain, with one now labeled $N$; label the other one $1$.

Next, find the wire connected to the one labeled $1$, and label it $2$. Find the wire that used to be twisted together with $2$ on this side, and label it $3$. Find the wire currently connected to $3$, and label it $4$. Fnd the wire that used to be twisted together with $4$ on this side, and label it $5$. Continue this way until you've labeled all the wires.