You have a cable with 3 wires inside.

If they were color coded like this, it would be easy to tell which wires are which.

However, suppose they
**
aren't
**
color coded. If all you have is a potentiometer, which can detect if two ends of a wire are connected or not, what is the minimum number of times you would need to hook up the potentiometer in order to guarantee the determination of which wires on one end connect to which wires on the other end?

**
Clarification:
**
No matter what the result of your measurements (i.e. assuming the worst case scenario), what is the minimum number of measurements that guarantees that you can determine the connectivity of all three wires?

2
3
4
5
6
7

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

Interesting approach, Ajinkya! I wonder if a similar method could be used to determine the connectivity of 4 wires with 5 moves...

Geoff Pilling
- 4 years, 3 months ago

Upvoting because modern art

Adam Hufstetler
- 4 years, 3 months ago

First off, there are six different ways the wires could be connected up, and every time you make a measurement, you get one bit of information (connected or not connected).

So, the lower bound on the number of times you'd need to hook up the potentiometer is:

$\lceil \log_2(6) \rceil = 3$

And, you can do it with three measurements as follows:

Call the wires on one end A1, A2, and A3. And, call the wires on the other end B1, B2, B3.

1) Measure A1 vs B1:

```
If they connect:
2) Measure A2 vs B2
If they connect: A1-B1, A2-B2, A3-B3
If they don't: A1-B1, A2-B3, A3-B2
If they don't:
2) Measure A2 vs B1:
If they connect:
3) Measure A1 vs B2:
If they connect: A1-B2, A2-B1, A3-B3
If they don't: A2-B1, A1-B3, A3-B2
If they don't:
3) Measure A2 vs B2
If they connect: A1-B3, A2-B2, A3-B1
If they don't: A1-B2, A2-B3, A3-B1
```

If you liked this problem, try its harder counterpart, this one.

3 Helpful
0 Interesting
0 Brilliant
0 Confused

The question asks for the MINIMUM number of tests. This must be two. The first pair you test you test you get quite lucky (1/3) and find continuity you mark that pair. The second pair you test you again get fairly lucky (1/2) and get continuity. The remaining pair will also have continuity. I agree that in any circumstances the maximum is three tests to completely identify all the wires, assuming there is no break in any of the wires.

Ed Sirett
- 4 years, 3 months ago

Log in to reply

Agree, the wording of the question specifies minimum.

Brad Simmerman
- 4 years, 3 months ago

Log in to reply

I agree. If you check the first and get a match; check the second and also get a match then you are done. No need to check the final one as they must also match!

Andrew Eardley
- 4 years, 3 months ago

The intent of these type of questions is to have us find the minimum number that guarantees identification, but you're right, as presently worded this is not explicit and thus can be interpreted as you have done.

@Geoff Pilling Perhaps to address Ed's concern the wording near the end of the text could be "... in order to guarantee the determination of which wires on one end ....".

Brian Charlesworth
- 4 years, 3 months ago

Log in to reply

Good point... Lemme see if I can update the wording to make it a bit clearer...

Geoff Pilling
- 4 years, 3 months ago

Log in to reply

@Geoff Pilling – There... I've tried to clarify the question a bit... Any ideas on what else I might be able to add?

Geoff Pilling
- 4 years, 3 months ago

Log in to reply

@Geoff Pilling – Looks good. You'd need to find some high-priced lawyers to quibble about this now. At least no one yet has found a $guaranteed$ method of identifying the wires in 2 measurements.

Is there a general formula for the guaranteed minimum for $n$ wires on either side? We might be able to use some tricks for larger $n$ .

Brian Charlesworth
- 4 years, 3 months ago

Log in to reply

@Brian Charlesworth – Good question... I was wondering that myself... For example for n=4, 4! = 24, so theoretically we should be able to do it with 5 testings (Since 2^5 = 32 > 24). However, I haven't thought of a way to do it with 5 testings yet. I can do it with 6... Maybe you need to short some on one end?

Geoff Pilling
- 4 years, 3 months ago

Log in to reply

@Geoff Pilling – I can't get it down to 5 either, and shorting doesn't seem to help at all. The general formula appears to be $\displaystyle\sum_{k=1}^{n-1} k = \dfrac{n(n - 1)}{2}$ .

Brian Charlesworth
- 4 years, 3 months ago

Log in to reply

@Brian Charlesworth – OK, Brian, you got me thinking, and I came up with this . Enjoy! :)

Geoff Pilling
- 4 years, 3 months ago

While I like this problem, it flies in the face of the "measure twice - cut once" philosophy. What if the potentiometer doesn't even work?

Ken Hodson
- 4 years, 3 months ago

Log in to reply

Haha.... Yup! Any good electrician would definitely connect it one more time to make sure! :0)

Geoff Pilling
- 4 years, 3 months ago

Log in to reply

Quite so, in fact it is a requirement (here in the UK) to check the tester before and after making measurements.

Ed Sirett
- 4 years, 3 months ago

Thanks for the clarification update. In practice, this is something I do from time to time diagnosing faults on heating controls (where there may be an inaccessible join and different colours used at some point in the cable). I would tend to use the tactic of joining a pair at one end and finding the pair at the other end.

Ed Sirett
- 4 years, 3 months ago

Nice solution layout. I somewhat anxiously chose $3$ , as I was worried that there was some trick you had up your sleeves to get it down to $2$ , but your added 'Assumption' made me reasonably sure of the answer. If the 'Assumption' condition were not in effect, is there some trick, (crossing wires or some such thing), to get it down to $2$ measurements?

Brian Charlesworth
- 4 years, 3 months ago

Log in to reply

I considered not including the assumption, since I think you don't need it.

Since there are 6 possible outcomes and even by tying wires together the most you will get are 2 bits of information, I'm reasonably sure there are no tricks you can use...

Do you suppose I should remove it?

Geoff Pilling
- 4 years, 3 months ago

Log in to reply

I've tried to come up with a trick to no avail so it's probably safe to remove it, (not that I'm an electronics whiz or anything). Not having it might prompt people to be creative, which makes the question more fun to work on. And if someone does come up with some trick then the more power to them, and we learn something in the process as well.

Brian Charlesworth
- 4 years, 3 months ago

Log in to reply

@Brian Charlesworth – Done. I've taken it out... Now lets see if anyone comes up with anything really tricky... :-)

Geoff Pilling
- 4 years, 3 months ago

@Brian Charlesworth – I much prefer an answer that could (potentially) be wrong, over a problem where the answer is guaranteed to be correct, if the former makes for a more interesting question! :-)

Geoff Pilling
- 4 years, 3 months ago

@Ken Hodson , The best way is to get your assistant to make and break the connection at one end and then find the pair where the tester is showing on/off/on/off. Or on your own with an audible tester you can connect the tester to one pair and then find which pair it is from the other end.

Ed Sirett
- 4 years, 3 months ago

×

Problem Loading...

Note Loading...

Set Loading...

For showing that 2 is the lower bound, see the other solution. For seeing if it is acheivable, Here is 1 easy possible answer Connect $A_1$ and $A_2$ with each each other and connect $B_1$ and $B_2$ to the potentiometer.

Case 1: Current flows. $A_3$ and $B_3$ Are corresponding ends. Check $A_1$ and $B_1$ , If they connect, or do not connect , either way We have anwer in 2 moves.

Case 2: Current does not flow. Check $A_3$ with $B_1$ . If it does connect, we know that they are corresponding ends . If they do not, $A_3$ and $B_2$ are corresponding ends . Check $A_2$ and $B_3$ If the match or do not, either way we have Answer in 3 moves