October 2007 - mathfun@mailman.xmission.com

[math-fun] Smallest magic squares of powers
by Christian Boyer 01 Sep '08

01 Sep '08

Oct 7th, 2007: the smallest known magic square of 4th powers is now a 44x44 square constructed by Jaroslaw Wroblewski (Poland) and Hugo Pfoertner (Germany). Jaroslaw built the semi-magic square in June, then Hugo needed a very impressive computing job of 3 months, on 57 processors of a SGI computer http://www.sgi.com/products/remarketed/origin3000/, in order to find two magic diagonals in this square! A big progress, because the previous smallest known was a 243x243 square, coming from the 243x243 tetramagic square of Pan Fengchu (China). The best known results, and their first authors, are now: Magic square Smallest known ------------ --------------- Of squares 4x4 (Euler, 1770) Of cubes 9x9 (Boyer, 2006) Of 4th powers 44x44 (Wroblewski-Pfoertner, 2007) Of 5th powers 729x729 (from the pentamagic square of Li Wen, 2003) ON ANY POWER, WE DO NOT KNOW WHAT THE SMALLEST POSSIBLE MAGIC SQUARE IS! For example, as you know, we still do not know if a 3x3 magic square of squares is possible... 4x4, 5x5, 6x6, 7x7, and 8x8 magic squares of cubes are unknown... And the problem of the diagonals is extremely difficult, as proved by the impressive computing search of Hugo. It remains a big gap between the smallest known magic and semi-magic squares (=with or without magic diagonals) of 4th powers: 44x44 versus 4x4... Here is the 4x4 semi-magic square of 4th powers (Morgenstern-Boyer, 2006): 14101^4 938^4 931^4 37762^4 35866^4 20881^4 21038^4 13393^4 24806^4 30191^4 30418^4 9263^4 413^4 32026^4 31787^4 1106^4 Christian.

2 2

Re: [math-fun] How we "do mathematics"
by Eugene Salamin 02 Feb '08

02 Feb '08

----- Original Message ---- From: David Gale <gale(a)math.berkeley.edu> To: math-fun <math-fun(a)mailman.xmission.com> Sent: Thursday, August 9, 2007 3:17:48 AM Subject: RE: [math-fun] How we "do mathematics" ... >A (very) old one I like : > >Two Death Valley marathonians friends complete their run >together and seek shadow in their tent nearby the finish >line. > >The first one had prepared a fresh 5-liter tank of water >in a cooling box and his friend a similar 3-liter one. > >They were about to start drinking when a journalist enters >the tent desperately asking for water. > >OK, the water is divided into three equal parts -- and drunk. > >The thankful journalist insists to pay his share and leaves >8 dollars to be split between the two friends. > >How? > >---- Why is this problem so fascinating? The two friends are paid $8. The guy who contributed 5 l gets $5, and the guy who contributed 3 l gets $3. Or maybe the $8 goes towards paying for their campsite. I must be missing something. Gene ____________________________________________________________________________________ Pinpoint customers who are looking for what you sell. http://searchmarketing.yahoo.com/

5 4

Re: [math-fun] Compute a Function From its Fourier Series?
by Bill Gosper 17 Jan '08

17 Jan '08

GFee>See the following paper. >Authors: Gottlieb and Shu Title: On the Gibb's phenomenon and its resolution Journal: SIAM Review Issue: Vol.39, No. 4, pages 644-668, December 1997 Also see http://www.tweedledum.com/rwg/gibbs.htm --rwg --------------------------------- Tonight's top picks. What will you watch tonight? Preview the hottest shows on Yahoo! TV.

3 10

[math-fun] nice little sin(a+b+c+...) formula
by Bill Gosper 03 Nov '07

03 Nov '07

n n ==== /===\ \ k | | %pi k > (- 1) | | 2 sin(a - -----) n / | | j n + 1 ==== ==== j = 0 \ k = 0 sin( > a ) = ------------------------------------, / k 2 (n + 1) ==== k = 1 where %pi n a := -----. 0 2 There are n^2 sins on the right, vs n2^(n-1) for the usual addition formula. But all n^2 sins are different, vs only 2n species for the usual formula. E.g., for n=3, %pi %pi sin(a + a + a ) = - sqrt(2) sin(a + ---) sin(a + ---) 3 2 1 1 4 2 4 %pi %pi %pi %pi sin(a + ---) - sqrt(2) sin(a - ---) sin(a - ---) sin(a - ---) 3 4 1 4 2 4 3 4 + 2 sin(a ) sin(a ) sin(a ) 1 2 3 = - sin(a ) sin(a ) sin(a ) + cos(a ) cos(a ) sin(a ) 1 2 3 1 2 3 + cos(a ) sin(a ) cos(a ) + sin(a ) cos(a ) cos(a ) 1 2 3 1 2 3 We can trade # of terms vs # of species by applying the new(?) formula recursively, e.g., a_1 = b_11+b_12+b_13, a_2= b_21+b_22+... . --rwg __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

6 9

[math-fun] generalized Pythagorean theorem
by James Propp 01 Nov '07

01 Nov '07

By the way, can anyone give me a reference for the generalization of the Pythagorean theorem that says that squared k-dimensional volume of a flat k-dimensional object sitting in n-space is the sum of the squared k-dimensional volumes of the k-dimensional shadows that the object casts in the n-choose-k different directions associated with an orthogonal coordinate frame? For instance, spin a coin in the air; the shadows that it casts on the floor and two perpendicular walls will rapidly change, but their squared areas will add up to a constant, namely the squared area of (one side of!) the coin. I seem to recall that this is due to Cayley or Sylvester or someone like that. But I'm more interested in where an interested math major might read about this result, rather than who first noticed it. (Surely there's an American Mathematical Monthly or Mathematics Magazine article about this!) Jim Propp

4 3

[math-fun] Re: random walk
by Steve Witham 31 Oct '07

31 Oct '07

>Bill Cordwell asks: >I'm looking for a simple derivation of the probability that a random >walk starting at 0, with unit steps, will ever end up to the left of 0. >Probability that the person goes to the left (towards the negative) at >any step is p. >From: Dan Asimov <dasimov(a)earthlink.net> > >Let L be the desired probability: that the walk ever reaches -1. > >Then > L = p + (1-p) L^2 >[...] > L = (1-sqrt(1-4p(1-p))) / 2(1-p), > >which simplifies to > > L = (1-|2p-1|) / 2(1-p). > >Considering the cases p >= 1/2 and p <= 1/2 separately: >------------------------------- >L(p) = 1 if p >= 1/2, >and >L(p) = p/(1-p) if p <= 1/2. >------------------------------- When I see a solution to a problem, I would like to figure out the way to look at it that leads to the solution "obviously". I have this half-Pascal's-triangle in my mind and Dan's rationale... >...since if the first step is to the right, the probability of >then ever reaching -1 requires first ever reaching 0 (prob = L by >translation-invariance) and then ever reaching -1 from there (L again). ...doesn't immediately dispel it or show me how to fix it. But... ARGUMENT 1: the probability of eventually going left, L = is the probability that you will... p go left or + qL p right, then eventually left, then left, or + (qL)^2 p right, eventually left, right, eventually left, left, or + (qL)^3 p ... = p + qL( p + qLp + (qL)^2 p ... ) = p + qL^2 ARGUMENT 2: L is the probability that this procedure will terminate: def getLeftOf(x): while rnd() >= p: getLeftOf(x+1) The while loop can be written tail-recursively: def getLeftOf(x): if rnd() >= p: // escape probability p // else (1-p) getLeftOf(x+1) // x L getLeftOf(x) // x L Dan's solution and my embellishments are examples of dealing with infinity by mapping a set one-to-one with a subset of itself ;-) --Steve

1 0

[math-fun] garden paths
by Marc LeBrun 31 Oct '07

31 Oct '07

Similarly: I've wondered how many other folks have leapt to hypothesizing, from hand-working initial cases, that the partitions were the primes? Any other fun examples?

2 1

[math-fun] a question from Raymond Boute
by James Propp 31 Oct '07

31 Oct '07

Raymond Boute asked me (by private email): > ... > I would appreciate your help > in retrieving the following puzzle. Most likely it appeared as part of > an article in the "American Mathematical Monthly" (possibly, but less > likely CMJ or Mathematical Magazine). > > The problem was combinatorial, the problem statement and the initial > solution given were simple and the solution appeared free of > pitfalls. However, the unique feature, which I never saw in any other > problem, was that this solution broke down if the basic parameter (possibly > some number of persons in the problem statement) reached a certain value > that was significantly larger than one would expect for a smallest > counterexample (several dozens or perhaps even several hundreds). > > Admittedly this description is very vague, but if you ever saw the problem, > you probably remember it. Otherwise it is looking for a needle in a > haystack, and I do not ask you wasting time in searching. Does anyone have any idea what problem Raymond is thinking of? Jim

2 1

Re: [math-fun] random walk
by James Propp 31 Oct '07

31 Oct '07

Bill Cordwell (oops, I called him "Bill Cardwell" in my previous message; sorry, Bill!) wrote: >I'm looking for a simple derivation of the probability that a random >walk starting at 0, with unit steps, will ever end up to the left of 0. >Probability that the person goes to the left (towards the negative) at >any step is p. I'll mention that for p = 1/3 (and for other nice values of p, but let's stick with p = 1/3) there's a cute way to "derive" the answer to Bill's question with a gadget that derandomizes random walk (although one needs to support this derivation with a proof showing that the derandomized procedure always gives the correct answer). The states of the gadget are infinite strings of 0's, 1's, and 2's. Image a bug that does a walk on such a string. It goes to the left when it sees a 2 and it goes to the right when it sees a 0 or a 1, and after a bug leaves a location, the number in that location increments by 1 mod 3. So if the initial string is 2 2 2 2 2 ... ^ with the bug at the left (as marked by the "^"), then the bug will fall off to the left at the next step, giving 0 2 2 2 2 ... ^ Now add a second bug at the leftmost location: 0 2 2 2 2 ... ^ It moves to the right (and the leftmost symbol increments): 1 2 2 2 2 ... ^ Then the bug moves to the left: 1 0 2 2 2 ... ^ Then the bug moves to the right: 2 0 2 2 2 ... ^ At this stage, we recognize that we're in the same situation as we were when we added the second bug (shifted over one position), so we can see what the second bug will do from now on: right-left-right, right-left-right, right-left-right, etc. After the second bug has wandered off to infinity, the state of the system looks like 2 2 2 2 2 ... again. So if we add a third bug at the far left, it'll do what the first bug did, and a fourth bug will do what the second bug did, etc. Since half of the non-randomly walking bugs fall off to the left, we conclude that the probability of a randomly walking bug falling off to the left is 1/2. (As I said above, this conclusion needs to be supported by a proof, but the proof isn't hard.) If you start with a different initial string of 0's, 1's, and 2's, the result is almost the same: the second bug might not do the opposite of what the first bug did, but the third bug will do the opposite of what the second bug did, and the fourth bug will do the opposite of what the third bug did, etc. So it's still true that the proportion of the bugs that fall off to the left goes to 1/2, and the error in our derandomized estimate of the probability L falls like O(1/n). In contrast, a truly random simulation would give estimates of the probability L with error like O(1/sqrt(n)). For more about bugs walking on an infinite string of 0's, 1's, and 2's, see pages 81 and 91-93 of Peter Winkler's book "Mathematical Puzzles: A Connoissuer's Collection" (though the statement of the problem given in the book deliberately hides some of the structure by replacing the three numbers by three colors). To learn about a related but harder problem that also illustrates the link between random walk and "derandomized walk with rotor- routers", see Michael Kleber's very nice article "Goldbug Variations": http://people.brandeis.edu/~kleber/Papers/rotor.pdf For more on the rotor-router approach to derandomization (which I'm developing jointly with Ander Holroyd and Lionel Levine), see http://faculty.uml.edu/jpropp/quasirandom.html If you're in the Boston area, you can attend a talk by Levine this coming Friday, described at http://www-math.mit.edu/~combin/ Jim Propp

1 0

Re: [math-fun] random walk
by James Propp 31 Oct '07

31 Oct '07

Bill Cardwell wrote: >I'm looking for a simple derivation of the probability that a random >walk starting at 0, with unit steps, will ever end up to the left of 0. >Probability that the person goes to the left (towards the negative) at >any step is p. Dan Asimov replied: >Let L be the desired probability: that the walk ever reaches -1. > >Then > L = p + q*L^2 > >(q = 1-p), since if the first step is to the right, the probability of >then ever reaching -1 requires first ever reaching 0 (prob = L by >translation-invariance) and then ever reaching -1 from there (L again). > >Which gives L = (1+-sqrt(1-4pq)) / 2q. > >The + sign would give probabilities > 1, so the answer must be > > L = (1-sqrt(1-4pq)) / 2q. This is a nice slick way to rule down the set of possible answers, but it's not a complete analysis. In the case where p is 1/2 or less, the + sign gives (1+|2p-1|)/2(1-p) = (1+1-2p)/2(1-p) = 1, which is not > 1. So it takes a bit more work to show that when p is less than 1/2, the answer to Bill's question is p/(1-p) rather than 1. (Unless I'm missing something here.) The way I filled this gap in the probability class that I'm teaching this semester is by looking at the analogous problem on a finite interval, and asking "What's the chance that the walker falls off by going to the left of the leftmost point, as opposed to going to the right of the rightmost point?". (Of course, one also has to show that with probability 1, one of these two outcomes will occur!) Then one takes the limit as the size of the interval goes to infinity. Jim Propp

1 0