96
$\begingroup$

I searched and couldn't find it on the site, so here it is (quoted to the letter):

On this infinite grid of ideal one-ohm resistors, what's the equivalent resistance between the two marked nodes?

Nerd Sniping

With a link to the source.

I'm not really sure if there is an answer for this question. However, given my lack of expertise with basic electronics, it could even be an easy one.

$\endgroup$
  • 4
    $\begingroup$ I instantly recognized the title from XKCD [Nerd Snipping is one of my favorites]. $\endgroup$ – Mateen Ulhaq Dec 20 '10 at 6:36
  • 2
    $\begingroup$ Discussion on meta: meta.physics.stackexchange.com/q/253 $\endgroup$ – Marek Dec 20 '10 at 8:35
  • 2
    $\begingroup$ The question @ m.SE... $\endgroup$ – user172 Dec 20 '10 at 10:49
  • 1
    $\begingroup$ @MarkEichenlaub Regarding your second comment: I don't have the time or will to detail every single result, but essentially there are three different problems addressed (adjacent, diagonal, and "knight's move", or even four if you count the general solution). The top solution is over 2800 words long, goes into much mathematical detail, and only solves the general diagonal problem. I feel the question still needs a concise, clear, organized answer that is easy to find. $\endgroup$ – Mark C Dec 23 '10 at 0:59
  • $\begingroup$ It is a duplicate, but it is too late to close; I'll call it a "good duplicate" and leave in peace. $\endgroup$ – user68 Jun 16 '11 at 10:05
47
$\begingroup$

Nerd Sniping!

The answer is $\frac{4}{\pi} - \frac{1}{2}$.

Simple explanation:

Successive Approximation! I'll start with the simplest case (see image below) and add more and more resistors to try and approximate an infinite grid of resistors.

Simulation results

Mathematical derivation:

$$R_{m,m}=\frac 2\pi \left( 1 + \frac 13 + \frac 15 + \frac 17 + \dots + \frac 1 {2m-1} \right)$$

$\endgroup$
  • 59
    $\begingroup$ +1, but it would be even better to outline the solution in the post so that people don't have to click a link to see how it's done. $\endgroup$ – David Z Dec 20 '10 at 2:12
  • 7
    $\begingroup$ The stuff on that math link is pretty complicated... Too much for mere inhuman lifeforms such as me. $\endgroup$ – Mateen Ulhaq Dec 20 '10 at 6:39
  • 2
    $\begingroup$ Yeah, it took me a few readings to figure out how it was done. (That's what makes it "fun" :-P) $\endgroup$ – David Z Dec 20 '10 at 7:22
  • 8
    $\begingroup$ @Sklivvz: regardless, we should have an explanation and not just a link in the answer. (For your answer as-is I think I may have been too quick to click the upvote button) $\endgroup$ – David Z Dec 20 '10 at 9:15
  • 3
    $\begingroup$ @kalle: Kirchhoff's law is what I mentioned in my comment above. You'll obtain an infinite-dimensional matrix and you'll have to compute it's determinant. Or you can use various dualities that connect resistor network with models in statistical physics. Nevertheless, I very much doubt any possible method is in any way easy. You'll definitely need to do Fourier transform or non-trivial integrals (as in the Sklivvz's link) at some point to obtain the results. So you are saying that you obtained something simple that can beat these established methods? I can't say I don't doubt you ;-) $\endgroup$ – Marek Dec 20 '10 at 18:05
23
$\begingroup$

Here's my favourite derivation, which is pretty much based on, but in my opinion rather simpler than the ones given in the links above. Only elementary integration is needed!

The set-up

Work on an $N$-dimensional grid for generality, and label the grid points by $\vec{n}$, an integer vector.

Suppose the voltage at each point is $V_\vec{n}$. Then the current flowing into $\vec{n}$ from its $2N$ neighbours is

$$ \sum_{i, \pm} ( V_{\vec{n} \pm \vec{e}_i} - V_\vec{n} ) $$

($\vec{e}_i$ is the unit vector along the $i$-direction.)

Insist that an external source is pumping one amp into $\vec{0}$ and out of $\vec{a}$. Current conservation gives

$$ \sum_{i, \pm} ( V_{\vec{n} \pm \vec{e}_i} - V_\vec{n} ) = -\delta_\vec{n} + \delta_{\vec{n} - \vec{a}} $$

($\delta_\vec{n}$ equals $1$ if $\vec{n} = \vec{0}$ and $0$ otherwise.)

This is the equation we want to solve. Given $V_\vec{n}$, the effective resistance between $\vec{0}$ and $\vec{a}$ is simply

$$ R_\vec{a} = V_\vec{0} - V_\vec{a} $$

Unfortunately, there are infinitely many solutions for $V_\vec{n}$, and their results for $R_\vec{a}$ do not agree! This is because the question does not specify any boundary conditions at infinity. Depending on how we choose them, we can get any value of $R_\vec{a}$ we like! It will turn out that there's a unique reasonable choice, but for now, let's forget about this problem completely and just find any solution.

Solution by Fourier transform

The strategy is to find a Green function $G_\vec{n}$ satisfying

$$ \sum_{i, \pm} ( G_{\vec{n} \pm \vec{e}_i} - G_\vec{n} ) = \delta_\vec{n} $$

A solution to the original equation would then be

$$ V_n = -G_\vec{n} + G_{\vec{n} - \vec{a}} $$

To find $G_\vec{n}$, assume it can be represented as

$$ G_\vec{n} = \int_0^{2\pi} \frac{d^N \vec{k}}{(2\pi)^N} (e^{i \vec{k} \cdot \vec{n}} - 1) g(\vec{k}) $$

Then noting that

\begin{align} \sum_{i, \pm} ( G_{\vec{n} \pm \vec{e}_i} - G_\vec{n} ) &= \int_0^{2\pi} \frac{d^N \vec{k}}{(2\pi)^N} e^{i \vec{k} \cdot \vec{n}} \left( \sum_{i, \pm} e^{\pm i k_i} - 2N \right) g(\vec{k}) \\ \delta_\vec{n} &= \int_0^{2\pi} \frac{d^N \vec{k}}{(2\pi)^N} e^{i \vec{k} \cdot \vec{n}} \end{align}

we see the equation for $G_\vec{n}$ can be solved by choosing

$$ g(\vec{k}) = \frac{1}{\sum_{i, \pm} e^{\pm k_i} - 2N} $$

which leads to

$$ G_\vec{n} = \frac{1}{2} \int_0^{2\pi} \frac{d^N \vec{k}}{(2\pi)^N} \frac{\cos(\vec{k} \cdot \vec{n}) - 1}{\sum \cos(k_i) - N} $$

By the way, the funny $-1$ in the numerator doesn't seem to be doing much other than shifting $G_\vec{n}$ by an $\vec{n}$-independent constant, so you might wonder what it's doing there. But without it the integral would be infinite, at least for $N \leq 2$.

So the final answer is

$$ R_\vec{a} = V_\vec{0} - V_\vec{a} = 2(G_\vec{a} - G_\vec{0}) = \int_0^{2\pi} \frac{d^N \vec{k}}{(2\pi)^N} \frac{1 - \cos(\vec{k} \cdot \vec{a})}{N - \sum \cos(k_i)} $$

Why is this the right answer?

(From this point on, $N = 2$)

I said earlier that there were infinitely many solutions for $V_\vec{n}$. But the one above is special, because at large distances $r$ from the origin, the voltages and currents behave like

$$ V = \mathcal{O}(1/r) \qquad I = \mathcal{O}(1/r^2) $$

A standard theorem (Uniqueness of solutions to Laplace's equation) says there can be only one solution satisfying this condition. So our solution is the unique one with the least possible current flowing at infinity and with $V_\infty = 0$. And even if the question didn't ask for that, it's obviously the only reasonable thing to ask.

Or is it? Maybe you'd prefer to define the problem by working on a finite grid, finding the unique solution for $V_\vec{n}$ there, then trying to take some sort of limit as the grid size goes to infinity. However, one can argue that the $V_\vec{n}$ obtained from a size-$L$ grid should converge to our $V_\vec{n}$ with an error of order $1/L$. So the end result is the same.

Doing the integrals

First consider the diagonal case

\begin{align} R_{n,n} &= \frac{1}{(2\pi)^2} \int_A dx \, dy \, \frac{1 - \cos(n(x + y))}{2 - \cos(x) - \cos(y)} \\ &= \frac{1}{2(2\pi)^2} \int_A dx \, dy \, \frac{1 - \cos(n(x + y))}{1 - \cos(\frac{x+y}{2}) \cos(\frac{x-y}{2})} \end{align}

where $A$ is the square $0 \leq x,y \leq 2 \pi$.

Because the integrand is periodic, the domain can be changed from $A$ to $A'$ like so:

Rectangles A and A'

Then changing variables to

$$ a = \frac{x+y}{2} \qquad b = \frac{x-y}{2} \qquad dx \, dy = 2 \, da \, db $$

the integral becomes

$$ R_{n,n} = \frac{1}{(2\pi)^2} \int_0^\pi da \int_{-\pi}^\pi db \, \frac{1 - \cos(2na)}{1 - \cos(a) \cos(b)} $$

The $b$ integral can be done with the half-tan substitution

$$ t = \tan(b/2) \qquad \cos(b) = \frac{1-t^2}{1+t^2} \qquad db = \frac{2}{1+t^2} dt $$

giving

$$ R_{n,n} = \frac{1}{2\pi} \int_0^\pi da \, \frac{1 - \cos(2na)}{\sin(a)} $$

The trig identity

$$ 1 - \cos(2na) = 2 \sin(a) \big( \sin(a) + \sin(3a) + \dots + \sin((2n-1)a) \big) $$

reduces the remaining $a$ integral to

\begin{align} R_{n,n} &= \frac{2}{\pi} \left( 1 + \frac{1}{3} + \dots + \frac{1}{2n-1} \right) \end{align}

Induction

While integration was needed to get the diagonal values of $R_{m,n}$, the rest can be determined without it. The trick is to use rotational/reflectional symmetry,

$$ R_{n,m} = R_{\pm n, \pm m} = R_{\pm m, \pm n} $$

together with the following recurrence relation

$$ R_{n+1,m} + R_{n-1,m} + R_{n,m+1} + R_{n,m-1} - 4 R_{n,m} = 2 \delta_{(n,m)} $$

which can be deduced using $R_\vec{n} = 2 G_\vec{n}$ and the defining equation for $G_\vec{n}$.

Start off with the trivial statement that

$$ R_{0,0} = 0 $$

Applying the recurrence relation at $(0,0)$ and using symmetry gives

$$ R_{1,0} = R_{0,1} = 1/2 $$

The next row is done like so

Fill in R11, then R02 and R20

And the one after that...

Fill in R12 and R21, then R03 and R30

Repeatedly alternating the two steps above yields an algorithm for determining every $R_{m,n}$. Clearly, all are of the form

$$ a + b/\pi $$

where $a$ and $b$ are rational numbers. Now this algorithm can easily be performed by hand, but one might as well code it up in Python:

import numpy as np
import fractions as fr

N = 4
arr = np.empty((N * 2 + 1, N * 2 + 1, 2), dtype='object')

def plus(i, j):
    arr[i + 1, j] = 4 * arr[i, j] - arr[i - 1, j] - arr[i, j + 1] - arr[i, abs(j - 1)]

def even(i):
    arr[i, i] = arr[i - 1, i - 1] + [0, fr.Fraction(2, 2 * i - 1)]
    for k in range(1, i + 1): plus(i + k - 1, i - k)

def odd(i):
    arr[i + 1, i] = 2 * arr[i, i] - arr[i, i - 1]
    for k in range(1, i + 1): plus(i + k, i - k)

arr[0, 0] = 0
arr[1, 0] = [fr.Fraction(1, 2), 0]

for i in range(1, N):
    even(i)
    odd(i)

even(N)

for i in range(0, N + 1):
    for j in range(0, N + 1):
        a, b = arr[max(i, j), min(i, j)]
        print('(', a, ')+(', b, ')/π', sep='', end='\t')
    print()

This produces the output

$$ \Large \begin{array}{|c:c:c:c:c} 40 - \frac{368}{3\pi} & \frac{80}{\pi} - \frac{49}{2} & 6 - \frac{236}{15\pi} & \frac{24}{5\pi} - \frac{1}{2} & \frac{352}{105\pi} \\ \hdashline \frac{17}{2} - \frac{24}{\pi} & \frac{46}{3\pi} - 4 & \frac{1}{2} + \frac{4}{3\pi} & \frac{46}{15\pi} & \frac{24}{5\pi} - \frac{1}{2} \\ \hdashline 2 - \frac{4}{\pi} & \frac{4}{\pi} - \frac{1}{2} & \frac{8}{3\pi} & \frac{1}{2} + \frac{4}{3\pi} & 6 - \frac{236}{15\pi} \\ \hdashline \frac{1}{2} & \frac{2}{\pi} & \frac{4}{\pi} - \frac{1}{2} & \frac{46}{3\pi} - 4 & \frac{80}{\pi} - \frac{49}{2} \\ \hdashline 0 & \frac{1}{2} & 2 - \frac{4}{\pi} & \frac{17}{2} - \frac{24}{\pi} & 40 - \frac{368}{3\pi} \\ \hline \end{array} $$

from which we can read off the final answer,

$$ R_{2,1} = \frac{4}{\pi} - \frac{1}{2} $$

$\endgroup$
  • $\begingroup$ It's very interesting that this same formalism can be used to solve the two point function of a massless scalar field on a lattice $\endgroup$ – Joe Mar 13 at 19:34

protected by Qmechanic Jan 23 '14 at 20:46

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.