113
$\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$
6
  • 11
    $\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
57
$\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$
16
  • 61
    $\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
  • 8
    $\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
38
$\begingroup$

This is the XKCD Nerd Sniping problem. It forced me to abandon everything else I was doing to research and write up this answer. Then, years later, it compelled me to return and edit it for clarity.

The following full solution is based on the links posted in the other answer. But in addition to presenting this information in a convenient form, I've also made some significant simplifications of my own. Now, nothing more than high school integration is needed!

The strategy in a nutshell is to

  1. Write down an expression for the resistance between any two points as an integral.

  2. Use integration tricks to evaluate the integral found in Step 1 for two diagonally separated points.

  3. Use a recurrence relation to determine all other resistances from the ones found in Step 2.

The result is an expression for all resistances, of which the knight's move is just one. The answer for it turns out to be

$$ \frac{4}{\pi} - \frac{1}{2} $$

Setting up the problem

While we're ultimately interested in a two-dimensional grid, to start with nothing will depend on the dimension. Therefore we will begin by working in $N$ dimensions, and specialise to $N = 2$ only when necessary.

Label the grid points by $\vec{n}$, an $N$-component vector with integer components.

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 at $\vec{n}$ gives

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

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

Solving this equation for $V_\vec{n}$ will give us our answer. Indeed, the resistance between $\vec{0}$ and $\vec{a}$ will simply be

$$ 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

To solve our equation for $V_\vec{n}$, we will look for a Green's function $G_\vec{n}$ satisfying a similar equation:

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

A solution to $\eqref{eqv}$ will then be

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

To find $G_\vec{n}$, assume (out of the blue) that 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}) $$

for some unknown function $g(\vec{k})$. Then noting that the two sides of $\eqref{eqg}$ can be written as

\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 $\eqref{eqg}$ can be solved by choosing

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

which leads to the Green's function

$$ 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_i \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 the addition of an overall constant, so you might wonder what it's doing there. The answer is that it's technically needed to make the integral finite, but other than that it doesn't matter as it will cancel out of the answer.

So the final answer for the resistance 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_i \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.

The diagonal case

It turns out the integral for $R_{n,m}$ is tricky to do when $n \neq m$, but much easier to do when $n = m$. Therefore, we'll deal with that case first. We want to calculate

\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}

A recurrence relation

The remaining resistances can in fact be determined without doing any more integrals! All we need is rotational/reflectional symmetry,

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

together with the 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 follows from $R_\vec{n} = 2 G_\vec{n}$ and $\eqref{eqg}$. It says that if we know all resistances but one in a "plus" shape, then we can determine the missing one.

Start off with the trivial statement that

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

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

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

The next diagonal is done like so:

Fill in R11, then R02 and R20

Here the turquoise square means that we fill in $R_{1,1}$ using the formula for $R_{n,n}$. The yellow squares indicate an appliation of the recurrence relation to determine $R_{2,0}$ and $R_{0,2}$. The dotted squares also indicate resistances we had to determine by symmetry during the previous step.

The diagonal after that is done similarly, but without the need to invoke the formula for $R_{n,n}$:

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$
2
  • $\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 '19 at 19:34
  • 3
    $\begingroup$ you forgot the units $\endgroup$ – Rainb Dec 6 '19 at 8:36

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