1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Packing Problem

  1. Jul 2, 2009 #1

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


  2. jcsd
  3. Jul 2, 2009 #2
    aaardvark - I don't know your background, so I'm not sure if the answer is more complicated than [tex]1000^2[/tex]?
  4. Jul 2, 2009 #3
    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.

  5. Jul 2, 2009 #4


    User Avatar
    Science Advisor

    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.
  6. Jul 2, 2009 #5
    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 [Broken]

    Last edited by a moderator: May 4, 2017
  7. Jul 2, 2009 #6
    Here's a link to a paper by Erdos and Graham (On Packing Squares with Equal Squares):


    (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
  8. Jul 2, 2009 #7
    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:

  9. Jul 2, 2009 #8
    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 [tex]\alpha[/tex]. If [tex]\alpha[/tex] is an integer, then the maximum area of the packed unit squares is obviously [tex]\alpha^2[/tex].

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

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

    W([tex]\alpha[/tex]) [tex]\leq[/tex] c[tex]\alpha^\frac{7}{11}[/tex]

    Intuitively, that means that W([tex]\alpha[/tex]) has the same "order" as [tex]\alpha^\frac{7}{11}[/tex]. As the author points out, for large [tex]\alpha[/tex], [tex]\alpha^\frac{7}{11}[/tex] 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.


    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
  10. Jul 2, 2009 #9


    User Avatar
    Science Advisor
    Homework Helper

    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
  11. Jul 2, 2009 #10
    Nice link. What a fascinating problem!
    Last edited by a moderator: May 4, 2017
  12. Jul 3, 2009 #11
    Thanks Petek.
  13. Jul 4, 2009 #12


    User Avatar
    Science Advisor
    Homework Helper

    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?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Packing Problem Date
Similar to bin packing Jan 16, 2016
Point packing problem Apr 25, 2014
2d bin packing + selective grouping Dec 4, 2012
Uniform rectangle packing May 23, 2009
Sphere packing problem Jun 5, 2008