Mfcttrf

There are ten wires that run underground across a river. Thus on each of the banks, there are ten ends of the wires. Unfortunately, given an end of a wire on this bank, one doesn't know which end on the other bank it corresponds to. Suppose that you an ohmmeter and a bunch of wires. (You can then, for example, connect two ends on side A of the river, and go to the side B and measure the resistance between every pair of ends to figure out which pair on side B corresponds to the pair that is connected on side A). What is the minimum number of crossings you need to make in order to figure out the matching ends of all the ten wires?

To solve the problem, at least I can cross

$7$ times.

And the strategy is:

- Connect two wires, says wire $1$ and $2$, then cross.

- Find the corresponding connected wires of $1$ and $2$. Connect another two wires $3$ and $4$, then cross.

- Find the corresponding connected wires of $3$ and $4$. Connect another two wires $5$ and $6$, then cross.

- Find the corresponding connected wires of $5$ and $6$. Connect another two wires $7$ and $8$, then cross.

- Find the corresponding connected wires of $7$ and $8$. You also know which two lefts are $9$ and $10$. Now, connect wires corresponding to $1$ and $3$, then cross.

- Find the corresponding connected wires of $1$ and $3$. You also know for sure about $1$, $2$, $3$, and $4$. Now, connect wires corresponding to $5$ and $7$, then cross.

- Find the corresponding connected wires of $5$ and $7$. You also know for sure about $5$, $6$, $7$, and $8$. Now, connect wires corresponding to $2$ and $9$, then cross.

- Find the corresponding connected wires of $2$ and $9$. You also know for sure about $9$ and $10$.

For improvement, if

I can pair more than once, after the fourth crossing, I can just pair $1$ and $3$, $5$ and $7$, also $2$ and $9$ simultaneously. So I can cross only $5$ times.

The absolute minimum is

2 crossings

First some observations:

Notice that when you connect ends of wires together, you are forming a partition. Notice that 10 is a triangular number, that is 10 = 1 + 2 + 3 + 4

The actual strategy:

So, first group wires into groups of one, two, three and four. Cross the river. You will be able to identify each group by continuity.

Next

Take one from each group, and form a group of four that way. Then take one from the remaining 3 groups, and so on. Once again, you have formed four differently sized groups, which will be identifiable once you cross the river. Additionally, since each group is formed by members of different groups, you will be able to tell which one is which.

Proof:

It obviously can't be solved with one crossing, as that would mean that you can connect the wires somehow on one end, and read something different on each wire.