0356: "Nerd Sniping"

[ArbiterKC]

The answer can be found here (along with higher dimensional derivations):
http://atkinson.fmns.rug.nl/public_html/resist.pdf

[phlip]

Just counting the paths isn't going to work, if those paths overlap... consider, two 2ohm resistors in parallel, vs two 1ohm resistors in parallel with another 1ohm resistor in series. Both have two paths, and all the paths are 2ohm... but the total resistances are 1ohm and 1.5ohm, respectively... since, in the latter case, the two paths share a resistor.

Since there's only 4 resistors leading to each of the marked nodes, there's a maximum of 4 paths you can draw between the two nodes without them sharing resistors... so there's no infinite series of parallel circuits.

[Syphon]

For those put off by PDFs.

The Fourier invokers were right.

[chishm]

Doing it the traditional engineering way, I approximated the solution to a finite 11*16 grid. Using SPICE, I found the answer in that case was 0.79. This is off by less than 0.02, which is only a 2.5% error, much better than the tolerances of many actual resistors.

[CD_XK/USERNAME]

I got sniped badly

Consider the grid as a superposition of many paths (an infinite number in fact)
The solution resistance (R_s) is given by

Sum of all [1/R_p] = 1/R_s

where R_p is a path resistance (equal to the path length in resistors) and all paths are summed..yes it is a sum of an infinite number of paths.

Although the expression on the left hand side is always positive and is being summed to infinity the expression will approach zero. I feel strongly that this sequence will converge to a number greater than 1 but less than 10. I have seen solutions involving pi being touted and those seem the most plausible as infinite sums like this often produce transcendental numbers.

Strange as it may seem many summed infinite series converge to surprisingly small numbers

pi=4(1-1/3+1/5-1/7..........)

The solution probably involves pi or root 2 or similar.

The difficulty is in finding a formula for the length of a path in terms of n, an assigned path number. This formula could then be summed over all n to solve the problem. The formula must cover all possible paths without repetition. This is not an easy task at all. We must be wary of superposition...we cannot count any path that could be constructed by adding and subtracting paths already counted.

Just my two penny's........

I'm an engineering graduate.....I parse problems I don't do maths. We usualy have tables for such things.

A comment on sensible solutions so far proposed
Finite element methods will get close to the answer damn fast, but they're a dirty engineering hack really. Great for the real world where you don't get nice mathematically abstractable shapes but this problem is crying out for an elegant mathematical solution.

Using fourier series seems like a really intelligent idea. I have no idea how they help in this case (surely they are constructs for continuous problems when what we have here is a discrete problem hence the discrete summation I proposed). Still, it's amazing what you can do with fourier series and I wouldn't say that they can't be applied here by someone of more mathematical nous than myself.

[xquared]

Doing it the traditional engineering way, I approximated the solution to a finite 11*16 grid. Using SPICE, I found the answer in that case was 0.79. This is off by less than 0.02, which is only a 2.5% error, much better than the tolerances of many actual resistors.

w00t for approximations... just working the safety factors

[iNap]

Doing it the traditional engineering way, I approximated the solution to a finite 11*16 grid. Using SPICE, I found the answer in that case was 0.79. This is off by less than 0.02, which is only a 2.5% error, much better than the tolerances of many actual resistors.

I was planning to do this same thing. I just ordered a couple hundred 1-ohm resistors...hm. Maybe I should've read the past couple of pages first. *shrug*

[ahecht]

Wouldn't the resistance be 0? I actually came up with a number that would satisfy this in my Calculus class: 1-.99999... It comes out to .000...0001 (infinite zeros). It can be represented as "the limit of y such that y=1/x as x goes to infinity". Since it could never really reach zero it would be as close to zero as was possible. Just a thought.

This is a rather pedantic point, but 1-.9999... is not .0000....001 and does not require limits to solve. It's just 0. I will demonstrate.

.999... = x
9.999... = 10x (multiply both sides by 10)
9.999... - .999... = 10x - .999 (subtract .999 from the left, x from the right)
9 = 10x - .999... (simplify left side)
9 = 10x - x (.999 = x, see first line)
9 = 9x (simplify right side)
1 = x (divide both sides by 9)
1 = .999... (.999=x, see first line)
QED.

And so your problem is really 1 minus 1, which is just 0. No limits needed

Here is a simpler proof:

1/9 = .111...
2/9 = .222...
3/9 = .333...
4/9 = .444...
5/9 = .555...
6/9 = .666...
7/9 = .777...
8/9 = .888...
9/9 = .999...
9/9 = 1
Therefore .999 = 1

[Mystitat]

Forgive me if this has been noted already (for I haven't read through the current five pages of replies to this thread), but I believe there is a flaw in this game. Eventually wouldn't all these physicists and mathematicians hesitate to begin walking across a crosswalk littered with remnants of corpses?

At least, I hope they would.

[Simetrical]

Another one sniped. I was far too lazy to spend more than a minute on it (I'm a mathematician, not an engineer! I don't like electromagnetism anyway!), and I didn't sign up just to read this, but this one triggered a rare visit to the forum so I could see the answer. While I'm here . . .

This is a rather pedantic point, but 1-.9999... is not .0000....001 and does not require limits to solve. It's just 0.

1) You can say 1 − 0.999... = 0.000...01 (= lim 10⁻ⁿ), but of course the latter quantity equals zero.

2) Your proof must use limits to be formally valid. There is no way to rigorously deal with a quantity such as 0.999... without first defining it rigorously. As it happens, in this case the results of the conventional rigorous definition agree with intuition, but that's not enough to prove that the answer is correct, only to suggest that it could be a good answer. (Okay, I don't deny the possibility of a rigorous definition of repeating decimals that does not involve limits, but your post is not an example of that.)

Cute but decimals are not a unique representation so it isn't valid.

Um, yes, decimal representations aren't unique, that's what 1 = 0.999... proves. No kidding. It has no bearing on the intuitive proof that Brandon presents, which is valid so long as you can show that 0.999... is well-defined (which it is: it represents a unique number under the conventional definition, even if it's not unique as a decimal representation of that number), and that it behaves "intuitively" with respect to multiplication and subtraction ― that is, that 10 · 0.999... = 9.999... and 9.999... − 0.999... = 9 (both of which are true).

The non-uniqueness of decimal representation is typically unimportant, in general. The only non-unique representations for a number in the base of an integer n > 1 will be representations of the form a₁···a_k.a_k+1···a_m000··· = a₁···a_k.a_k+1···(a_m − 1)(n − 1)(n − 1)(n − 1)··· for a_m ≠ 0, and it's easy to specify which of them you prefer to work with, if it would affect your proof. (A common summary of Cantor's diagonal argument for the disparity between the natural numbers and the reals uses decimals but is unaffected by which representation is chosen for any given number.)

Here is a simpler proof:

1/9 = .111...
2/9 = .222...
3/9 = .333...
4/9 = .444...
5/9 = .555...
6/9 = .666...
7/9 = .777...
8/9 = .888...
9/9 = .999...
9/9 = 1
Therefore .999 = 1

Also relatively intuitive and therefore useful, but also not a rigorous proof. Without a rigorous definition of a repeating decimal, you could justly say that the equality holds because repeating decimals are nonsense, so of course you can produce nonsensical results, 0.999... doesn't equal anything. (That is what I said when presented by someone with the proof you post, in like eighth grade. It was presented as a paradox, not a proof, incidentally, which I think is how many people perceive non-unique decimal representations.)

[Syphon]

Wouldn't the resistance be 0? I actually came up with a number that would satisfy this in my Calculus class: 1-.99999... It comes out to .000...0001 (infinite zeros). It can be represented as "the limit of y such that y=1/x as x goes to infinity". Since it could never really reach zero it would be as close to zero as was possible. Just a thought.

This is a rather pedantic point, but 1-.9999... is not .0000....001 and does not require limits to solve. It's just 0. I will demonstrate.

.999... = x
9.999... = 10x (multiply both sides by 10)
9.999... - .999... = 10x - .999 (subtract .999 from the left, x from the right)
9 = 10x - .999... (simplify left side)
9 = 10x - x (.999 = x, see first line)
9 = 9x (simplify right side)
1 = x (divide both sides by 9)
1 = .999... (.999=x, see first line)
QED.

And so your problem is really 1 minus 1, which is just 0. No limits needed

Here is a simpler proof:

1/9 = .111...
2/9 = .222...
3/9 = .333...
4/9 = .444...
5/9 = .555...
6/9 = .666...
7/9 = .777...
8/9 = .888...
9/9 = .999...
9/9 = 1
Therefore .999 = 1

Here's a simpler proof.

1/3 = .333...
.333... x 3 = .999...
1/3 x 3 = 3/3
.999... = 3/3
.999... = 1

[phlip]

And to think I tried to nip this 0.999...=1 thing in the bud

See previous discussion here, and here, and plenty of other threads.

Also please read this thread.

[DragonHawk]

400 equals infinity!

If I was the kind of person who put random quotes in sigs, I'd quote this in my sig.

I'm tempted to quote that in my sig.

Besides, it's all in the delivery. Not just "400...", but "800 equals infinity too!". LOL. argonaut wins the game (not that game (you just lost that game (so did I)), a different game).

[Agent Anderson]

it is a sum of an infinite number of paths.

So we need to ask ourselves: is it countably infinite, or uncountably infinite.

[bcoblentz]

Wouldn't that just help you decide whether to use a sum or an integral? That wouldn't really get you anywhere unless you had already worked most of it out.

I'm enjoying this thread. Parts of it, anyway.

[Kin]

I'm trying to resist the urge... I need sleep T_T

I caught mes another one!

[Simetrical]

it is a sum of an infinite number of paths.

So we need to ask ourselves: is it countably infinite, or uncountably infinite.

Any path can be viewed as a finite sequence of numbers from 1 to 4 (a finite tuple in ℤ₄). For any given path length, we can construct a finite set of all paths of the given length by exhaustion. There are only countably many path lengths, and the union of countably many finite sets is countable. Therefore there are only countably many paths.

[Simetrical]

Wouldn't that just help you decide whether to use a sum or an integral? That wouldn't really get you anywhere unless you had already worked most of it out.

I'm enjoying this thread. Parts of it, anyway.

You're being far too focused here.

[bcoblentz]

Huh?

[Alphaniner]

The Classhole graces the following 25 comics with his presence.

Classhole
Bored with the Internet
Attention, Shopper
Digital Rights Management (Look closely. Definitely a hat.)
Gravitational Mass
Computational Linguists
Centrifugal Force? I dunno. He does have the hat.
There is a man with a hat in Marketing Interview, but I don't think it's the Classhole.
Pointers
Join MySpace
Commented
Donald Knuth
Words that end in -gry
Not really into Pokemon
IPoD (Definitely the classhole. Hat+Crossbow. Who else?)
Lojban
Reno Rhymes
e to the pi minus pi. (Such blatant sadism is obviously the classhole's work.
Labyrinth Puzzle
Black Hat Support
Orphaned Projects
Pix plz
A-minus-minus
Trolling
And of course, Nerd Sniping

[Quantum Potatoid]

I feel rather unsafe now... I'll have to be on the lookout for Black Hatted men... I can be baited rather easily. Actually, you could probably get me by just taking my TI Graphing Calculator away from me and running into the middle of the road with it. Me: *Caresses calculator* I've finally got you back at la-*SMACK*

[DragonHawk]

Bored with the Internet

Is that really the Classhole, though, or just a guy with a hat? (I mean, sure, they could be the same guy, but since it's a web comic, I'd say characters are defined by how they act. The hat-guy is not being an asshole of any type, there, so he is not the Classhole.)

(I'm nit-picking because it's something to do instead of folding my laundry.)

[gringer]

Y'know, Randall didn't really specify what *kind* of infinite grid it was. Picture such a grid stretched out all over Earth, with all the lines joining up, or in a simpler case, something like this:


[i.e. A is connected to D and C, B is connected to E, and so on]

Would this change the resistance?

I will allow myself to define such a grid as infinite, as there is a model of the infinite universe where points wrap around in a similar way.

[Simetrical]

Y'know, Randall didn't really specify what *kind* of infinite grid it was. Picture such a grid stretched out all over Earth, with all the lines joining up, or in a simpler case, something like this:


[i.e. A is connected to D and C, B is connected to E, and so on]

Would this change the resistance?

I will allow myself to define such a grid as infinite, as there is a model of the infinite universe where points wrap around in a similar way.

Your example is not infinite. There's nothing wrong with wrapping around, but it contains only finitely many resistors. So your example isn't legit. (The universe is not infinite either, if its geometry is spherical, and possibly not if its geometry is Euclidean either.) Also, keep in mind that to qualify as a "grid" in the intended sense, it's clear that each intersection must have four paths going out (a node of order four, I think it's called? I'm not into graph theory much).

Related examples may be infinite grids with different topologies from the obvious one, though. Consider a grid of infinite length but finite width, wrapped into a regular polygonal cylinder. That satisfies all explicitly stated conditions (infinity and grid-ness). Clearly it's not what was intended, but it's an interesting added puzzle. I expect the resistance to be lower for the cylinder, because there should be more paths of any given length between any two points, but of course it would vary with the size of the cylinder. In the limit of infinite size I would suppose its resistance to converge to the planar grid. The smallest possibly-acceptable grid like this would be a right triangular cylinder, which should have considerably lower resistance than the planar grid.

Edit: One could of course argue that a two-dimensional grid should be planar to qualify as a grid, but that's really beside the point. This is obviously a separate problem, not the one that was posed. You can nitpick the specs, but come on, this is an engineering problem. Of course the finite grid posed by gringer is by that logic equally valid as an alternative problem to consider, but I think it's not very interesting. It's not hard to compute the exact resistance of any finite grid of resistors, it's just computation.

[gringer]

Your example is not infinite.

Ah well, there go my attempts for further sniping.

Related examples may be infinite grids with different topologies from the obvious one, though. Consider a grid of infinite length but finite width, wrapped into a regular polygonal cylinder. That satisfies all explicitly stated conditions (infinity and grid-ness)

Or not...

[OP Tipping]

HERE BE SPOILERS............

Spoiler:

http://atkinson.fmns.rug.nl/public_html/resist.pdf, the answer is 4/pi-1/2

[scarletmanuka]

I have a sudden urge to post a link, despite how old the video is.
Oh screw it, I can't resist.
http://www.youtube.com/watch?v=BipvGD-LCjU

I managed to get through most of this with no more than the occasional laugh or groan - I particularly liked "but then you drove a wedge between our 2-forms" - until I got to this line:

When we first met, we simply connected

me: *facepalm*

[Nimz]

Y'know, Randall didn't really specify what *kind* of
infinite grid it was. Picture such a grid stretched out all over Earth,
with all the lines joining up, or in a simpler case, something like
this:


[i.e. A is connected to D and C, B is connected to E, and so on]

Would this change the resistance?

I
will allow myself to define such a grid as infinite, as there is a
model of the infinite universe where points wrap around in a similar
way.

Your example is not infinite. There's nothing wrong with
wrapping around, but it contains only finitely many resistors. So your
example isn't legit. (The universe is not infinite either, if its
geometry is spherical, and possibly not if its geometry is Euclidean
either.) Also, keep in mind that to qualify as a "grid" in the intended
sense, it's clear that each intersection must have four paths going out
(a node of order four, I think it's called? I'm not into graph theory
much).

Related examples may be infinite grids with different
topologies from the obvious one, though. Consider a grid of infinite
length but finite width, wrapped into a regular polygonal cylinder.
That satisfies all explicitly stated conditions (infinity and
grid-ness). Clearly it's not what was intended, but it's an interesting
added puzzle. I expect the resistance to be lower for the cylinder,
because there should be more paths of any given length between any two
points, but of course it would vary with the size of the cylinder. In
the limit of infinite size I would suppose its resistance to converge
to the planar grid. The smallest possibly-acceptable grid like this
would be a right triangular cylinder, which should have considerably
lower resistance than the planar grid.

Edit: One could of course
argue that a two-dimensional grid should be planar to qualify as a
grid, but that's really beside the point. This is obviously a separate
problem, not the one that was posed. You can nitpick the specs, but
come on, this is an engineering problem. Of course the finite grid
posed by gringer is by that logic equally valid as an alternative
problem to consider, but I think it's not very interesting. It's not
hard to compute the exact resistance of any finite grid of resistors,
it's just computation.

In that picture, the geometry isn't spherical. It's toroidal. (I'm nitpicking because I've already folded my laundry, unlike some other people.)

When I am confronted with an interesting problem, I am snipable insofar as I might procrastinate on other problems that I should be working on. I don't think I'm in too much danger from FOOOOM-trucks, though, because I come from the future, where nerd-sniping has caused an evolution in nerds to instinctively move to safe-appearing locations without any conscious thought whenever presented with interesting problems.

[Ari]

Infinitely small is zero, as has been discussed to death elsewhere.

Within the domain of real numbers. Some domains (I have no idea how useful or well-defined they are) do allow for infinetesimals.

[cranberrytuna]

One thing I never liked about this comic is how it excludes "Literary Nerds", if you will.

i.e. "Which is a better literary work, Stephen Crain's "Open Boat" or Ralph Waldo Emerson's "Self Reliance"?"

Art is subjective, though. While this question is either right or wrong.

.... not sure what point I'm trying to make. I had it, but now I'm tired and I forgot.

and hey, you feel excluded by the comic, I feel excluded when literary nerds make fun of the books I read. (Why do you hate me, english majors!? Why?!)

[Chalnoth]

Well, the solution has been mentioned, but I don't think anybody's actually mentioned how to solve the problem (though some papers that do show this have been presented, they may not be understandable). So, I thought I'd give my solution (which closely mirrors that in Cserti's paper which has been mentioned previously in the thread: http://arxiv.org/abs/cond-mat/9909120v4 ). I had a lot of fun solving this problem, so I thought maybe some of you might be interested in how I did it

Spoiler:

To start the problem, we consider that current must be conserved. If there is no source voltage or ground at a point, the total current flowing into and out of it must be zero. For the two points between which we are attempting to find the equivalent resistance R, we can place a test voltage differential V, and find that the sum of the current exiting the higher voltage point will be V/R, and that entering the lower voltage point must therefore also be V/R.

We can then define the voltage at every point in the lattice, and use differences in the voltage between neighboring points to represent the currents between lattice points in terms of voltages (and the known resistance between lattice points). This gives us one equation for each lattice point (from current conservation at the point) and one unknown for each lattice point (its voltage). This is just a linear algebra problem that can be solved with matrix methods.

Essentially, you can write the problem as follows:

A_ij * V_j = dQ_i

Here A_ij is chosen such that A_ij * V_j is equal to the sum of the currents exiting each lattice point i, and dQ_i is the time rate of change of the charge at that point, which is zero for all lattice points but the two test points, where, as mentioned above, it's equal to V/R or -V/R, depending. To solve this sort of equation, we merely need to invert A_ij.

What's that? Invert an infinite dimensional matrix, you say? No problem! The answer is just to use eigenvector decomposition of the matrix. The eigenvectors turn out to be Fourier modes where the wave number has a range of 2pi (easiest to use -pi to pi as the range). Once you've diagonalized the matrix, the inverse is obtained by merely inverting the eigenvalues individually. From here the result is a rather straightforward, if ugly integral.

Hopefully somebody finds this interesting

Edit: The above is a rough sketch, of course. You would probably want to make use of two indices to label each lattice point, and the matrix inversion does require that you're a bit careful about how to compose the matrix A out of the eigenvectors and eigenvalues, but the essence is all there.

[Fuller]

@ the spoiler in the above post:

If you say:
"Eigenvector decomposition of the matrix"
In an Austrian accent like that cartoon professor on the "Felix the Cat" cartoon, it sounds really cool.

[PAStheLoD]

I don't even know that I've been registered here before, but to my suprise I've a valid account, so not this comic lured me here entirely, but made me spend almost 2 days thinking about this problem

So I may worth a few points or something, being a CS degree aspirant and math-lover :]

My issue with these problems in general is that I understand the math part of it (ok, most of them..) and I'm a little familiar with the underlying physics.. but the linked papers are just not detailied enough for my little mind

[DrLex]

Second, it seems like everyone working on the problem here and historically has been a mathematician, not an EE. Why? Because an EE would make it into a simpler problem. I'm going to go out on a huge limb here and say that everyone who has posted solutions is wrong since the current will not go through *every* resistor in the plane. Path of least resistance yada yada. So heres my solution:...

Your idea is good, except that your understanding of "path of least resistance" is flawed. Technically, electrons take the path of least impedance. At low frequencies like DC, this is indeed the path of least resistance, but at high frequencies it's the path of least inductance. This leads to some neat behavior...the high-frequency return currents on a reference plane near a digital trace follow the shape of the trace; they do not go straight back to the source.

Yes indeed, the "path of least resistance" (or impedance, or inductance) is just a gross oversimplification to learn kids, who like to think in extremes, some basic principles about electricity. It's not like when you put two light bulbs in parallel and one has a slightly higher impedance than the other one, only one of them will burn. Otherwise we would probably never have bothered with electric light and still be using candles, gas lamps and torches, because only being able to turn on one bulb at a time isn't very practical.
The more correct formulation of this rule is Ohm's law, which states that components in an electrical circuit obey V = I·R, or more generally, V = I·Z. If one puts two resistors in parallel, then this formula shows that I=V/R will be smaller for the larger R. So indeed, more current will flow through the smaller R, but not all of it, as the PoLR rule seems to imply.

Anyway, there are also other paths that the electricity will take, because the path of absolute least resistance will be crowded. You might be surprised how far it spreads out.

Yes, as a matter of fact, current will flow in every single resistor of this infinite grid. Of course, if you go far enough from the 'contact points', the current will become incredibly small.

[Simetrical]

In that picture, the geometry isn't spherical. It's toroidal.

Well, I didn't say otherwise, but you're right that I spoke misleadingly. The universe need not be spherical to wrap around itself, as I implied. Is there a proper term for "wrapping around itself in some direction"? Like "finite but unbounded in some direction"? I haven't ever taken an advanced geometry course, or topology or anything (yet).

[sab39]

I don't think it makes a difference whether the infinite plane "wraps around" at infinity or not. On an infinite non-wrapping "flat" plane, once you get sufficiently far from the two points that voltage is being applied, the voltage level becomes indistinguishable from the average of the two voltages, right? And the current flowing becomes indistinguishable from zero.

So if conditions at an infinite distance are identical regardless of which direction you go, it makes no difference whether those infinitely-far-away points *are* the same point, or not.

(I'm aware that this isn't a rigorous proof. But it's good enough to convince me in an intuitive sense, especially since an "infinite torus" is pretty darn impossible in the first place).

Incidentally, isn't there a projection of the complex numbers onto a sphere which treats infinity in all directions as the point at the north pole? So it is possible to map an infinite grid onto a sphere - but it's not very clear how the resistors would join up at the top, other than being packed infinitely dense.

[scalziand]

You know if xkcd has this kind of motivating power, Randall ought to put it to good use. For example slip in a subtle problem that is equivalent to a proof of NP-completeness or some other intractable task... within hours of being posted someone on the fora might have a solution!

well... Umm... He sorta did already:

[MrBawn]

First thing I thought of when I saw this was that episode of Star Trek TNG where they planned to destroy the Borg by feeding them an unsolvable gemoetry problem.

[chopps]

Isn't it simply 20 ohms? There may be infinite resistors, but I only see 4 parallel paths.

[J Spade]

I came up with 0 < R < 3.

Cuz' resistors in parallel come to less resistance than the least resistant resistor, and the smallest line would have 3 ohms of resistance.

EDIT: But an infinite number of parallel series with potentially infinite resistances would potentially bring R infinitely close to 3?