October 2004 - mathfun@mailman.xmission.com

[math-fun] Somehow I got off the list
by Steve Gray 29 Oct '04

29 Oct '04

HI Rich, Please resubscribe me to math-fun. I miss it. Thanks Steve Gray stevebg(a)adelphia.net

2 1

[math-fun] tiling rectangles with rectangles.
by David Gale 26 Oct '04

26 Oct '04

Dylan Thurston writes Can you say a bit more about the proof? I would guess that essentially from the definition of tensor product you can get an algorithm that possibly uses negative area rectangles, and the difficulties are avoiding those? This is exactly correct. Our secret weapon is, POSITIVE BASIS THEOREM. Let {a_1, . ,a_n b} be a set of positive (real) numbers. Then there exists a set {b_1,. . ,b_m} of positive numbers such that 1. The b_i are rationally independent, 2. The a_i are rational linear combinations of the b_i with NON-NEGATIVE coefficients. Such a simple statement! Has anyone seen it before? I won't spoil your fun by giving a proof. I'll try to explain referring to the example below. Verify the rectangles above and below the line have the same symmetric (that is a(x)b = (b(x)a) tensor area * * * * * * * * * * * * * * * * * b-d * * d * * * * * * * * * * * * * * * * * * * a a-c ____________________________________________________________ * * * * * * * b-c * * * * * * * b * * c * * * * * * * * * * * * * a-e * * a-e-c * * * * e In the Example the heights and widths of the 5 rectangles are the {a_i} and a basis might be {a-c-e, b-c,c-d, d,e}. you can verify condition 2. Next in 2. replace let b'_i = b_i/d where d is a common denominator of the coefficients. Now all widths and heights are non-negative INTEGRAL combinations of the b'_i. OK, for each rectangle R, sides a and b are integer combinations of the b'_i so R can be tiled as a cartisian product with tiles of form b'_i(x)b'_j but these form a basis for the tensor product, so if two families of rectangles have the same tensor area then the expression for this tensor area in terms if the basic ij tiles is the same, and hence for all i and j the two tilings have the same number of ij tiles for each ij. done

1 0

[math-fun] tiling rectangles with rectangles.
by David Gale 26 Oct '04

26 Oct '04

I would like to know whether the following stuff is known. Well known: There does not exist a set of rectangles which will tile both a 1 by 2 rectangle and a square of side sqrt(2) (although they both have the same area). We say these sets are not EQUI-TILABLE. GENERAL PROBLEM: Let S be a union of a finite set of rectangles and let S' be another such set. Under what conditions are S and S' equi-tilable. ANSWER: Think of reals as a vector space over Q. For a rectangle of width a and height b we can form their TENSOR PRODUCT a(x)b. The TENSOR AREA of the set S is summation(a_i(x)b_i) summed over the rectangles of S. THEOREM. The sets S and S' are equi-tilable if and only if they have the same tensor area. The necessity of the condition is easy and probably known. It's the sufficiency which is interesting. EXAMPLE; a,b,c,d,e are rationally independent positive numbers S consists of two rectangles with (width, height) (a,b-c) and (a-c,d) S' is three rectangles (e,b),(a-e,b-c),(a-e-d,c) . One verifies the tensor areas are equal. Our proof of sufficiency is constructive showing how to find the tiles that do the job. (I have some pretty pictures if anyone is interested) [ Actually it matters whether we or not we use SYMMETRIC tensor product where we have a(x)b=b(x)a. This corresponds to allowing interchanging height and width in the tiling. (or of rotating tiles through 90 degrees). Refernces?? David G

4 5

RE: [math-fun] tiling rectangles with rectangles.
by Daniel Asimov 26 Oct '04

26 Oct '04

David: << The book "Hilbert's Third Problem" by Vladimir Boltyanskii 1978 is the definitive reference. >> Me: << I have that book and it's very nice, written at a level most upper division math undergrads could understand, though I don't think he tries to prove Sydler's sufficiency proof. >> David: << Dan, are you perhaps thinking of a different Boltyanskii book "Equivalent and Equidecomposable Figures"? This is the book which I used for my website exhibit. (I still have hopes someone will look at it). http://mathsite.math.berkeley.edu/polygon/polygonGalleryIntro.html The book "Hilbert's Third Problem" is non-elementary and it's devoted mostly to proving Sydler's converse. >> Oops, that must be the book I have (in the sense that it's in storage with most of my other math books somewhere in Chico, Calif.). --Dan

1 0

RE: [math-fun] tiling rectangles with rectangles.
by David Gale 25 Oct '04

25 Oct '04

Rich, maybe I didn't make it clear. The requirement is that the sets be equi-tilable BY RECTANGLES. The example of the 1 by 2 rectangle and the square with side sqrt(2) shows that equal area is not sufficient for equi-tilability. (if you don't restrict to rectangular tiles but allow say triangles then equal area is necessary and sufficient in R2, -but in even dimensions? I never heard of that) Dan, are you perhaps thinking of a different Boltyansii book "Equivalent and Equidecomposable Figures"? This is the book which I used for my website exhibit. (I still have hopes someone will look at it). http://mathsite.math.berkeley.edu/polygon/polygonGalleryIntro.html The book "Hilbert's Third Problem" is non-elementary and it's devoted mostly to proving Sydler's converse. David At 03:34 PM 10/25/2004 -0600, you wrote: >My memory from a long-ago popular article is that in even dimensions, >all that's required is equal measure (area, hypervolume, ...) for >hyper-polyhedra to be interdissectable. It works for D=2. > >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 Daniel Asimov >Sent: Monday, October 25, 2004 1:52 PM >To: math-fun >Subject: Re: [math-fun] tiling rectangles with rectangles. > > >David Gale wrote: > ><< >Dehn only proved the necessity. The sufficiency was proved (?) >seventy years later by a Danish mathematician named Sydler and a clear >proof was given by Borge Jessen shortly afterwards. The proof is difficult >and uses homological algebra (!). The book "Hilbert's Third Problem" by >Vladimir Boltyanskii 1978 is the definitive reference. >... > >> > >I have that book and it's very nice, written at a level most upper >division math >undergrads could understand, though I don't think he tries to prove Sydler's >sufficiency proof. > >QUESTION: I've never heard of any generalization of Dehn-Sydler to >higher dimensions than 3. Does anyone out there know of progress >in higher dimensions? > >--Dan Asimov > >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

RE: [math-fun] tiling rectangles with rectangles.
by Schroeppel, Richard 25 Oct '04

25 Oct '04

My memory from a long-ago popular article is that in even dimensions, all that's required is equal measure (area, hypervolume, ...) for hyper-polyhedra to be interdissectable. It works for D=2. 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 Daniel Asimov Sent: Monday, October 25, 2004 1:52 PM To: math-fun Subject: Re: [math-fun] tiling rectangles with rectangles. David Gale wrote: << Dehn only proved the necessity. The sufficiency was proved (?) seventy years later by a Danish mathematician named Sydler and a clear proof was given by Borge Jessen shortly afterwards. The proof is difficult and uses homological algebra (!). The book "Hilbert's Third Problem" by Vladimir Boltyanskii 1978 is the definitive reference. ... >> I have that book and it's very nice, written at a level most upper division math undergrads could understand, though I don't think he tries to prove Sydler's sufficiency proof. QUESTION: I've never heard of any generalization of Dehn-Sydler to higher dimensions than 3. Does anyone out there know of progress in higher dimensions? --Dan Asimov _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] Gravity Simulators (centrifuges)
by Henry Baker 25 Oct '04

25 Oct '04

I'm sure that NASA must have looked into all variations of this problem, but I haven't been able to find anything. Suppose that I wanted to build a centrifuge that incorporated a very active load (heavy mass that moves around a lot at the end of the centrifuge arm. The problem is that I would also have to keep some sort of counterweight also moving around in order to keep the arm statically and dynamically balanced, in order to not put huge loads on the axle & bearings. The most obvious solution (to me) would be to incorporate some sort of microprocessor and motor system to actively move the counterweight(s) to reduce the vibration and loads on the axles and bearings. But I was also wondering if there were a completely passive solution. I thought of putting the dynamic load inside of a rigid sealed box, and then suspending the box in a fluid having the same (average) density as the box. Presumably, the box wouldn't be able to move very far in any direction within the fluid. Can anyone think of any other "passive" type solutions? Can anyone point me to any literature references? Thanks.

2 1

Re: [math-fun] tiling rectangles with rectangles.
by Daniel Asimov 25 Oct '04

25 Oct '04

David Gale wrote: << Dehn only proved the necessity. The sufficiency was proved (?) seventy years later by a Danish mathematician named Sydler and a clear proof was given by Borge Jessen shortly afterwards. The proof is difficult and uses homological algebra (!). The book "Hilbert's Third Problem" by Vladimir Boltyanskii 1978 is the definitive reference. ... >> I have that book and it's very nice, written at a level most upper division math undergrads could understand, though I don't think he tries to prove Sydler's sufficiency proof. QUESTION: I've never heard of any generalization of Dehn-Sydler to higher dimensions than 3. Does anyone out there know of progress in higher dimensions? --Dan Asimov

1 0

[math-fun] Re: Avoiding Colinear Points
by T. D. Noe 24 Oct '04

24 Oct '04

The latest results from Flammenkamp appear at http://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html Someone should add this link to A000769. Correction: According to a table there, at least one solution is known for all n <= 46 and n=48,50,52. Tony

5 4

[math-fun] Re: Avoiding Colinear Points
by Richard Guy 22 Oct '04

22 Oct '04

I got the no-three-in-line problem from Heilbronn over 50 years ago. See F4 in UPINT. In Canad. Math. Bull. 11 (1968) 527--531; MR 39 #129 Guy & Kelly conjecture that, for large n, at most (c + eps)n points can be selected, where 3c^3 = 2pi^2 i.e. c ~ 1.85. Curiously, as recently as last March, Gabor Ellmann pointed out an error in our heuristic reasoning, which, when corrected, gives 3c^2 = pi^2, or c ~ 1.813799. I should send a correction to Canad Math Bull! R. PS. For those with a lot of computer time to spare, there's a lot to be discovered. Apart from a limping odd-even phenomenon, the number of solutions with 2n points appears to grow exponentially at first. Who will be the first to show that this begins to tail off? A000769 in OEIS has 3 more terms than I give in UPINT (perhaps due to Flammenkamp?). Also, OEIS says `Extension: It is known that a(n)=0 for all sufficiently large n.' By whom ??? R. On Thu, 21 Oct 2004, David Wasserman wrote: > Good point. Also, a single n-queens solution can already have 3 or more collinear points. > > -*-------- > ---*------ > -----*---- > -------*-- > ---------* > *--------- > --*------- > ----*----- > ------*--- > --------*- > >> There is no solution to the n-queens problem for n=2 or n=3. >> Besides, superimposing two n-queens solutions does not always yield 2n points. >> For example, here are two 8-queens solutions and their superposition, which only has 13 distinct points. >> >> --*----- >> -----*-- >> -*------ >> ------*- >> *------- >> ---*---- >> -------* >> ----*--- >> >> >> --*----- >> -----*-- >> -------* >> -*------ >> ---*---- >> *------- >> ------*- >> ----*--- >> >> Superimposed (13 points): >> >> --*----- >> -----*-- >> -*-----* >> -*----*- >> *--*---- >> *--*---- >> ------** >> ----*--- >> >> ----- Original Message ----- From: "Jud McCranie" <j.mccranie(a)adelphia.net> >> To: "Leroy Quet" <qq-quet(a)mindspring.com> >> Cc: "Leroy Quet" <qq-quet(a)mindspring.com>; <seqfan(a)ext.jussieu.fr> >> Sent: Thursday, October 21, 2004 3:54 PM >> Subject: Re: Avoiding Colinear Points >> >> >>> At 04:44 PM 10/21/2004, Leroy Quet wrote: >>> >>>> I describe a sequence and game based on the following idea. >>>> >>>> If we have a rectangular grid of n lattice-points by n lattice-points, >>>> how many dots can we place at the lattice-points, at most one dot per >>>> lattice-point, so that no 3 or more dots are colinear (in any direction)? >>>> >>>> I get the sequence: >>>> 1, 4, 6, 8, 10,.. >>>> And Richard Mathar has extended it: >>>> 12, 14, (15 or 16),... >>>> >>>> The upper bound on each term is obviously 2n, since we can have at most 2 >>>> dots in each row and column. >>> >>> There is an easy approach to this for nxn. If you superimpose any two different n-queens solutions, you get a solution with no three colinear points. Therefore 2n is always possible (for n > 1). >

2 1