11274 - Infinite Resistor Network

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11274 - Infinite Resistor Network

Post by sclo » Wed Sep 12, 2007 8:11 am

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: 11274 Infinite Resistor Network

Post by sclo » Wed Sep 12, 2007 11:12 pm

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
Maybe I should try to use more symmetry argument to find an recursion.

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.

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

I need help on finding res of infinite resistor network

Post by tanaeem » Thu Sep 13, 2007 9:15 am

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)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Thu Sep 13, 2007 5:37 pm

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:
(V1-A)/d(V1,A) + (V1-B)/d(V1,B) = 0
(V2-A)/d(V2,A) + (V2-B)/d(V2,B) = 0
(A-V1)/d(A,V1) + (A-V2)/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=(A-B)/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:
(A-V1)/d(A,V1) + (A-V2)/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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Sep 14, 2007 12:15 am

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.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Fri Sep 14, 2007 1:18 am

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)
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:
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++  	2007-09-11 05:53:48

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Correction

Post by baodog » Fri Sep 14, 2007 9:28 am

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^4-k) < 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.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: Correction

Post by Robert Gerbicz » Fri Sep 14, 2007 3:48 pm

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^4-k) < 10^4.

Sorry about the mistake. I will be much more careful the next time.
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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Sep 15, 2007 7:18 am

It actually takes my program 80 secs to compute the solution.

goodwill
New poster
Posts: 25
Joined: Mon Sep 03, 2007 10:54 am

Post by goodwill » Mon Sep 17, 2007 6:09 am

Is there other way to compute the kth digit instead of storing the first and last 10^4 digits?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Sep 17, 2007 6:57 am

goodwill wrote:Is there other way to compute the kth digit instead of storing the first and last 10^4 digits?
You'll get the fields medal if you can figure that out.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Re: Correction

Post by shahriar_manzoor » Tue Sep 18, 2007 10:42 am

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.
Hehe! I should not be replying this.

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.

Post Reply

Return to “Volume 112 (11200-11299)”