eklhad@ihnet.UUCP (K. A. Dahlke) (10/12/85)
> If this is quiz time then my all time favorite is: > > Take 12 one ohm resistors and wire them so that they form a 3-D cube with > each resistor on an edge of the cube. What is the total resistance across > the long diagonal? there is an interesting generalization. This question reflects my net.math tendencies, but it *is* an electrical engineering problem, so I will post it here. What is the resistance across the long diagonal of a hypercube of N dimensions. As before, each edge of the cube has a 1 ohm resistance. Express your answer as a function of N. -- When You ferst realise that you're net artical contains spelling and grammatically errors, and sentense fragments. Karl Dahlke ihnp4!ihnet!eklhad
moews_b@h-sc1.UUCP (david moews) (10/19/85)
> What is the resistance across the long diagonal of > a hypercube of n dimensions. > As before, each edge of the cube has a 1 ohm resistance. > Express your answer as a function of n. We can coordinatize the n-cube so that each vertex has as coordinates a vector of length n composed of 1's and 0's. Then by "symmetry", as for the 3-dimensional case, we can short together all vertices with the same number of 1's in their coordinate vectors (since they will be at the same potential). Then for each i, i = 1,...,n, we will have a group of 1-ohm resistors connected in parallel (going from vertices with i 1's to vertices with i-1 1's), and all these groups will be connected in series. Now the number of vertices with exactly i 1's in their coordinate vector is just ( n ) ( ) ( i ), the number of ways of choosing i elements out of n elements. But the number of resistors from a vertex with i 1's to a vertex with i-1 1's is just i times this number (since there are i coordinates that we can change from 1 to 0), so there will be just ( n ) i ( ) ( i ) resistors in group number i; the resistance of group i will be the reciprocal of this, so the total resistance will be n ===== 1 \ ---------- > ( n ) / i ( ) ===== ( i ) i=1 . Using binomial identities, we can simplify this to n-1 ===== 1 1 \ --------- , or if you prefer factorials to binomial - > ( n-1 ) coefficients, you can write this as n / ( ) ===== ( i ) i=0 n-1 ===== 1 \ -- > i! (n-1-i)!. n! / ===== i=0 ( n-1 ) Since for i=1,...,n-2, ( ) >= n-1, we know that for i=1,...,n-2, ( i ) 1 ------- 1 0 <= ( n-1 ) <= --- ( ) n-1, ( i ) so our resistance is between (1+1+(n-2)0)/n = 2/n and (1+1+(n-2)/(n-1))/n = (3 - 1/(n-1))/n; in particular, as n goes to infinity, the resistance goes to zero. (But what's the asymptotic behavior?) For any n-dimensional electrical engineers out there, here are the first few values: n Resistance (ohms) ----------------------------------- 0 0 1 1 2 1 3 5/6 4 2/3 5 8/15 6 13/30 7 151/420 8 32/105 9 83/315 10 73/315 David Moews moews_b%h-sc1@harvard.arpa ...!harvard!h-sc1!moews_b "The Cray-5 can execute an infinite loop in under a minute."