A holiday puzzle: solution

I now discuss two solutions to the puzzle described in the last post — one for the special case of a linear grid, and the other for the general 2D grid.  I thank Johan Ugander and Shiva Navabi for very useful pointers (see the Comment in the last post, and a funny nerd snipe comic) — I will return to them below.  But first, here is a simple heuristic solution.

Special case: linear grid

We first solve the one-sided linear grid shown in the figure below.

fig-LinearGrid1

Let {R_1} denote the equivalent resistance between node + and node -.   By symmetry, the one-sided infinite grid on the upper panel of the figure is equivalent to the finite circuit in the lower panel.  Hence, applying Kirchhoff’s current law at node +, we have

\displaystyle \begin{array}{rcl} \frac{1}{R_1} & = & 1 + \frac{1}{1+R_1+1} \end{array}

giving \displaystyle \begin{array}{rcl} R_1 & = & \sqrt{3}-1\ \end{array}   ohm.

For the two-sided infinite linear grid shown in the upper panel of the figure below, let {R_2} denote its equivalent resistance.

fig-LinearGrid2

By symmetry, the infinite grid is equivalent to the finite circuit in the lower panel.  Applying Kirchhoff’s current law at node +, we have

\displaystyle \begin{array}{rcl} \frac{1}{R_2} & = & 1 + \frac{1}{1+R_1+1} + \frac{1}{1 + R_1 + 1} \end{array}

giving \displaystyle \begin{array}{rcl} R_2 & = & \frac{R_1+2}{R_1+4} \ \ = \ \ \frac{\sqrt{3}+1}{\sqrt{3}+3}\ \end{array}   ohm.

General case: 2D grid

It is not clear how to extend the simple symmetry argument for the linear gird to the 2D grid.  For the 2D grid, we will use loop current analysis, choosing every “cell” as a loop, including the loop involving the voltage source.  The analysis is straightforward, but unlike for the linear grid, I don’t have a closed-form solution (see the next section for a closed-form solution).  To solve it numerically, I will solve a sequence of finite grid, and assume that the sequence of solutions converges to the solution of the infinite grid.

To illustrate the method, consider the simplest (base) case with 2 cells, as shown in the figure below.fig-2loops

There are 3 loops in this circuit: the loop involving the voltage source, and the 2 loops that define the grid. The corresponding loop currents, in clockwise direction, are denoted by {I_0, I_{11}, I_{12}} respectively. To simplify the illustration for cases involving more loops, I will represent this definition simply as in the lower panel of the figure.

Applying KVL around the two loops in the grid, we have

\displaystyle \begin{array}{rcl} 0 & = & I_{11}\cdot 4 \ + \ I_0\cdot 1 \ - \ I_{12}\cdot 1 \\ 0 & = & I_{12}\cdot 4 \ - \ I_0\cdot 1 \ - \ I_{11}\cdot 1 \end{array}

Hence, we have a linear equation in the vector variable {I := (I_{11}, I_{12})} of the form {A I = b}.  The matrix {A} is nonsingular.  Inverting {A} solves {I} in terms of {I_0}{I_{11} = -0.2 I_0} and {I_{12} = 0.2I_0}.

Applying Kirchhoff’s voltage law (KVL) around the loop involving the voltage source, we have {1 = I_0 + I_{11} - I_{12}}.  Substituting {I_{11}} and {I_{12}} yields the equivalent resistance:

\displaystyle \begin{array}{rcl} R_1 & := & \frac{1}{I_0} \ \ = \ \ {1 - 0.2 - 0.2} \ = \ \frac{3}{5}\ \end{array} ohm

Solving the general case numerically boils down to deciding a sequence of finite 2D grids and, for each finite grid, algorithmically writing down the matrix {A} and vector {b} in the linear equation {A I = b} to solve for the vector {I} in terms of the current {I_0}.   It’s standard loop current analysis, and the small trick is to label the variables to simplify coding.  The details are here, and the result is in the figure below.  Empirically, it shows that the equivalent resistance for the 2D grid is 0.5 ohm, which makes sense.

fig-EquivResistance+

Other (more rigorous) methods 

There has indeed been quite a bit of work on resistance and currents in infinite electric networks, as pointed out in Johan Ugander and Shiva Navabi’s Comments in the last post.  Here is a nice summary by a Dartmouth mathematician Peter Doyle.  It starts out with a very simple folk argument that shows the equivalence resistance of the 2D infinite grid to be 0.5 ohm, and then develops a general mathematical theory to make everything precise.

The folk argument uses a current source instead of a voltage source as I did.  Suppose we connect a unit current source/sink to nodes + and – that injects 1A of current into node + and withdraws 1A from node -.  The voltage drop from node + to node – is then 1A times the equivalent resistance, which is equal to the current {I} on the line connecting (from) node + and (to) node -, multiplied by 1 ohm.  Hence, the equivalent resistance is (in value) {I}. What then is this current {I} on this line, when 1A is injected into node + and withdrawn from node -?   Imagine a node at infinity.  Imagine that there is only a single current source at node + (and no current sink at node -) that injects 1A at node +, and consider the current from node + to infinity.  By symmetry, since there are 4 lines incident on node +, 0.25A flows from node + to infinity through the line connecting nodes + and -.  Similarly, imagine that there is only a single current sink at node – (and no current source at node +) that withdraws 1A from node -, and consider the current to node – from infinity.   By symmetry, 0.25A flows into node – from infinity through the line connecting nodes + and -.   When there is both a source that injects 1A at node + and a sink that withdraws 1A from node -, by superposition, the total current {I} on this line is their sum, i.e., 0.5A.  Hence, the equivalent resistance between nodes + and – is 0.5 ohm.  This argument applies to an infinite grid in d dimension, and it shows that the equivalent resistance between adjacent nodes is 1/d (d=2 in our case).

To rigorously justify this folk argument, the mathematicians start from the very basic: what does it even mean by an infinite grid?   In particular, there can be multiple ways to define how currents behave at the infinity edge of the grid, and it is not clear a priori which is the right definition.   A formal mathematical theory is developed to resolve this in the works of Foster, Flanders, Purcell, Doyle, and Snell, etc. from the 1940s through 1980s, as Johan and Shiva pointed out.   The idea is roughly as follows.  One can always define mathematically and unambiguously quantities (variables) for any finite grid, such as currents, voltages, and equivalent resistance, and equations that these variables satisfy, such as Kirchhoff’s laws.  As always, the currents and equivalent resistance of the infinite grid are defined as the limits of the corresponding quantities in sequences of finite grids.  To resolve the (apparent) ambiguity of how currents behave in the infinite grid, the mathematicians define two sequences of finite grids.  The equivalent resistances in one sequence lower bounds, and that in the other sequence upper bounds, the (multiple possible definitions of the) equivalent resistance of our 2D infinite grids.  They then prove that both sequences converge and to the same limit.  Since our 2D infinite grid is sandwiched between these two bounding sequences, everything makes sense. The theory applies to infinite grids in any finite dimension.  Peter Doyle’s concise summary provides a mathematical framework in which our heuristic numerical solution can also be justified.

Advertisements

One thought on “A holiday puzzle: solution

  1. Pingback: Rigor + Relevance | A holiday puzzle

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s