March 2012 - mathfun@mailman.xmission.com

Re: [math-fun] Tiling a square
by Stuart Anderson 01 Mar '12

01 Mar '12

Hi Kerry, Although you are asking about a 16x16 square dissection, there is a parity test that can be applied when attempting a tiling of an odd sized square with squares of given sizes; Firstly reduce the sizes of the squares by their greatest common divisor then count the number of odd squares. Joseph DeVincentis noticed that the numbers of odd squares that can appear are restricted to 1 mod 4 http://www.mathpuzzle.com/partridge.html " I noticed that many of my best solutions for odd-sided squares (which was all of them, because composite-sided squares could invariably be done best as a blown-up version of the solution for their smallest factor) had exactly 5 odd-sided squares, and this was the minimum number of such squares by a parity argument. The area of a square of odd integer side is congruent to 1 mod 4, and the area of an even square is 0 mod 4. Thus, to fill this square, you need a number of odd squares that is 1 mod 4, and the smallest value, 1, could only be done using the degenerate solution of filling the square with a square, because of the parity issue in every row and column. The next smallest possible value was 5, and many of my solutions exhibited this, with an arrangement of odd squares that consisted of one large odd square in each of two opposite corners, and 3 smaller squares that formed an L-shaped path between those two, arranged so that each column and each row contained either 1 or 3 odd squares." Stuart Anderson > > Message: 3 > Date: Wed, 29 Feb 2012 13:27:15 -0700 > From: Kerry Mitchell <lkmitch(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: [math-fun] Tiling a square > > Hi all, > > I know that 7 * 5^2 + 9 * 3^2 = 16^2, which suggests that 7 5x5 squares > plus 9 3x3 squares can possibly tile a 16x16 square. Is there a relatively > simple way to figure out if either: a) no, they won't, or b) yes, and > here's how? Ideally, I'd like to learn the process, not just the answer, > as I will probably have other combinations to consider. > > Thanks, > Kerry Mitchell > -- > lkmitch(a)gmail.com > www.kerrymitchellart.com >

1 0

[math-fun] Correction re Geometry of the Weierstrass ℘ function
by Dan Asimov 01 Mar '12

01 Mar '12

I wrote: << Then P(z+w) = P(z) for all w in C and all v in L. This should have read: << Then P(z+w) = P(z) for all z in C and all w in L. Sorry about that. --Dan ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] Geometry of the Weierstrass ℘-function
by Dan Asimov 01 Mar '12

01 Mar '12

Don't know whether ℘ will show up in most people's e-mail, so I'll use P. ((( In case you don't know it: The Weierstrass P-function is a meromorphic function that's doubly-periodic on the complex plane C. P(z) depends on a choice of lattice L in C (an additive subgroup generated by two periods w1 and w2 with WLOG Im(w2/w1) > 0). Then P(z+w) = P(z) for all w in C and all v in L. The definition is P(z) := 1/z^2 + Sum_{w in L'} (1/(z-w)^2 - 1/w^2), which doesn't make its double-periodicity immediately obvious. It's important because all doubly-periodic (w.r.t. L) meromorphic functions are rational functions of P(z) and its derivative P'(z). ))) P(z) can be thought of as a holomorphic map T^2 -> S^2, where these are the Riemann surfaces C/L and C u{oo}, resp. T^2 comes from identifying the opposite sides of a period parallelogram (whose vertices lie at, say, 0, w1, w2, and w1+w2). To see what P(z) does geometrically, chop the parallelogram into 8 congruent acute triangles (or else right, if the parallelogram is a rectangle). Take 4 of these triangles and make a tetrahedron with them as faces. Then T^2 (also thought of as made of the 8 triangles) can be mapped onto the tetrahedron so each triangle goes isometrically onto a face. The vertices of these triangles on T^2 number 4 in total, around each of which there are 6 triangles. The 3 opposite pairs each are mapped to the same face of the tetrahedron, so the 6 "go around twice". Finally, map the tetrahedron onto the sphere by mapping each face onto the unique spherical triangle with exactly double the angles; these 4 spherical triangles fit together exactly to make the usual S^2. I haven't seen this mentioned in the usual literature on the P-function, so thought it was worth mentioning. --Dan ________________________________________________________________________________________ It goes without saying that .

1 0

Re: [math-fun] Tiling a square
by Michael Reid 01 Mar '12

01 Mar '12

> I know that 7 * 5^2 + 9 * 3^2 = 16^2, which suggests that 7 5x5 squares > plus 9 3x3 squares can possibly tile a 16x16 square. Is there a relatively > simple way to figure out if either: a) no, they won't, or b) yes, and > here's how? Ideally, I'd like to learn the process, not just the answer, > as I will probably have other combinations to consider. 3x3 and 5x5 squares tile all m x n rectangles such that m and n are sufficiently large, and satisfy * either 3 divides m or 5 divides n , and * either 5 divides m or 3 divides n . (In this particular instance, "sufficiently large" means "at least 8".) See Example 3.9 from my paper "Asymptotically Optimal Box Packing Theorems" in The Electronic Journal of Combinatorics: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r78 A portion of that paper is devoted to expounding on results of the late F.W. Barnes, which do not seem to be as well-known, or as well- understood as they should be. Based on Barnes' work, this type of question is reduced to a simple calculation. It is too much to describe all the details behind it, but hopefully this summary will pique your interest: The set of all m x n rectangles that can be tiled by 3x3 squares is the set of (m, n) satisfying * (either) 3 divides m (or 0 divides n ), and * (either 0 divides m or) 3 divides n . The parenthesized conditions evaluate to "false", but they are there to put the conditions in the proper form. We'll encode these conditions by calling them "restrictions" [3, 0] and [0, 3] . Likewise, the set of all m x n rectangles that can be tiled by 5x5 squares is the set of all (m, n) satisfying the set of restrictions {[5, 0], [0, 5]} . To get the set of all m x n rectangles that can be tiled by 3x3 squares and 5x5 squares together, we wedge together the two sets of restrictions: {[3, 0], [0, 3]} v {[5, 0], [0, 5]} = {[3, 0] v [5, 0], [3, 0] v [0, 5], [0, 3] v [5, 0], [0, 3] v [0, 5]} = {[1, 0], [3, 5], [5, 3], [0, 1]} where the wedge takes the component-wise GCD of the restrictions. Any "restriction" with a 1 evaluates to "true", so can be discarded. Thus we are left with the two restrictions [3, 5] and [5, 3] that I gave above. Satisfying these restrictions is not sufficient to be tileable, but it is sufficient if m and n are large enough (hence the "asymptotically" in my title). For the case where your tiles are two rectangles (using translations only) you may be interested to see the "two bricks theorem" in Packing Boxes with Bricks by Richard J. Bower and T. S. Michael, Math Magazine, (February 2006) v. 79, no. 1, pp. 14-30. ( http://www.jstor.org/stable/27642898 ) Michael Reid

3 2

Re: [math-fun] two geometrical riddles (SPOILER)
by Bill Gosper 01 Mar '12

01 Mar '12

Fred>Bill --- why multiply by pi/4 to define your "mean"? WFL So that mean(x,x) = x instead of 4 x/π. It's legally required by the Federal Bureau of Weighs and Means. --rwg On 3/1/12, Bill Gosper <billgosper(a)gmail.com <http://gosper.org/webmail/src/compose.php?send_to=billgosper%40gmail.com>> wrote:> Jim Propp>>> One tends to think that the random variable associated with the larger> circle would have more variance.> But as many of you have probably figured out by now, the two random> variables have the exact same distribution.>> A more symmetrical way to describe this random variable is as the length of> the vector u-v (or if you prefer u+v), where u and v are plane vectors of> length 1 and 2, respectively, chosen uniformly and independently.>> If you exploit symmetry by choosing u to be a fixed vector of length 1 and> letting v vary over all vectors of length 2, you get one of the two> asymmetric descriptions; if you instead choose v to be a fixed vector of> length 2 and let u vary over all vectors of length 1, you get the other one.>> Jim Propp>>> It's easier than that. Uniform on the circles means uniform angles> wrt x-axix, e.g.> The segment joining (1,0) to 2(cos t, sin t) is obviously congruent to the> one> joining (2,0) to (cos t, sin t), length = sqrt(5 - 4 cos t).>> Interesting: The expected length of the third side of SAS triangle x,t,y> for t uniform in (0,π) is>> (2*(x + y)*EllipticE[(4*x*y)/(x + y)^2])/Pi .>> So (1/2)*(x + y)*EllipticE[(4*x*y)/(x + y)^2] is an interesting sort of> mean.>> --rwg

1 0

Re: [math-fun] two geometrical riddles (SPOILER)
by Bill Gosper 01 Mar '12

01 Mar '12

Jim Propp> One tends to think that the random variable associated with the larger circle would have more variance. But as many of you have probably figured out by now, the two random variables have the exact same distribution. A more symmetrical way to describe this random variable is as the length of the vector u-v (or if you prefer u+v), where u and v are plane vectors of length 1 and 2, respectively, chosen uniformly and independently. If you exploit symmetry by choosing u to be a fixed vector of length 1 and letting v vary over all vectors of length 2, you get one of the two asymmetric descriptions; if you instead choose v to be a fixed vector of length 2 and let u vary over all vectors of length 1, you get the other one. Jim Propp It's easier than that. Uniform on the circles means uniform angles wrt x-axix, e.g. The segment joining (1,0) to 2(cos t, sin t) is obviously congruent to the one joining (2,0) to (cos t, sin t), length = sqrt(5 - 4 cos t). Interesting: The expected length of the third side of SAS triangle x,t,y for t uniform in (0,π) is (2*(x + y)*EllipticE[(4*x*y)/(x + y)^2])/Pi . So (1/2)*(x + y)*EllipticE[(4*x*y)/(x + y)^2] is an interesting sort of mean. --rwg

2 1

Re: [math-fun] two geometrical riddles (SPOILER)
by James Propp 01 Mar '12

01 Mar '12

One tends to think that the random variable associated with the larger circle would have more variance. But as many of you have probably figured out by now, the two random variables have the exact same distribution. A more symmetrical way to describe this random variable is as the length of the vector u-v (or if you prefer u+v), where u and v are plane vectors of length 1 and 2, respectively, chosen uniformly and independently. If you exploit symmetry by choosing u to be a fixed vector of length 1 and letting v vary over all vectors of length 2, you get one of the two asymmetric descriptions; if you instead choose v to be a fixed vector of length 2 and let u vary over all vectors of length 1, you get the other one. Jim Propp

1 0

Re: [math-fun] Slightly harder 15 puzzle
by Bill Gosper 29 Feb '12

29 Feb '12

From: "Erich Friedman" <efriedma(a)stetson.edu> Date: Sun, January 23, 2011 9:41 pm NeilB>> I'd very much like to know whether there is a harder 4x4 of either type. EF>surely a brute force search could answer this for 4x4 and smaller puzzles. though i bet 5x5 puzzles are going to be computationally expensive. not necessarily in solving a given puzzle, but in enumerating the possible puzzles! erich friedman Date: Tue, February 28, 2012 2:55 pm rwg> ... because I've already asked Funster Neil (who owes us his sliding block report) to figure it out for tomorrow. Neil has dutifully blogged it all at http://nbickford.wordpress.com/ At Erich's instigation, Neil did the brute-force search, taking about a cpu month, but with some bugs. He eventually got it down to a few hours and zero(?) bugs. "In the previous post I mentioned several methods that could be used to speed up the finding and exhaustive searching of sliding block puzzles, as well as a candidate for the ‘hardest’ one-piece-goal diagonal-traverse 4×4 sliding block puzzle. I am pleased to say that the various bugs have been worked out of the sliding block puzzle searcher, and that 132 has been confirmed to be the maximum number of moves for a simple simple simple 4×4 sliding block puzzle with no internal walls! (that’s not a lot of qualifiers at all)" I think it's remarkable that Neil found the 132 heuristically way beforehand. And the only solver I'm aware of is Corey Ziegler Hunts! (Rumor: also Nick Baxter?) In the summary picture<http://nbickford.files.wordpress.com/2012/01/best44.png>, note an apparent paradox: 11 pieces 64 moves 12 pieces 73 moves but the 12 piecer is just the 11 piecer with a domino cut in half! I'll spoil it only to the extent of revealing that the explanation is at http://nbickford.wordpress.com/2011/09/20/what-ive-been-working-on-lately/ --rwg

2 1