0

Is there a mathematical way to know the answer? (or you can do it only by trial and error). Could you prove that it is possible or impossible mathematically?

salsabil.raisa
  • 13
  • 5
  • 1
    By knowing the formulae? – Bradman175 Jan 06 '17 at 07:31
  • What is the answer? @Bradman175 – salsabil.raisa Jan 06 '17 at 07:32
  • Read my answer. – Bradman175 Jan 06 '17 at 07:43
  • 1
    You should ask this question on Mathematical Forum. I am afraid it will boils down to some theory of approximation of convex manifolds, or something of this sort. – Ale..chenski Jan 06 '17 at 08:05
  • @DaveTweed-- the Euclidean Algorithm will give you *an answer*. The request was for a *minimal answer* – Scott Seidman Jan 06 '17 at 14:24
  • @ScottSeidman: the request is for a *mathematical* solution. I'm not aware of any single algorithm that always finds an optimal solution. – Dave Tweed Jan 06 '17 at 15:27
  • @DaveTweed -- "least number" is certainly in the title. Might still need closing, but its not a dup – Scott Seidman Jan 06 '17 at 15:40
  • I did not any optimal solution. I wanted the least solution. So, this can never be a duplicate. @DaveTweed – salsabil.raisa Jan 06 '17 at 16:31
  • In that case, this isn't an EE question at all. You need to ask this on a mathematics site. It can be readily shown that the accepted answer is optimal for the specific problem that you posed, but if you're looking for a rigorous mathematical proof about whether an optimal algorithm exists for the general problem, I doubt that anyone here has the chops for that. – Dave Tweed Jan 06 '17 at 16:44
  • @DaveTweed ah well, it's not that hard. Basically, you can tree-build your way out of this by starting with a single resistor, and building all possible circuits you can build from that circuit by adding a single resistor. Stop if you find a 5Ω solution. If you don't, continue to find all possible circuits that can be generated by adding another resistor to the circuits you've found in the last step. Rinse, repeat. If you're good, have a way of purging duplicates. You're guaranteed to find the smallest possible solution that way, but it'll be a slow search, basically a brute force approach – Marcus Müller Jan 06 '17 at 17:55
  • @MarcusMüller: Yes, you can always do a brute-force search, but I think the OP is looking looking for an algorithm to *construct* an optimal solution directly. – Dave Tweed Jan 06 '17 at 18:18
  • well, what I described *is* a constructive algorithm! – Marcus Müller Jan 06 '17 at 18:19
  • (other than that, the problem is as far as I can tell actually NP-hard, since it involves finding a factorization of a rational number, which is of the same complexity as factorizing natural numbers, and that is as far as we can tell today hard, in fact, it's so hard that we base a lot of our encryption theory on that complexity. In other words: If you can't find a solution by looking sharply, trying out all the combinations in a sensible order is the best you can do to solve the problem or even estimate how long it'll take to solve it) – Marcus Müller Jan 06 '17 at 18:21
  • @MarcusMüller: No, you described a way to construct candidate solutions that need to be tested for correctness. That is the definition of a search. Compare to the Euclidean algorithm, which moves at every step directly toward a solution. – Dave Tweed Jan 06 '17 at 18:24
  • What IS your problem??? @DaveTweed – salsabil.raisa Jan 07 '17 at 16:06
  • I don't have a problem. In fact, I have a solution, which you will find if you follow the link above. The extensive discussion, both here and there (also [here](http://electronics.stackexchange.com/a/202027/11683)), shows that there is no general *constructive* algorithm for the general case. As I said before, if you want a more rigorous mathematical treatment of the topic, you'll have to take it to a mathematics site. I could reopen the question as "not strictly a duplicate", but then I'd have close it again anyway because the underlying more general question is off-topic here. – Dave Tweed Jan 07 '17 at 16:53

3 Answers3

6

I never faced this particular question before. But faced with it now, I'd start out (after mentally verifying that a bridge arrangement would be pointless -- and it is) by asking myself what, in parallel with \$8\:\Omega\$ would yield \$5\:\Omega\$?

It turns out that the answer is \$13\frac{1}{3}\:\Omega\$.

Then I'd wonder about what might make that. Well, if I had \$8\:\Omega\$ already, then I'd need another \$5\frac{1}{3}\:\Omega\$ to get that total. Well, luckily \$16\:\Omega\vert\vert 8\:\Omega\$ makes that.

So that's my answer. It's not a general purpose algorithm to get from \$X\$ to \$Y\$, exactly. But it's a thought process to find an answer here. And it suggests an algorithm (discussed below.)

The answer I'd give is:

$$\left(\left(\left(8\:\Omega+8\:\Omega\right)~\vert\vert~8\:\Omega\right)+8\:\Omega\right)\vert\vert ~8\:\Omega$$

or,

schematic

simulate this circuit – Schematic created using CircuitLab

The algorithm might be to realize that 8 and 5 are relatively prime and that it is likely that you'll need to reach their product, \$8\cdot 5=40\$, in order to find an answer. Intuitively, this makes some sense thinking that you are probably looking for a least common multiple of the two values. So it does strongly suggest that 5 resistors will be the minimum you can use here.

jonk
  • 77,059
  • 6
  • 73
  • 185
  • I did not understand the algorithm part. – salsabil.raisa Jan 06 '17 at 08:47
  • @Mathematics It comes from the idea of conductance, which is \$\frac{1}{R}\$. You are combining such fractions. So you need to look for the LCM (I think.) However, I didn't actually develop an algorithm there. Just pointed in a direction where I think one might be found. – jonk Jan 06 '17 at 08:48
  • Good answer. A more formal description of the algorithm can be found [here](http://electronics.stackexchange.com/a/69036/11683). – Dave Tweed Jan 06 '17 at 12:28
  • @DaveTweed Yes, I was thinking about the use of continued fractions, in fact. Nice to see it discussed by you. – jonk Jan 06 '17 at 19:27
  • +1 to your bank. What about more convoluted interconnect topologies? Like 3D cubes, with horizontal cross-links? – Ale..chenski Jan 06 '17 at 23:38
  • @AliChen: They exist, but the Euclidean algorithm won't find them. Consider a balanced Wheatstone bridge (four equal resistors), with a fifth resistor across the middle. The resistance from top to bottom is simply R, because the middle resistor carries no current. Now unbalance the bridge by adding a sixth resistor in series with one leg. The resistance becomes \$\frac{13}{11}R\$. The Euclidean algorithm will come up with a network of eight resistors to produce this value. – Dave Tweed Jan 07 '17 at 17:05
  • @DaveTweed I'd considered the Wheatstone. But a minimum is 5 resistors so I dropped the idea right immediately. Still, the bridge resistance has a nice symmetry for computing it. It's the sum of all _interesting_ (excepting the two cases where they all share the same node) products of 3 resistors divided by the sum of all _interesting_ products of 2 resistors (excepting the two cases where they simply bridge across the middle resistor.) Your case has the 2R leg appearing 5 times in the numerator and thrice in the denominator, so \$\frac{2\cdot 5+3}{2\cdot 3+5}R=\frac{13}{11}R\$. As you say. – jonk Jan 07 '17 at 19:10
1

It's possible but I cannot tell you with the fewest resistors possible.

16 ohm parallel to 8 ohm would get you close at 5,3 ohm. \$5,3 = R||2R\$. Depending on the tolerance it can already be a good answer.

Series: \$Rt = R1 + R2\$

Parallel: \$Rt = \frac{R1 \cdot R2}{R1 + R2}\$ also written as \$Rt = R1||R2\$

The easiest and exactly 5 is \$Rt = R||R + R||R||R||R||R||R||R||R\$ where R = 8 ohm. 2R parallel gives R/2. 8R parallel gives R/8. In this case a total of 5 ohm.

I would write a program to check the first 100k combinations of parallel and series resistors.

My best with trial and error is. \$5,05 = R||3R||4R\$

Dave Tweed
  • 168,369
  • 17
  • 228
  • 393
1

You can find it mathematically. It only works for rational numbers though.

Note that this does not mean it's the solution with the least amount of resistors required.

You first need to find the highest number that when multiplied by any positive integer, it can equal both numbers.

So far for 8 and 5, it's only 1.

For 8 to reach 1. You need 8/1 which is 8.

Thus you put 8 resistors in parallel.

Now you have this.

enter image description here

Then you need to put these jumble of resistors in series to add to the amount of resistance you want. Since each jumble of resistors is 1, 5/1 is 5 so we need 5 jumbles of them.

Now you have this abomination.

enter image description here

Congrats you got your desired resistance... now count them up yourself.

Bradman175
  • 1,181
  • 12
  • 22
  • Obviously your solution is not optimal, since one simple answer is "10", not 40. The other answer is "13". – Ale..chenski Jan 06 '17 at 08:01
  • Using your algorithm it is obvious that the problem has infinite number of solutions. So it is quite natural to ask for a minimum. – Ale..chenski Jan 06 '17 at 08:08
  • What if the question asked the least possible number of resistors? – salsabil.raisa Jan 06 '17 at 08:27
  • 3
    @Mathematics Then you'd better ask that on a math site, as Ali suggested. Because the most reasonable solution an electronic engineer can come up with is: "go buy a 5 ohm resistor, for christ sake!". – dim Jan 06 '17 at 08:35
  • It is possible to use less resistors. If you made 1 Ω from 8 parallel resistors, you need to add 4 Ω to get 5 Ω. It is easy to get 4 Ω, just two 8 Ω resistors in parallel. That is one solution using 10 resistors, but a solution with only 5 resitros was shown here too. – Uwe Jan 06 '17 at 13:57
  • Note that a 5x5 section of your matrix can be replaced by a single resistor. This leaves a 5x3 matrix. A 3x3 section of that can be replaced by another resistor, leaving a 2x3 matrix. Replace 2x2 of that by a third resistor, and you're left with 1x2, which is irreducible. Total of five resistors, same as the accepted solution. It turns out that this problem is isomorphic to the problem of tiling an arbitrary rectangle with squares. – Dave Tweed Jan 06 '17 at 14:08
  • @DaveTweed Beauty, Lego-man! This systematic approach has the smell of an optimal solution. Please consider offering it as a vote-able answer. Jonk's intuitive approach is impressive too, but he "lucked out". – glen_geek Jan 06 '17 at 15:11
  • @glen_geek: see the duplicate question linked above for my original answer. Also, it can be shown that this algorithm does not always find the optimal solution. – Dave Tweed Jan 06 '17 at 15:21