Page 1 of 1
Difficult maths/physics question
Posted: 2009.06.14 (22:17)
by DW40
On an infinite, two-dimensional, rectangular lattice of 1-ohm resistors, what is the resistance between two nodes that are a knight's move away.
From
Google Aptitude Test (and XKCD).
If you have never encountered this problem before, how would you begin to find an answer?
Let's all try and reach a solution.
Re: Difficult maths/physics question
Posted: 2009.06.15 (04:03)
by T3chno
Seems like a trick question. Probably infinite.
Re: Difficult maths/physics question
Posted: 2009.06.20 (04:00)
by jean-luc
assuming a knight's move, resistance of the direct path is 4 ohms. So it's going to be less than that, because of all the other paths. I'd stab a guess at around 3.5 ohms, but I have no idea how to start calculating that.
So, look at the basic component problem.
Code: Select all
4 ohm
__/\/\/\__
/ \
A B
\__/\/\/\__/
5 ohm
Given two paralell resistors between point A and B, one 4 and one 5 ohms, how do you calculate the resistance between points A and B? I have no idea how to calculate this.
Also, check out my ASCII schematic. How cool is that.
Re: Difficult maths/physics question
Posted: 2009.06.20 (06:41)
by PsychoSnail
BanjoDave wrote:If you have never encountered this problem before, how would you begin to find an answer?
By writing 42 and walking away. By figuring out what it means, or rather the concepts needed to solve this.
Re: Difficult maths/physics question
Posted: 2009.06.20 (08:48)
by t̷s͢uk̕a͡t͜ư
jean-luc wrote:assuming a knight's move, resistance of the direct path is 4 ohms. So it's going to be less than that, because of all the other paths. I'd stab a guess at around 3.5 ohms, but I have no idea how to start calculating that.
So, look at the basic component problem.
Code: Select all
4 ohm
__/\/\/\__
/ \
A B
\__/\/\/\__/
5 ohm
Given two paralell resistors between point A and B, one 4 and one 5 ohms, how do you calculate the resistance between points A and B? I have no idea how to calculate this.
Also, check out my ASCII schematic. How cool is that.
For parallel resistors: (1 / R_eq ) = (1 / R_A ) + ( 1 / R_B )
Or if you want the more convenient version: R_eq = (R_A * R_B) / (R_A + R_B)
In the example you gave, it becomes:
Where R_eq = 4 * 5 / (4 + 5) = 20 / 9
Re: Difficult maths/physics question
Posted: 2009.06.20 (16:40)
by jean-luc
Tsukatu wrote:jean-luc wrote:assuming a knight's move, resistance of the direct path is 4 ohms. So it's going to be less than that, because of all the other paths. I'd stab a guess at around 3.5 ohms, but I have no idea how to start calculating that.
So, look at the basic component problem.
Code: Select all
4 ohm
__/\/\/\__
/ \
A B
\__/\/\/\__/
5 ohm
Given two paralell resistors between point A and B, one 4 and one 5 ohms, how do you calculate the resistance between points A and B? I have no idea how to calculate this.
Also, check out my ASCII schematic. How cool is that.
For parallel resistors: (1 / R_eq ) = (1 / R_A ) + ( 1 / R_B )
Or if you want the more convenient version: R_eq = (R_A * R_B) / (R_A + R_B)
In the example you gave, it becomes:
Where R_eq = 4 * 5 / (4 + 5) = 20 / 9
Can that be extended for more paths, like so: (1 / R_eq) = (1 / R_A) + (1 / R_B) + (1 / R_C)?
In that case, you need to work out all the routes between the two points (I think this can be done with combinatorics, but I'm not sure how), which will be infinite. As you figure that equation with the longer and longer routes, though, you'll quickly reach an approximation that is accurate to many decimal places.
Re: Difficult maths/physics question
Posted: 2009.06.20 (18:06)
by Brocerius
How the hell can it be infinite and rectangular? Or is the rectangle the shape between the different resistors? In which case, why mention it - does it change anything (superconductors?)?
Re: Difficult maths/physics question
Posted: 2009.06.20 (21:16)
by Ad
jean-luc wrote:Can that be extended for more paths, like so: (1 / R_eq) = (1 / R_A) + (1 / R_B) + (1 / R_C)?
Indeed it can.
Brocerius, it's theoretical, why not? They're just seperated by the shape:
where each line on this portion of the infinite grid is a resistor.
...Oh, I see what you mean. I don't get that either.
Re: Difficult maths/physics question
Posted: 2009.06.20 (21:35)
by t̷s͢uk̕a͡t͜ư
jean-luc wrote:Can that be extended for more paths, like so: (1 / R_eq) = (1 / R_A) + (1 / R_B) + (1 / R_C)?
In that case, you need to work out all the routes between the two points (I think this can be done with combinatorics, but I'm not sure how), which will be infinite. As you figure that equation with the longer and longer routes, though, you'll quickly reach an approximation that is accurate to many decimal places.
Not necessarily.
I've made a diagram in mspaint to illustrate the relevant rules here:
If it was just one knight's move as Ad. put, with no other resistors, it'd just be a series problem. Add up the resistors and you have your answer.
But because there are other resistors in the way, you can't combine them exactly that way.
So if there is also a path from 6-2-3-7 that has resistors between each of those nodes, you cannot ignore them. In that case, you'd sum up the 6-2, 2-3, and 3-7 resistors, and then put that sum in parallel with the 6-7 resistor to get the equivalent resistance between 6 and 7... and then the equivalent resistance between A and B would be R_5->6 + R_eq_6->7 + R_7->11. It gets trickier and trickier the more you add in, so the resistors infinitely far away do in fact influence the path from A to B.
Re: Difficult maths/physics question
Posted: 2009.06.21 (03:04)
by jean-luc
Ok, so we can easily determine the resistance of a given path (1 ohm * number of steps), and once we have all the totals we can easily sum those to the total resistance between two points. This leaves is with a much more annoying question. How do we get all the possible paths?
The only thing I know how that's even faintly related is find the number of possible paths on a finite grid, and that's just simple combinatorics. I have no idea how to go about this.
We can pretend that the grid is finite. The farther out you go the greater of the resistance of the paths, and thus the less of an effect on the total. So pretending the grid is 100*100 should give us pretty good accuracy. How do you determine the lengths of all of the possible paths between two points on a finite grid, then?
Wait. wait... hm... multiple possible paths involve the same resistors, is this a problem? I'm thinking it might not, but my brain exploded. Does it? I think it doesn't.
Re: Difficult maths/physics question
Posted: 2009.06.22 (12:12)
by 999_Springs
jean-luc wrote:Wait. wait... hm... multiple possible paths involve the same resistors, is this a problem? I'm thinking it might not, but my brain exploded. Does it? I think it doesn't.
It certainly does.
Suppose you take the following simpler problem:
Imagine an infinite ladder of resistors, starting from 0 and going up to infinity, such that there is a resistor between (0,n)and (1,n), a resistor between (0,n) and (0, n+1), and a resistor between (1,n) and (1, n+1). What is the resistance between (0,0) and (1,0)?
If you consider all possible paths, you find:
(0,0)->(1,0): 1 ohm
(0,0)->(0,1)->(1,1)->(1,0): 3 ohms
(0,0)->(0,1)->(0,2)->(1,2)->(1,1)->(1,0): 5 ohms
etc.
Using 1/Rtotal = 1/R1 + 1/R2 + 1/R3 + ...
you get: 1/Rtotal = 1 + 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/13...
=> 1/Rtotal = Infinity
=> Rtotal = 0
Which is wrong.
I think that in the same way you can't reduce a Wheatstone Bridge formation of resistors using series/parallel formulae.
I found a solution to the above ladder resistor problem on
another forum that I have an account on. The solution is a bit unclear but it can be understood, although it contains a few numerical typos and one unproved assumption. If that solution is correct, then perhaps it would provide an alternative method of trying to solve the problem in the first post, but it does look much harder.
Re: Difficult maths/physics question
Posted: 2009.06.23 (06:14)
by jean-luc
oh, I've seen the solution to the infinite grid problem. and it's not pretty. which is to say, I completely don't understand it. I have a lengthy paper that explains it, but I haven't read that yet.
