Packing Problem

**aaardvark** · Jul2-09, 07:20 AM

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** · Jul2-09, 08:46 AM

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

?

**aaardvark** · Jul2-09, 09:05 AM

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** · Jul2-09, 09:31 AM

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 1000²= 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** · Jul2-09, 09:49 AM

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

http://www.math.ucsd.edu/~sbutler/ro...scheduling.pdf

Aaardvark.

**Petek** · Jul2-09, 10:45 AM

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** · Jul2-09, 11:26 AM

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

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

Aaardvark.

**Petek** · Jul2-09, 03:41 PM

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 $LaTeX Code: \\alpha$ . If $LaTeX Code: \\alpha$ is an integer, then the maximum area of the packed unit squares is obviously $LaTeX Code: \\alpha^2$ .

For each positive real number $LaTeX Code: \\alpha$ , the author defines a function W( $LaTeX Code: \\alpha$ ). W represents the difference between the optimal packed area $LaTeX Code: \\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( $LaTeX Code: \\alpha$ ) = O( $LaTeX Code: \\alpha^\\frac{7}{11}$ )

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

W( $LaTeX Code: \\alpha$ ) $LaTeX Code: \\leq$ c $LaTeX Code: \\alpha^\\frac{7}{11}$

Intuitively, that means that W( $LaTeX Code: \\alpha$ ) has the same "order" as $LaTeX Code: \\alpha^\\frac{7}{11}$ . As the author points out, for large $LaTeX Code: \\alpha$ , $LaTeX Code: \\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** · Jul2-09, 07:01 PM

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

The problem, in general, is quite hard.

**Petek** · Jul2-09, 09:38 PM

Originally Posted by CRGreathouse

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** · Jul3-09, 04:09 AM

Originally Posted by 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 $LaTeX Code: \\alpha$ . If $LaTeX Code: \\alpha$ is an integer, then the maximum area of the packed unit squares is obviously $LaTeX Code: \\alpha^2$ .

For each positive real number $LaTeX Code: \\alpha$ , the author defines a function W( $LaTeX Code: \\alpha$ ). W represents the difference between the optimal packed area $LaTeX Code: \\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( $LaTeX Code: \\alpha$ ) = O( $LaTeX Code: \\alpha^\\frac{7}{11}$ )

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

W( $LaTeX Code: \\alpha$ ) $LaTeX Code: \\leq$ c $LaTeX Code: \\alpha^\\frac{7}{11}$

Intuitively, that means that W( $LaTeX Code: \\alpha$ ) has the same "order" as $LaTeX Code: \\alpha^\\frac{7}{11}$ . As the author points out, for large $LaTeX Code: \\alpha$ , $LaTeX Code: \\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** · Jul4-09, 01:32 AM

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?