11274  Infinite Resistor Network
Moderator: Board moderators
11274  Infinite Resistor Network
Anyone has any idea on how to do this?
I tried some finite cases, but don't see any patterns.
It seems to converge to some constant around 0.6
I tried some finite cases, but don't see any patterns.
It seems to converge to some constant around 0.6
Re: 11274 Infinite Resistor Network
Maybe I should try to use more symmetry argument to find an recursion.sclo wrote:Anyone has any idea on how to do this?
I tried some finite cases, but don't see any patterns.
It seems to converge to some constant around 0.6
I am solving for it numerically, and it seems to be
0.6589186226... and accurate to about 12 digits.
From the finite cases, I see that it is of the form 1/2 + a*sqrt(2), where a is a rational number.
I need help on finding res of infinite resistor network
I have tried to find soln of this and the other problem on resistance but personally I have no idea how to find resistance of infinite resistor nework.
Will you please ecplain how resistance is computed in some base cases.
( I don't even understand the sample inputs)
Will you please ecplain how resistance is computed in some base cases.
( I don't even understand the sample inputs)
study Kirchoff's Law and Ohm's Law
For finite cases, we can view the problem as some kind of network flow from A to B of current = 1:
Ohm: resistance between a,b on a wire = (voltage (potential) drop between a,b) divided by current on the wire.
Kirchoff: Sum of current flowing out of any intersection is equal to 0.
we denote A as source, and B as the sink.
The idea is that we assign each vertex a variable that denotes the potential at that vertex, and apply the 2 laws to each edge incident to a vertex.
Example:
Suppose all the edges in the network are:
A V1
A V2
V1 B
V2 B
And assume d(a,b) is the length of wire between a,b. (we assume uniform resistance on a wire, so resistance of the wire is simply d(a,b))
(This base case is so simple that there is a reduction to a single resistance, but we need to use general case for more complicated ones)
set up equations as follows:
(V1A)/d(V1,A) + (V1B)/d(V1,B) = 0
(V2A)/d(V2,A) + (V2B)/d(V2,B) = 0
(AV1)/d(A,V1) + (AV2)/d(A,V2)  1 = 0
B = 0
We need to compute A, and that will represent the resistance between A,B since potential = current * resistance.
The solution of above is V1 = V2 = 1/2, A = 1, B = 0 (assuming all edges are length 1)
Closest look at it will tell you that V1=V2 because they top down symmetric, and
V1=V2=(AB)/2, since left and right is also symmetric.
The observation is always true:
All node in the general case that is eqidistance from A,B has potential A/2,
And all nodes in the upper half has same potential to a corresponding node in the lower half.
Thus, we can just look at say the left half, and we can just set the potential of any vertex equidistance from A,B to 0, and the final solution should be 2*A
Back to our example:
we set V1=0, and V1=V2
so there is only 1 equation left:
(AV1)/d(A,V1) + (AV2)/d(A,V2)  1 = 0
the equation becomes:
A/d(A,V1) + A/d(A,V1)  1 =0
so the solution is A = 1/2, so the potential between A,B is 2*(1/2) = 1 which is expected.
If I use the computer to recursively construct more and more cases, I found that the potential between A,B to approach 0.6589186226
Through some more work, I've managed to reduce the system into a 1dimensional recurrence, and computed the solution.
For finite cases, we can view the problem as some kind of network flow from A to B of current = 1:
Ohm: resistance between a,b on a wire = (voltage (potential) drop between a,b) divided by current on the wire.
Kirchoff: Sum of current flowing out of any intersection is equal to 0.
we denote A as source, and B as the sink.
The idea is that we assign each vertex a variable that denotes the potential at that vertex, and apply the 2 laws to each edge incident to a vertex.
Example:
Suppose all the edges in the network are:
A V1
A V2
V1 B
V2 B
And assume d(a,b) is the length of wire between a,b. (we assume uniform resistance on a wire, so resistance of the wire is simply d(a,b))
(This base case is so simple that there is a reduction to a single resistance, but we need to use general case for more complicated ones)
set up equations as follows:
(V1A)/d(V1,A) + (V1B)/d(V1,B) = 0
(V2A)/d(V2,A) + (V2B)/d(V2,B) = 0
(AV1)/d(A,V1) + (AV2)/d(A,V2)  1 = 0
B = 0
We need to compute A, and that will represent the resistance between A,B since potential = current * resistance.
The solution of above is V1 = V2 = 1/2, A = 1, B = 0 (assuming all edges are length 1)
Closest look at it will tell you that V1=V2 because they top down symmetric, and
V1=V2=(AB)/2, since left and right is also symmetric.
The observation is always true:
All node in the general case that is eqidistance from A,B has potential A/2,
And all nodes in the upper half has same potential to a corresponding node in the lower half.
Thus, we can just look at say the left half, and we can just set the potential of any vertex equidistance from A,B to 0, and the final solution should be 2*A
Back to our example:
we set V1=0, and V1=V2
so there is only 1 equation left:
(AV1)/d(A,V1) + (AV2)/d(A,V2)  1 = 0
the equation becomes:
A/d(A,V1) + A/d(A,V1)  1 =0
so the solution is A = 1/2, so the potential between A,B is 2*(1/2) = 1 which is expected.
If I use the computer to recursively construct more and more cases, I found that the potential between A,B to approach 0.6589186226
Through some more work, I've managed to reduce the system into a 1dimensional recurrence, and computed the solution.
Last edited by sclo on Sat Sep 15, 2007 7:15 am, edited 1 time in total.
So basically, we need to compute 10 million digits of irrationals, which is crazy.
Last edited by sclo on Sat Sep 15, 2007 7:15 am, edited 1 time in total.

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
My first guess was to use FFT to compute square roots, this is a well known technique, but hard to implement. But what is very annoying:sclo wrote:So basically, we need to compute 10 million digits of sqrt(3) and sqrt(2), which is crazy.
Coincidently, the solution is also sin(pi/3)+sin(pi/6)sin(pi/4)
on contest the time limit was 1 sec. for this problem and pifast can compute sqrt(2) in about 20 sec. on my pc. So it would take about 40 sec. to compute our number, but pifast using a very well optimized FFT and my pc is 1.7 GHz Celeron, it is obviously TLE on judge.
My second guess is to use a BBP formula to compute directly only the required digits of sqrt(2) and sqrt(3). But it is not known if it is exist for sqrt(2). OK, it can be still exist for our number but I don't think that. I've checked some sites but haven't found.
One person already solved, the problemsetter ( and also the input setter?! ), I hope this isn't cheat:
Code: Select all
Ranking Submission User Time used (ms) Memory used Language Submission time
1 5911509 baodog 690 C++ 20070911 05:53:48
Correction
The input specification is incorrect due to a mixup.
I have already sent in a correction, but it may be
awhile before the html is updated since people are busy
updating the new server software.
It should say the following:
k < 10000000 and 0 < min(k,990*10^4k) < 10^4.
Sorry about the mistake. I will be much more careful the next time.
What happened is my problem tester increased the dataset,
but I didn't submit the correctly updated html file. Even
my solution got TLE, until I submitted his code.
Unfortunately, no one asked for clarification on this problem
during the contest. Hey, on the bright side, maybe someone
come up with a BPP formula for sqrt(2) and win the Fields medal.
I have already sent in a correction, but it may be
awhile before the html is updated since people are busy
updating the new server software.
It should say the following:
k < 10000000 and 0 < min(k,990*10^4k) < 10^4.
Sorry about the mistake. I will be much more careful the next time.
What happened is my problem tester increased the dataset,
but I didn't submit the correctly updated html file. Even
my solution got TLE, until I submitted his code.
Unfortunately, no one asked for clarification on this problem
during the contest. Hey, on the bright side, maybe someone
come up with a BPP formula for sqrt(2) and win the Fields medal.

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Re: Correction
OK, now solved only in 0.01 sec.baodog wrote:The input specification is incorrect due to a mixup.
I have already sent in a correction, but it may be
awhile before the html is updated since people are busy
updating the new server software.
It should say the following:
k < 10000000 and 0 < min(k,990*10^4k) < 10^4.
Sorry about the mistake. I will be much more careful the next time.
Are you also a member of Elite Problemsetters? Try to avoid Shahriar Manzoor, because he is the top of the leader of posting wrong problems.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Re: Correction
Hehe! I should not be replying this.Robert Gerbicz wrote: OK, now solved only in 0.01 sec.
Are you also a member of Elite Problemsetters? Try to avoid Shahriar Manzoor, because he is the top of the leader of posting wrong problems.
When you post most number of problems, statistically you will make most mistakes.
Most wrong problems posted by me were before the formation of Elite Panel. So there is nothing to relate the Elite Panel with making mistakes.