February 2006 - mathfun@mailman.xmission.com

Re: [math-fun] batting averages
by Michael Reid 27 May '06

27 May '06

> SHOULDA > wrote: > At minimum, > (c74) block([keepfloat:true],linsolve((2*integer+1)/(5*integer+3)=0.3985)) > > (d74) [integer = 26.066] > > (c75) subst(ceiling(%),5*integer+3) > > (d75) 138 > Serves me right for not using continued fractions. > at bats. ok, that looks better. but how do you get the form (2n + 1) / (5n + 3) ? is there some way without continued fractions? btw, the c.f. method i described before can be cleaned up slightly. to find the "simplest" rational number in the closed interval [a, b] , compute the convergents for the cf's of a and b . suppose p/q and P/Q are the last two they have in common. then the next convergent for each will be of the form (p + Pn) / (q + Qn) for some positive integer n . if the simpler of these two is in the target interval, then that's the one. otherwise, replace n by n+1 in its expression as above, and that gives the simplest fraction in the interval. (this may require a and b to be positive, but it's easy to reduce to that case.) mike

2 2

[math-fun] Problem Puzzler 1999
by Christian Boyer 10 May '06

10 May '06

Jean-Paul Delahaye publishes in the new issue of Pour La Science a very interesting article on Sudokus. He asked a very strange Sudoku problem WITHOUT any given numbers, only ">" and "<" signs between cells. He mentions that this problem was published in Puzzler, 1999, and that he does not know the solution. I have the solution, sent this morning to J.-P. Delahaye. Now looking for "Puzzler 1999" on Google, I find that Ed Pegg Jr. wrote an article in September 2005 including the same astonishing puzzle, figure 7 "Greater Than Sudoku" in: http://www.maa.org/editorial/mathgames/mathgames_09_05_05.html Perhaps that somebody else had already the solution? Ed, did you receive a solution to your article? Christian.

3 8

[math-fun] Re: partitions of a set
by James Propp 28 Feb '06

28 Feb '06

> Is there a formula for LP(n) ? > What about an asymptotic formula? Rota's proof of Dubinski's formula, as described in the book "Finite Operator Calculus", is a gem. This little book is one of the reasons I went into combinatorics. Jim Propp

1 0

[math-fun] Stirling Numbers?
by Schroeppel, Richard 28 Feb '06

28 Feb '06

This message is from Dan Asimov, about 10 days ago. The mailing list software didn't like it for some reason. I did some heavy editing to unHTML it, so I may have mangled it. --Rich ---------------------------------------------- Suppose you want to count all possible partitions of the set X_n = {1,2,...,n}. I.e., you want to know how many [collections of mutually disjoint nonempty subsets of X_n] have union = X_n. Ordinary partitions are of course equivalence classes of these "labeled partitions" (my term). ; E.g., for X_5: ordinary partitions: # of corresponding labeled partitions -------------------- -------------------------- 1+1+1+1+1 = 1 1+1+1+2 C(5,2) = 10 1+2+2 5 * C(4,2)/2 = 15 1+1+3 C(5,3) = 10 1+4 C(5,1) = 5 2+3 C(5,2) = 10 5 C(5,5) = 1 ----- total: 52 Is there a formula for LP(n) ? What about an asymptotic formula? --Dan

2 1

[math-fun] squaring a series for pi
by Schroeppel, Richard 28 Feb '06

28 Feb '06

Bill Cordwell has called my attention to a paper by Robin Chapman that collects 14 proofs that zeta(2) [:= sum(1/n^2)] = (pi^2)/6. http://www.maths.ex.ac.uk/~rjc/etc/zeta2.ps (or .pdf) Proof #13 is what I asked for in HAKMEM: The proof squares the double-ended series ... + 1/-3 - 1/-1 + 1/1 - 1/3 + 1/5 - ... (easily seen to be just 2*(pi/4) when summed from the center) and shows equality to the double-ended series ... + 1/9 + 1/1 + 1/1 + 1/9 + 1/25 + ... (which is absolutely convergent) and is equal to (pi^2)/4. From there, it's a quick wave of the hands to get zeta(2) = (pi^2)/6. Chapman credits the proof to the Borweins' book "Pi and the AGM", and, indeed, it is exercise 11 in section 11.3, on page 381. The proof only requires some algebra, the logN estimate for a harmonic sum, and limits. The first move is to clip the series, summing each series from the -(2K+1) term through the 2K+1 term. The term squares cancel, leaving the problem of showing that the cross terms in the squared series sum to a value that approaches 0 as K->infinity. Since the clipped series are finite, there are no nasty worries about conditional convergence. It's a little complicated, but a nice first principles proof. Even the logN estimate is dispensable, being replaceable with an upper bound of, say, sqrtN for the harmonic sum. Rich

1 0

[math-fun] Re: Polyomino question
by Dean Hickerson 28 Feb '06

28 Feb '06

Franklin T. Adams-Watters asked: > What is the smallest polyomino that contains all polyominos of size n? ... > 2n-2 is a simple lower bound, since fitting the general "line" polyomino > requires n in a single row (or column), while the general "snake" > polyomino has only 2 squares in any given row. This bound can be improved by considering 'linear' polyominoes of other slopes. For 0 <= s <= 1, let P(s,n) be an n-omino which approximates a line of slope s. E.g. the straight line polyomino is P(0,n), and the snake is P(1,n). P(1/2,n) looks like a subset of this: ooo ooo ooo ooo ooo ooo ... P(2/3,n) could be a subset of either of these; I don't know which will give the best lower bound: oooo ooo o oo oooo ooo o oo oooo ooo o oo oooo ooo o oo oooo ooo ... ... P(1/2,n) can overlap P(0,n) in at most 3 squares, and overlap P(1,n) in at most 6 squares, so any polyomino that contains P(0,n), P(1,n), and P(1/2,n) has at least n + (n-2) + (n-3-6) = 3n-11 squares. If we also include P(1/3,n), we need at least 4n-31 squares, if I've maximized the intersections correctly: slopes maximum intersection 0 1 2 0 1/2 3 1 1/2 6 0 1/3 4 1 1/3 4 1/2 1/3 12 I'll leave it to someone else to figure out the best choice for P(s,n), a general formula for the maximum intersection of P(s,n) and P(t,n), and the choice of slopes which gives the best lower bound for n-ominoes. Dean Hickerson dean(a)math.ucdavis.edu

3 3

Re: [math-fun] Polyomino question
by Michael Reid 27 Feb '06

27 Feb '06

> What is the smallest polyomino that contains all polyominos of size n? interesting question. a relevant reference: http://www.xprt.net/~munizao/polycover/ (but i'm not sure how far he's taken it.) mike

1 0

[math-fun] Polyomino question
by franktaw＠netscape.net 27 Feb '06

27 Feb '06

What is the smallest polyomino that contains all polyominos of size n? For n = 1 or 2, the value is clearly n. For n = 3, it's 4; either of the following will work: OOO OOO O O For n = 4, there is a unique size 6 polyomino that works: OOOO OO For n = 5, the best I can do is 9: O OOOOO OOO I don't know if this is unique; I would be very surprised if 8 is possible. For n = 6, I can get 12: OO OOOOOO OOOO Again, this may not be unique, and might possibly be improved. For n = 7, the best I've found is 17: OOOOO OOOOOOO OOO OO I would not be at all surprised if there is a solution with 16, but I didn't find one. If 17 is the best, it is not unique; some simple variants of this also work. For n = 8 and beyond, I have no real idea. ---- We can establish a general upper bound from the consideration that a size n polyomino always fits in a k x (n+1-k) box for some k. It follows that sum_{k=1}^{ceiling(n/2)) n+1-k = ceiling(n/2)*(n+floor(n/2)+1)/2 is an upper bound. (This can be improved to ceiling(n/2)*(n+floor(n/2)-1)/2 + 1 by noting that, for k>1, the polyomino cannot occupy all four corners of the box.) This is asymptotically 3/8 n^2. From the very limited data above, it looks more like 1/4 n^2. Even that the sequence grows quadratically is not certain, however. 2n-2 is a simple lower bound, since fitting the general "line" polyomino requires n in a single row (or column), while the general "snake" polyomino has only 2 squares in any given row. Franklin T. Adams-Watters 16 W. Michigan Ave. Palatine, IL 60067 847-776-7645 ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com

1 0

RE: [math-fun] (a1 + a2 + ...)^2 = a1^2 + a2^2 + ... = Pi^2/8
by Schroeppel, Richard 27 Feb '06

27 Feb '06

Fascinating! I had a different objective in mind when I wrote the problem. My goal was to reach the fairly difficult pi^2/6 result using series manipulation, starting from a definition of pi based on 1 - 1/3 + 1/5 - ... or the like. Ideally, one would avoid calculus and complex integrations and the theory of dilogarithms, or Euler's trick with the power series for sin x. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov(a)mailman.xmission.com [mailto:math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com] On Behalf Of Robert Baillie Sent: Wednesday, February 22, 2006 8:39 AM To: math-fun Subject: [math-fun] (a1 + a2 + ...)^2 = a1^2 + a2^2 + ... = Pi^2/8 HAKMEM 239 has this interesting question: "119 (Schroeppel): Can someone square some series for Pi to give the series Pi^2/6 = 1 + 1/2^2 + 1/3^2 + ... ?" Would you settle for squaring a series for Pi/Sqrt(8) to get a series for Pi^2/8? Pi/Sqrt(8) = 1 + 1/3 - 1/5 - 1/7 + 1/9 + 1/11 --++ ... Pi^2/8 = 1 + 1/3^2 + 1/5^2 + 1/7^2 + 1/9+2 + 1/11^2 + ... Also, notice that you can square the first series by adding the squares of the individual terms! I first noticed this by comparing exercises 6a and 6b on page 398 in Wilfred Kaplan's "Advanced Calculus". The series for Pi/Sqrt(8) comes from the Fourier series for f1(x) = 0 for -Pi <= x < 0, f(x) = 1 for 0 <= x <= Pi. The series is f[x_] := (1/2) + (2/Pi) Sum[ Sin[(2n-1)x]/(2n-1), {n, 1, Infinity}] f[Pi/4] gives the series for Pi/Sqrt[8]. The series for Pi^2/8 comes from the Fourier series for g1(x)= Abs[x], -Pi <= x <= Pi. g[x_] := (Pi/2) - (4/Pi) Sum[ Cos[(2n-1)x]/((2n-1)^2), {n, 1, Infinity}] g[0] gives the series for Pi^2/8. _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

3 2

[math-fun] Smallest bimagic square: unknown!
by Christian Boyer 27 Feb '06

27 Feb '06

A magic square is bimagic if it remains magic after squaring each of its integers. The smallest bimagic squares using consecutive integers are known: 8x8. BUT... the smallest bimagic squares using distinct integers (= not forced to be consecutive) are still unknown! 5x5, 6x6, 7x7??? If 5x5 is impossible, a proof??? Edouard Lucas was the first to work on the subject, in 1891, easily proving that 3x3 is impossible. For more information, go to www.multimagie.com/indexengl.htm Click on "Magic squares of squares" in the left menu, then click on "Open problems". And, from this table, you will find the current status of the research. Any help or idea on the subject is welcome! Christian.

1 1