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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ This must be a duplicate $\endgroup$– Dr XorileAug 25, 2019 at 14:46
-
$\begingroup$ What counts as one wiring? If I connect end A1 to A2 and B1 to B2 is that two and then measure the resistance between A1 and B1, is that one wiring or two? $\endgroup$– HelenaAug 25, 2019 at 15:33
-
$\begingroup$ Possible duplicate of Labeling wires in a bundle (@DrXorile) $\endgroup$– boboquackAug 26, 2019 at 4:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.