On this infinite grid of resistors, what's the equivalent resistance? [closed]

Question

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?

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.

Answer 1

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.

Mathematical derivation:

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

Answer 2

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:

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:

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

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