January 2008 - mathfun@mailman.xmission.com

Re: [math-fun] xkcd points out dangers of math fun
by Eugene Salamin 06 Jan '08

06 Jan '08

On a square grid of 1 ohm resistors, the effective resistance between the node at (0,0) and the node at (p,q) is given by the following expression. R[p,q] = (1/(4 pi^2)) int (F(x,y), x=-pi..pi, y=-pi..pi), F(x,y) = [1 - cos(p x + q y)] / [2 - (cos x + cos y)]. This can be generalized to the cubic array in d dimensions. R[p[1], ... , p[d]] is (2 pi)^(-d) times the integral over [-pi, pi]^d of the fraction whose numerator is 1 - cos(p[1] x[1] + ... + p[d] x[d]), and whose denominator is d - (cos x[1] + ... + cos x[d]). Gene ____________________________________________________________________________________ Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ

1 0

Re: [math-fun] xkcd points out dangers of math fun
by Eugene Salamin 06 Jan '08

06 Jan '08

----- Original Message ---- From: Steve Witham <sw(a)tiac.net> To: math-fun(a)mailman.xmission.com Sent: Saturday, December 15, 2007 3:32:41 PM Subject: [math-fun] xkcd points out dangers of math fun Here's a comic with an interesting random-walk problem: http://www.xkcd.com/356/ --Steve _______________________________________________ On a square grid of 1 ohm resistors, the effective resistance between the node at (0,0) and the node at (p,q) is given by the following expression. R[p,q] = (1/(4 pi^2)) int (F(x,y), x=-pi..pi, y=-pi..pi), F(x,y) = [1 - cos(p x + q y)] / [2 - (cos x + cos y)]. Gene ____________________________________________________________________________________ Never miss a thing. Make Yahoo your home page. http://www.yahoo.com/r/hs

2 1

Re: [math-fun] Proofs without words
by Marc LeBrun 06 Jan '08

06 Jan '08

>Dan Asimov >c) sum of the first n cubes = (sum of first n numbers)^2 Yow! This reminded me I'd forgotten to forward this note a former funster sent back on 6/14: ======== From: Shel Kaphan Subject: How to visualize that a squared triangular number is the sum of cubes Hi Marc, Perhaps you could forward this to math-fun for me, if it still exists. Maybe someone there will enjoy it. Hopefully the fixed width font I "drew" this in will survive email transport. If not let me know and I'll try something different. thanks, Shel Here is how to visualize that a squared triangular number is a sum of cubes: A squared triangular number is a triangle of triangles of the same size, e.g. for n=3: x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x Tri(3)^2 = 36 (where Tri(n) = n(n+1)/2) To go from Tri(n) to Tri(n+1), we add a new row of triangles and increase the size of each existing triangle. E.g., to go from n=3 to n=4: x x x x x x o o o o x x x x x x x x x x x x o o o o o o o o x x x x x x x x x x x x x x x x x x o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o Notice that the last row of triangles can be stacked up as a triangular prism: o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o (this is supposed to be a 3D drawing...) This prism contains Tri(n+1) x (n+1) blobs. To fill out the cube, we would need an additional prism of Tri(n) x (n+1) blobs. This is the number of blobs added to the bottoms of the triangles in the diagram for Tri(n)^2 when we increased it to Tri(n+1)^2 (i.e., the o's added to the bottoms of the triangles of x's in the diagram above). So, Tri(n+1)^2 = Tri(n)^2 + (n+1)^3

1 0

[math-fun] Re: xkcd points out dangers of math fun
by Steve Witham 05 Jan '08

05 Jan '08

>From: James Propp <jpropp(a)cs.uml.edu> > >Steve Witham wrote: > >>Here's a comic with an interesting random-walk problem: >> >>http://www.xkcd.com/356/ > >The problem in question was > >>On an infinite square lattice with equal unit resistances along each edge, >>find the resistance between two nodes at a knight's move from one other. > >Nobody's described the precise connection with random walks, People might have thought it had to do with absent-minded mathematicians crossing the street in the comic. I didn't think of that. Might be fun to work into the joke or the problem. >By the way, what Fred Lunnon calls "admittence", namely the reciprocal >of resistance, is something I always thought was called "conductance". >Is this ones of those transatlantic terminological differences? Ask nice and Google replies in two first hits: >[Admittence] > >Did you mean: admittance? > >[yes] > >Admittance - Wikipedia, the free encyclopedia >In electrical engineering, the admittance (Y) is the inverse of the >impedance (Z). Impedance is complex whereas resistance is real. You're right, conductance is the inverse of plain resistance. Wouldn't it be faster to set some initial weights (absolute voltages) over the grid and just loop redistributing weights among neighbors while always resetting the two endpoints to 1 and 0 (resp.)? (And then run the result through Plouffe's Inverter for an added touch of magic before turning in your answer.) --Steve It's very dark and after 23:59.

1 0

Re: [math-fun] xkcd points out dangers of math fun
by Eugene Salamin 05 Jan '08

05 Jan '08

----- Original Message ---- From: Christoph Pacher <christoph.pacher(a)arcs.ac.at> To: math-fun <math-fun(a)mailman.xmission.com> Sent: Friday, January 4, 2008 11:44:17 AM Subject: Re: [math-fun] xkcd points out dangers of math fun Fred lunnon wrote: > Thinking about this, though --- what happens in the original problem > if we replace "1 ohm" by "1 microF" ? > > Presumably probabilistic simulations _do_ depend in an essential way > on the resistances being real? There should not happen much. The impedance of an (ideal) capacitor is Z=-i/(2 pi f C). The -i corresponds just to a phase shift of Pi/2 between voltage and current and can be ignored for the moment. 1/(2pi f) is a constant factor which you take out now and plug in at the end (if you are interested in the impedance and not the capacity). Thus you basically replace 1 Ohm with the inverse of 1microF in the "standard calculation" and take the inverse at the final result again. How you obtain the standard calculation (probabilistic or not) is of course not important. Christoph _______________________________________________ Yes, that's completely correct. The effective resistance between two nodes in the resistor network is a homogeneous function of degree 1 in the individual resistances. When all the resistances are equal, Reff = k R, for some positive constant k. If R is replaced by an impedance Z, then Zeff = k Z. Gene ____________________________________________________________________________________ Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping

1 0

Re: [math-fun] Proofs without words
by Michael Reid 04 Jan '08

04 Jan '08

> ____ > /\ \ > ____/ \___\ > /\ \ / / > ____/ \ \/___/ > /\ \ \ \ > ____/ \ \ \_______\ > /\ \ \ \ / / > / \ \ \ \/_______/ > \ \ \ \ \ > \ \ \ \___________\ > \ \ \ / / > \ \ \/___________/ > \ \ \ > \ \_______________\ > \ / / > \/_______________/ the reference is: giorgio goldoni, a visual proof for the sum of the first n squares and for the sum of the first n factorials of order two, mathematical intelligencer, v. 24, no. 4 (2002) pp. 67-69. try this url: http://tinyurl.com/2vgsuo (it might require some proxy access, i'm not certain about that.) mike

1 0

Re: [math-fun] xkcd points out dangers of math fun
by James Propp 04 Jan '08

04 Jan '08

Steve Witham wrote: >Here's a comic with an interesting random-walk problem: > >http://www.xkcd.com/356/ The problem in question was >On an infinite square lattice with equal unit resistances along each edge, >find the resistance between two nodes at a knight's move from one other. Nobody's described the precise connection with random walks, so I'll bring this into the conversation: the effective resistance between (0,0) and (1,2) is equal to the reciprocal of 4p, where p is the probability that a random walker who starts at (0,0) will hit (1,2) before returning to (0,0). (With probability 1, the walker will eventually hit one or the other.) Here 4 arises as the sum of the reciprocals of the resistances on the edges incident to (0,0). If we used (1,1) in place of (1,2), the probability in question would be Pi/8. If you want to know why this equality is true, see Doyle and Snell's "Random Walks and Electric Networks", available at math.PR/0001057. By the way, what Fred Lunnon calls "admittence", namely the reciprocal of resistance, is something I always thought was called "conductance". Is this ones of those transatlantic terminological differences? I asked Google, and it gave 0 results for "electrical admittence", about 5700 results for "electrical admittance", and about 76300 results for "electrical conductance". To determine whether use of admittance vs. conductance correlates with geography, we'd need a hybrid of the Google search engine with Google Maps that instead of just counting hits would show us a map of the world with each hit represented by a red dot at the physical location hosting the site. :-) In any case, one way to estimate the effective resistance is to estimate p. How might we do this? If we do a pseudorandom simulation of n runs of random walk, and let k be the number of successes (where success is defined as the event that the walker hits (1,2) before hitting (0,0)), then k/n should be close to p, with an error on the order of 1/sqrt(n). To get our error down to 1/10^5, we'd need to do ~ 10^10 runs, which is clearly not feasible. Of course, we could exploit parallelism and do 10^10 runs in tandem. (We don't have to follow the 10^10 walkers individually; we just need to know how many are at a given node at each time-step.) The trouble is that some of the 10^10 walkers won't hit either (0,0) or (1,2) within a computationally feasible amount of time. (In fact, it'd take about exp(10^10) steps for all the walkers to get absorbed!) So our estimate will be an interval [k/n,k'/n] rather than a single number. Some of the error comes from the width of this interval; other error comes from the randomness in the procedure. A better way is to numerically simulate a discrete-time deterministic mass-flow in which 1 unit of mass enters the system at (0,0) at the start and flows through the system according to the rule that the mass at a node gets divided equally among its four neighbors at the next time-step, with mass exiting the system at (0,0) and (1,2). If you could do this for an infinite number of steps, the amount of mass leaving the system via (1,2) and via (0,0) would be p and 1-p, respectively. If you simulate the flow for n steps, then (leaving aside rounding error) your error will be bounded by the amount of mass that doesn't get absorbed in the first n steps. (Peter Doyle tells me that the real industrial-strength way to solve many problems of this sort is with something called the conjugate gradient method. I haven't had time to learn this technique, but if you want to, check out http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf ; Shewchuck's write-up looks quite friendly.) If I were applying for a job at Google, I'd probably try to get an approximation to p via the rotor-router method of deterministically estimating characteristics of random processes (on the assumption that the hiring committee is more interested in seeing originality than perfect mathematical precision). For a description of rotor- routing, see Michael Kleber's article "Goldbug Variations" in the Winter 2005 issue of The Mathematical Intelligencer (available at http://people.brandeis.edu/~kleber/Papers/rotor.pdf) If you go to http://www.cs.uml.edu/~jpropp/rotor-router-model/, click on "The Applet", set the Graph/Mode selector to "2-D Walk", and press "Paused (Press to Resume)", you'll see how rotor-routing can be used to get decent approximations to Pi/8. (When you get bored, hit "Running (Press to Pause)" and change "1 Step" to "1 Stage" or "10 Stages" or "100 Stages".) What works for (1,1) should work for (1,2), so I expect that 10^5 runs of rotor-router walk with emission at (0,0) and absorption at (0,0) and (1,2) would give an estimate of p with an error on the order of 1 part in 10^5. (The best result I can prove is that the error for n runs goes like (log n)/n or smaller, but for values of n at least up through 10^4, that log n might as well be replaced by a small constant like 2, as far as I can tell.) This sort of simulation can be parallelized, so I suspect 10^5 runs would be feasible, though the set of sites visited would be a square of size roughly 10^5 by 10^5, so keeping track of all the rotor-settings might be a problem unless one used an intelligent scheme of memory-management (making use of the fact that throughout large patches of the square, the rotor setting is locally constant). I can give more details (and maybe even try to do the simulation) if people are interested. Jim Propp

5 4

Re: [math-fun] church of the sub-genus?
by James Propp 04 Jan '08

04 Jan '08

I wrote: >More precisely, I claim that the natural way to build >up the set of such maps uses 2 vertices (0-cells), >6 edges (1-cells), 18 faces (2-cells), 54 3-cells, >etc. I forgot to give the details of this. The (open) k-cells consist of all the polyhedral functions from (0,1) to {0,1} with exactly k points of discontinuity. There are only two polyhedral functions from (0,1) to {0,1} with 0 points of discontinuity, namely the constant function 0 and the constant function 1. These are the two 0-cells. The functions with 1 point of discontinuity are of the form { a if t < t_1 f(t) = { b if t = t_1 { c if t > t_1 where t_1 is some element of (0,1) and a,b,c are elements of {0,1} not all equal to one another. There are 2^3-2=6 ways to choose a, b, and c, and for each such choice, we get a 1-cell isomorphic to (0,1). So we have 6 1-cells. The functions with 2 points of discontinuity are of the form { a if t < t_1 { b if t = t_1 f(t) = { c if t_1 < t < t_2 { d if t = t_2 { e if t > t_2 where t_1 < t_2 are elements of (0,1) and a,b,c,d,e are elements of {0,1}, with a,b,c not all equal to one another and c,d,e not all equal to one another. There are 18 ways to choose a, b, c, d, and e, and for each such choice, we get a 2-cell isomorphic to the open triangle {(t_1,t_2): 0 < t_1 < t_2 < 1}. So we have 18 2-cells. Etc. I want to add that my proposed method of computing an Euler measure for infinite dimensional polytopes of this kind is not accompanied by any supporting geometrical ideas. It's just a system of formal noodling that points to the possibility of extending the definition of Euler measure beyond where it has gone before (and perhaps beyond where it ought to go). Jim Propp

1 0

Re: [math-fun] xkcd points out dangers of math fun
by Eugene Salamin 04 Jan '08

04 Jan '08

----- Original Message ---- From: Tom Knight <tk(a)csail.mit.edu> To: math-fun <math-fun(a)mailman.xmission.com> Sent: Friday, January 4, 2008 8:00:22 AM Subject: Re: [math-fun] xkcd points out dangers of math fun On Jan 4, 2008, at 10:39 AM, James Propp wrote: > > By the way, what Fred Lunnon calls "admittence", namely the reciprocal > of resistance, is something I always thought was called "conductance". > Is this ones of those transatlantic terminological differences? I > asked Google, and it gave 0 results for "electrical admittence", about > 5700 results for "electrical admittance", and about 76300 results for > "electrical conductance". To determine whether use of admittance vs. > conductance correlates with geography, we'd need a hybrid of the > Google search engine with Google Maps that instead of just counting > hits would show us a map of the world with each hit represented by > a red dot at the physical location hosting the site. :-) > Admittance is the AC (complex) extension of conductance. Resistance is to Impedance as Conductance is to Admittance. --------------------- Z = R + i X, Y = G + i B, Y Z = 1, V = Z I, I = Y V. Z = impedance, R = resistance, X = reactance, Y = admittance, G = conductance, B = suceptance, V = voltage, I = current. Z, Y, V, I are complex, R, X, G, B are real. The true physical voltage is Re(V exp(- 2 pi i f t)), with f = frequency, and similarly for current. Some people use +i instead of -i in the exponent. Engineers use j for sqrt(-1). Gene ____________________________________________________________________________________ Never miss a thing. Make Yahoo your home page. http://www.yahoo.com/r/hs

1 0

Re: [math-fun] church of the sub-genus?
by James Propp 04 Jan '08

04 Jan '08

Fred Lunnon writes: >I must say I find this computation most unconvincing! I agree. My intention was to be provocative and elicit appropriate incredulity. A fuller (and hopefully more convincing) account follows. >Not only that, but you include an "F" term appertaining to 3-space, when >your interval is (presumably) considered embedded in 2-space: while this >might be (partially) consistent with a rationalised definition, it is >inconsistent with the one you have used. It's worse than you think. Not only do I append an "F" term, I include infinitely many, since I claim that the set of polyhedral maps from (0,1) to {0,1} (i.e., the set of piecewise constant maps with only finitely many pieces) is most naturally viewed as infinite-dimensional! More precisely, I claim that the natural way to build up the set of such maps uses 2 vertices (0-cells), 6 edges (1-cells), 18 faces (2-cells), 54 3-cells, etc. To compute the "Euler characteristic" of this infinite complex, sum the geometric series 2-6+18-54+... the way Euler would to get 2/(1-(-3)) = 1/2. But an alternate method involves a theorem to the effect that the Euler characteristic of the set of polyhedral maps from polyhedral set S to polyhedral set T is chi(T) to the power of chi(S), which justifies the flimflam about 2 to the power of -1. (Except that I should really say "Euler measure" instead of "Euler characteristic" to make sure nobody gets confused about what I mean.) >In the case of polyhedra [or polytopes generally] the "Euler characteristic" >as commonly defined is defective, in that it omits both the polyhedron itself >and the null element [of dimension d = -1] . I agree about the former, but I'm not sure about the latter. One virtue of Stephen Schanuel's way of looking at Euler measure (which counts the polyhedron but not the null element) is that it's additive (and indeed finitely additive): The Euler measure of a disjoint union of sets is the sum of the Euler measures of the sets themselves. This works for all polyhedral sets (not just compact or even bounded ones). An open k-dimensional cell has Euler measure (-1)^k, so V-E+F-... is just the sum of the Euler measures of the "pieces" of our polytope. Meanwhile, a closed k-dimensional cell has Euler measure 1^k = 1. The formula V-E+F=2 (and its generalization to higher dimensions) follows almost trivially from the additivity property: e.g., you can view a cube as either the disjoint union of 8 0-cells, 12 1-cells, and 6 2-cells (with Euler measure 8-12+6) or as a closed cube minus an open cube (with Euler measure 1-(-1)). Of course, some dirt is being swept under the rug here, but isn't mathematics just the art of sweeping ever-more dirt under ever-smaller rugs? In this case, the sweeping involves iteratively defining 1-dimensional Euler measure, 1-dimensional Euler integration, 2-dimensional Euler measure, 2-dimensional Euler integration, etc., proving a Fubini theorem and whatnot as one goes. I think Rota and Klain's book "Introduction to Geometric Probability" has a nice treatment of this (though it may be in some other papers of Rota). Jim Propp

1 0