wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Infinite Resistor Network
        
(Message started by: william wu on Nov 21st, 2002, 2:55am)
Title: Infinite Resistor Network
Post by william wu on Nov 21st, 2002, 2:55am
Imagine an infinitely extending grid of squares. Between every two adjacent intersection points is a resistor of 1 ohm. Compute the resistance between two adjacent intersection points.
Title: Re: Infinite Resistor Network
Post by SWF on Nov 22nd, 2002, 5:29pm
Superimpose these two ways of applying current to this circuit:

Case 1:  Force 1 Amp into the circuit at point A while holding voltage zero at infinity.  By symmetry, 0.25 Amp flows through the resistor between A and B (going from A toward B).

Case 2: Take 1 Amp out of circuit at point B while holding voltage zero at infinity.  By symmetry, 0.25 Amp flows through the resistor between A and B (going from A toward B).

Superimposing these two situations gives 0.5 Amp flowing through the resistor between A and B for the case of 1 Amp into the circuit at A and 1 Amp out of the circuit at B.  So voltage difference between A and B is 0.5 Volts =0.5 Amp* 1 Ohm.  Since 1 Amp flows through the whole circuit, the equivalent resistance is 0.5 Volts/1 Amp= 0.5 Ohm.
Title: Re: Infinite Resistor Network
Post by Icarus on Nov 25th, 2002, 8:05pm
That is sweet. Much easier than the brute force method I was attempting. There is a mathematical objection to it, in that it assumes without proof that it is possible to force 1 amp into (or out of) the circuit at a point while holding infinity at zero voltage. But physicists are accustomed to ignoring such niceties.
Title: Re: Infinite Resistor Network
Post by James Fingas on Nov 26th, 2002, 5:24pm
A very beautiful solution. I was stuck in the same thought process as Icarus. I guess you can't shake that KVL/KCL method they teach you in school ...

I was also thinking about how it would be better if it was a continuous lump of metal rather than discrete resistors, because then we'd have a nice dipole, without realizing that of course a dipole is two monopoles superimposed near each other. And being somewhat blockheaded, I'm sure I would have integrated to infinity instead of doing something so thoughtful as SWF has done here ... doh!
Title: Re: Infinite Resistor Network
Post by Icarus on Nov 27th, 2002, 11:38am
First: You cannot force 1 amp into the system while holding infinity at zero volts. The resistance between any point and infinity is infinite. A quick heuristic way of seeing this is to pretend that each square centered at the point is a point itself. There are 4 1-ohm wires between the point and the first square: Resistance = 1/4. There are 12 wires between the first and second square. Resistance =1/12. In general there are 4n+4 wires between the nth and (n+1)th squares. So the total resistance out to infinity is at least approximated by the harmonic series SUMn 1/(4n+4), which diverges.

Second: I withdraw my mathematical objection to SWF's tactic. Despite what I've said above, it is still mathematically sound (or at least can be made that way with a few details). But I will not say why. After all, this is a puzzle site!
Title: Re: Infinite Resistor Network
Post by James Fingas on Nov 27th, 2002, 12:01pm
I doesn't matter whether or not you hold infinity at a finite voltage. It's infinitely far away--why would you care what voltage it's at? Just like I don't care how foul-mouthed Willy Wutang's overseas girlfriend is--I can't hear her here ;)

To satisfy yourself logically, you could take your reference voltage at point B. Then you simply get 0.25V at point A from forcing 1A in, and 0.25V at point A from drawing 1A out, for a grand total of 0.5V. Infinity never comes in to play.

If you want to deal with infinity, just notice that as you go to infinity, the two voltage distributions cancel each other out (as will the effects of any dipole). Even though infinity is at an infinite potential in each separate case, in the superposition, it collapses to a finite number (the average of the potentials of A and B).
Title: Re: Infinite Resistor Network
Post by william wu on Dec 16th, 2002, 10:58pm
To solve this problem, I was considering using a duality in computer science theory between resistors and random walks on graphs. This problem did not arise from such a context, but it's something that came to mind.

Consider a undirected connected graph, by which I mean a bunch of vertices connected by edges with no arrows. You start at one vertex. On every iteration, move to one of your immediate neighbors with equal probability. Keep moving like this forever. This process is termed a random walk. The hitting time Huv between two vertices is the expected number of iterations, or steps, you would take to reach vertex v starting from vertex u.

Very interestingly, it can be shown that


Huv + Hvu = 2mRuv


where m is the number of edges in the graph, and Ruv is the resistance between vertices u and v, where every edge is assigned a resistance of one Ohm. (Huv + Hvu is often referred to as the commute time Cuv, since you are starting at u and visiting v and then returning to u.) Thus, if we can solve for Huv and Hvu, we can find the desired resistance Ruv between two adjacent vertices on the grid-like graph.

However, it's a bit hairy. Since the graph is infinite, m = infinity. But also, Ruv = 0, since there exist an infinite number of paths to get from u to v. So I guess we have to look at progressively larger patches of the resistor grid, and show that as the size of the grid approaches infinity, the resistance somehow converges to a fininte value. I'm too lazy to carry this through now so if anyone wants to try it feel free; else maybe I'll try later.
Title: Re: Infinite Resistor Network
Post by Icarus on Dec 17th, 2002, 4:13pm
Okay, I'm a little confused here.

Quote:
But also, Ruv = 0, since there exist an infinite number of paths to get from u to v.

Is not finding the value of Ruv when u and v are adjacent the whole point of this puzzle? And is it not 0.5 Ohm, as SWF demonstrated?

And from James' last post:

Quote:
To satisfy yourself logically, you could take your reference voltage at point B. Then you simply get 0.25V at point A from forcing 1A in, and 0.25V at point A from drawing 1A out, for a grand total of 0.5V. Infinity never comes in to play.


No matter what, you cannot force a steady current in at any point of a circuit without pulling current back out somewhere.
Title: Re: Infinite Resistor Network
Post by william wu on Dec 17th, 2002, 6:25pm
Sorry, I erred. Yes, Ruv does converge to some positive value. It's the ratio of commute time over 2m which must converge to Ruv. Since Ruv approaches infinity, I guess the commute time must also ascend to infinity, but at a different rate. This isn't very intuitive to me though, because the vertices u and v are right next to each other, so you would think a random walk starting from u would not take terribly long to reach v.
Title: Re: Infinite Resistor Network
Post by James Fingas on Dec 18th, 2002, 7:12am

on 12/17/02 at 16:13:45, Icarus wrote:
No matter what, you cannot force a steady current in at any point of a circuit without pulling current back out somewhere.


Icarus, that is true. I am not saying that you don't take the current out somewhere. The current goes out somewhere in the neighbourhood of infinity. This doesn't change the solution, since you can still define the zero-voltage point at B. You just end up with a negative potential as you go farther away from A and B. As you go to infinity, the potential gets more and more negative without bound.

So the current is definitely going somewhere--we just don't have to care about what the potential is there.
Title: Re: Infinite Resistor Network
Post by Icarus on Dec 18th, 2002, 4:19pm
James: My point is that the .25 Amp current SWF calculates between A and B in each situation comes from the first situation being symmetrical about A, and the second being symmetrical about B. You can take the current out short of infinity in a symmetrical manner about A, and in one symmetrical about B. But you can't do it symmetrically about both. So when you add the A and B situations together, there will always be a dipole other than at A and B. As you stated in an earlier post, it is easy to see that this dipole goes to zero as you move it out to infinity, which is why I withdrew my objection. But you can't rigorously solve this way without taking the limit.
Title: Re: Infinite Resistor Network
Post by Chronos on Dec 19th, 2002, 11:49am
Why is it not possible to put current in without taking it back out?  You get a charge accumulation, but what's wrong with that?  If you don't want the charge accumulation to be too large, then you just don't leave the current running for a long time:  It doesn't have to be a steady-state situation.

Let me add, by the way, that I consider the solution extremely elegant, and I wish I hadn't read it so quickly.
Title: Re: Infinite Resistor Network
Post by Icarus on Dec 19th, 2002, 4:06pm
Yes, you can keep a 1 amp current going by steadily increasing the voltage, assuming there is some capacitance in the system. (Yes, all physical systems have capacitance, but hey, all physical systems are also finite!) However, in this case SWF's solution does not work! The charge distribution that you get from the situation for point A is not exactly opposite the charge distribution you get from the situation for point B. So when you add the two cases together you have extraneous charge distributed around the system, and thus the sum is not a solution to the actual puzzle.

And yes, despite my nitpicking, SWF's solution is extremely elegant!
Title: Re: Infinite Resistor Network
Post by HappyFunBall on Dec 21st, 2002, 9:58am
No matter how elegant the given solution is, you haven't justified just combining the two cases additively.  In fact, I don't think I'll buy that until I see an analytical solution that arrives at the same answer.  So let me throw one out...consider a half-infinite plane:


-o-o-o-o-o-o-
 | | | | | |
-o-o-A-B-o-o-
 | | | | | |



If the resistors along the top row have a resistance R (we can consider them all equal by symmetry), then we can find the resistance of segment AB.  Then we ask what value of R
makes AB's effective resistance also R, and we get R ~= 0.6757.  (Using the rules for resistances in series and parallel, and limits for infinite sequences of them)

So back to the original problem, we can look at it as an infinite ladder:


-o-o-X-o-o-o-
 | | | | | |
-o-o-Y-o-o-o-


Where the resistors along the top and bottom row are resistance R and the rungs are resistance 1.  So the effective resistance on segement XY (and any other in the network) comes out to ~ 0.50254 ohm.  Interestingly this is close to the other answer offered.

So, please let me know if you see any flaws in this, or how the earlier solution justifies adding both cases together simply.
Title: Re: Infinite Resistor Network
Post by Icarus on Dec 21st, 2002, 7:07pm
HappyFunBall:

Obviously your exposure to physics has been somewhat limited, since by physics standards SWF's solution as given is the very epitomy of rigor! ;)

The justification for adding together solutions lies in the linearity of the laws of electricity. To simplify matters, ignore for the time being my quibbling about infinite resistances, and assume that individual solutions for SWF's two situations exist. Now take the sum of the two solutions. That is, the voltage at each intersection is the sum of the two individual voltages, and the current in each wire is the sum of the individual currents. Here is the question: does this sum constitute a physically valid situation? But because the individual solutions satisfy Kirchoff's Laws and V=IR, it is easy to check that their sum does too. So it is physically valid, which means that the total resistance must be 0.5 Ohms as SWF said.

Now as for my quibble. Instead of taking the current out at infinity, ground the entire boundary of a square of side length 2D centered at A for the first situation. And a second square centered at B for the second situation. Now each situation is finite and it is possible to force 1 amp in or out of the circuit. Add these solutions together and you get one where the current enters at A and leaves at B, but nowhere else except at the boundaries of the two squares where the currents entering and leaving do not quite cancel. This is the dipole that James refers to. It should be intuitively obvious and not hard (though somewhat messy) to actually show that these dipole voltages and currents -->0 as D --> oo. Thus SWF's solution is justified.

Concerning your own solution, you have not justified (and frankly I am doubtful) that your infinite ladder is equivalent to the infinite plane of resistors.
Title: Re: Infinite Resistor Network
Post by SWF on Dec 22nd, 2002, 3:27pm
HappyFunBall, you did not give much detail of your infinite series method or fully explain your reasoning, so it is hard to comment on the flaw in the method, except to say that it gives an incorrect answer.

What is the point of a quick an easy solution if it needs to be verified with a complicated solution?  At least with the easy way, I knew the answer quickly.  I am not sure exactly what HappyFunBall is trying to do, but some features of that method seem reasonable.  I think the method shown below is similar to what HappyFunBall had in mind, but it does not require infinite series.

In the infinite array below, there is a 1 Ohm resistor between all nodes.  The effective resistance of over any pair of adjacent nodes, such as AB and BC, must be the same by symmetry.

     |  |  |  |  |  |  |  |
 ...-+--+--+--+--+--+--+--+-...
     |  |  |  |  |  |  |  |
 ...-+--+--A--B--+--+--+--+-...
     |  |  |  |  |  |  |  |
 ...-+--+--+--C--+--+--+--+-...
     |  |  |  |  |  |  |  |
 ...-+--+--+--+--+--+--+--+-...
     |  |  |  |  |  |  |  |

The whole semi-infinte array above AB and below C may be replaced by a row of horizonal resistors of some unknown resistance R, as long as the value of R gives the remaining portion of the circuit the same effective resistance as it had before.  That leaves the following infinte ladder circuit (now it is infinite only in the horizontal direction), in which all horizontal resistors (--) now have resistance R, and all vertical resistors (|) are still 1 Ohm.

 ...-+--+--A--B--+--+--+--+-...
     |  |  |  |  |  |  |  |
 ...-+--+--+--C--+--+--+--+-...

It is required to find the value of R which makes effective resistance AB equal to that of BC.

First find the effective resistance from DE of the semi-infinite ladder, call this effective resistance L:

              D--+--+--+--+-...
                 |  |  |  |
              E--+--+--+--+-...

The three leftmost resistors (2 horizontal of resitance R and one vertical of resistance 1) are connected to a semi-infinite ladder just like the orginal.  The series and parallel resistor laws may be used to give L=2R+R/(1+L).  Solving for L gives L=R+sqrt(R2+2R).  Oops, I am using shooting-from-the-hip physics style math again by disregarding the negative solution L=R-sqrt(R2+2R).

Now look back to BC in the infinite ladder.  It is seen that effective resistance BC is equivalent to 3 resistors in parallel:  2 of resistance L and one of resistance 1 Ohm.  So effective resistance BC is L/(2+L).

To find effective resistance of AB, turn it into a finite circuit by replacing the semi-infinite ladders with L on either side:

                 A--B
               L |  | L
                 +--+

Forgive the picture, but A and B are each connected to the node below by a 1 Ohm resistor and an L Ohm resistor in parallel.  Being a simple finite circuit, effective resistance between AB is easy to find as R*(R+R*L+2L)/2/(R+R*L+L).

The effective resistances AB and BC must be equal, so set the two expressions for them equal.  For a second equation use the value for L in terms of R as given for the semi-infinite ladder circuit.  After some tedious algebra, those two equations may be solved for R and L.  I get a cubic equation in R with roots R=2/3 and R=-2 (double root).  Again, disregard the negative solution, so R=2/3.  Plugging into equation for L gives L=2.  Inserting those values of R and L into the effective resistance equations for AC and BC give the value 0.5 Ohms for effective resistance between adjacent nodes.
Title: Re: Infinite Resistor Network
Post by ZJ on Dec 23rd, 2002, 5:46am
Hmm...wonder if SWF is anyone I know...got a similar question last year in December, except that it had to do with a hexagonal resistor grid...the same method was used for the solution as well.

I believe there is another way of solving this rather easily, and without all that computer language stuff (for the square grid at least, not the hexagonal), but I can't recall it off-hand.  :P
Title: Re: Infinite Resistor Network
Post by jkang on Dec 12th, 2007, 2:25pm
This is an interesting thread.  I agree on the point of super-positioning the current-flows to arrive at the voltage drop across a resistor.

However, inspired by the latest XKCD strip, I'm curious as to how this problem could be solved for non-adjacent nodes.

Assuming point A sources 1A of current to infinity, one can really only know that each resistor connected to node A conducts an equal level of current.  Afterwards, the distribution fans out and intersects each other.

What's everyone's take on this?
Title: Re: Infinite Resistor Network
Post by SMQ on Dec 12th, 2007, 3:45pm
Not to in any way stife a potential discussion here, but the thread in the XKCD discussion forum (http://forums.xkcd.com/viewtopic.php?f=7&t=16104) contains some useful points, along with links to several relevent theory papers. :)

--SMQ
Title: Re: Infinite Resistor Network
Post by Immanuel_Bonfils on May 26th, 2008, 5:39pm
I wonder if SWF can hear me (or maybe someone else...).

Realy enjoyed your solution, but: I would be very grateful to be convinced that all the horizontal resistors have the same resistance; should'nt they change whyle comming near A,B,C?
Title: Re: Infinite Resistor Network
Post by Grimbal on May 27th, 2008, 8:52am
The resistances won't change.  The current will.
Title: Re: Infinite Resistor Network
Post by Immanuel_Bonfils on May 27th, 2008, 10:47am
We're speaking of equivalent resistance, independent if there is current or no; depends of the pair of nodes refered.
Title: Re: Infinite Resistor Network
Post by towr on May 27th, 2008, 10:53am

on 05/27/08 at 10:47:55, Immanuel_Bonfils wrote:
We're speaking of equivalent resistance, independent if there is current or no; depends of the pair of nodes refered.
Every pair of adjacent nodes is equivalent by translation and rotation, considering it's an infinite grid.
Title: Re: Infinite Resistor Network
Post by Immanuel_Bonfils on May 27th, 2008, 11:36am
Of course. But once choosed the pair (A,B) or (B,C), the other parts of the network change whith translation...


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board