Packing Problem

[aaardvark]

Hi,

does any one know how many squares of side 1 millimeter can fit in a big square of side 1000.25 millimeters ?

Cheers,

Aaardvark.

[daviddoria]

aaardvark - I don't know your background, so I'm not sure if the answer is more complicated than 1000^2?

[aaardvark]

Apparently when the the big square is a large number of times plus a quarter bigger than the small square then the answer is not just that large numer squared. But I can't find out much more than this, ie how big does the large numer have to be etc.

Aaardvark.

[HallsofIvy]

Draw a line, perpendicular to a side, exactly 1000mm from one end a side, leaving 0.25 mm. Draw a second line, perpendicular to that line, exactly 1000 mm from one end of a side, leaving 0.25 mm. Those two lines, together with the opposite sides of the square form a square exactly 1000 mm on a side and so will fit exactly 10002= 1000000 small squares. The two portions outside the new drawn lines have width only .25 mm and so NO such squares will fit with them.

[aaardvark]

Page 8 touches on the subject but I can't find much else :frown:

http://www.math.ucsd.edu/~sbutler/ron/78_07_scheduling.pdf

Aaardvark.

[Petek]

Here's a link to a paper by Erdos and Graham (On Packing Squares with Equal Squares):

www.math.ucsd.edu/~sbutler/ron/75_06_squares.pdf

(At second glance, it comes from the same source as the pdf file in your last post, so perhaps you already know of it.)

[aaardvark]

No, I hadn't found that one. Looks useful :smile:

But in case my little brain isn't up to the job maybe some of you geniuses (genii ?)
could have a go and give me an executive summary :tongue2:

Aaardvark.

[Petek]

I think I can explain the statement of the theorem, but not the proof.

The problem is to maximize the sum of the areas of unit squares when packed into a square of side \alpha. If \alpha is an integer, then the maximum area of the packed unit squares is obviously \alpha^2.

For each positive real number \alpha, the author defines a function W(\alpha). W represents the difference between the optimal packed area \alpha^2 and the supremum (least upper bound) of the areas of all possible packings. (I think of W as representing the "waste".) The theorem states

W(\alpha) = O(\alpha^\frac{7}{11})

The so-called "big Oh" notation means that there exists a constant c such that

W(\alpha) \leq c\alpha^\frac{7}{11}

Intuitively, that means that W(\alpha) has the same "order" as \alpha^\frac{7}{11}. As the author points out, for large \alpha, \alpha^\frac{7}{11} is much smaller than the area of the packing obtained by placing the unit squares in rows and columns that are parallel to the sides of the big square.

The proof doesn't seem to use any advanced math, but I haven't tried to read it.

HTH

EDIT: Can anyone explain why my alphas aren't lining up correctly? I'm just learning Tex, so I assume I'm doing something wrong, but can't figure out what.

[CRGreathouse]

Here's a much more up-to-date survey:
http://www.combinatorics.org/Surveys/ds7.html

The problem, in general, is quite hard.

[Petek]

Here's a much more up-to-date survey:
http://www.combinatorics.org/Surveys/ds7.html

The problem, in general, is quite hard.

Nice link. What a fascinating problem!

[aaardvark]

I think I can explain the statement of the theorem, but not the proof.

The problem is to maximize the sum of the areas of unit squares when packed into a square of side \alpha. If \alpha is an integer, then the maximum area of the packed unit squares is obviously \alpha^2.

For each positive real number \alpha, the author defines a function W(\alpha). W represents the difference between the optimal packed area \alpha^2 and the supremum (least upper bound) of the areas of all possible packings. (I think of W as representing the "waste".) The theorem states

W(\alpha) = O(\alpha^\frac{7}{11})

The so-called "big Oh" notation means that there exists a constant c such that

W(\alpha) \leq c\alpha^\frac{7}{11}

Intuitively, that means that W(\alpha) has the same "order" as \alpha^\frac{7}{11}. As the author points out, for large \alpha, \alpha^\frac{7}{11} is much smaller than the area of the packing obtained by placing the unit squares in rows and columns that are parallel to the sides of the big square.

The proof doesn't seem to use any advanced math, but I haven't tried to read it.

HTH

EDIT: Can anyone explain why my alphas aren't lining up correctly? I'm just learning Tex, so I assume I'm doing something wrong, but can't figure out what.

Thanks Petek.

[CRGreathouse]

It looks like the Erdos-Graham method or a simpler variant would apply here, but I can't quite get through the details beyond the first trapezoids -- geometry's not my thing. Anyone want to take a stab at it?