Packing Problem

1. Jul 2, 2009

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.

2. Jul 2, 2009

daviddoria

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

3. Jul 2, 2009

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.

4. Jul 2, 2009

HallsofIvy

Staff Emeritus
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.

5. Jul 2, 2009

aaardvark

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

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

Aaardvark.

Last edited by a moderator: May 4, 2017
6. Jul 2, 2009

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[/URL]

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

Last edited by a moderator: Apr 24, 2017
7. Jul 2, 2009

aaardvark

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 :tongue2:

Aaardvark.

8. Jul 2, 2009

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.

Last edited: Jul 2, 2009
9. Jul 2, 2009

CRGreathouse

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

The problem, in general, is quite hard.

Last edited by a moderator: May 4, 2017
10. Jul 2, 2009

Petek

Nice link. What a fascinating problem!

Last edited by a moderator: May 4, 2017
11. Jul 3, 2009

aaardvark

Thanks Petek.

12. Jul 4, 2009

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?