Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Earlier today, somebody asked what looks like a homework problem, but admits the following reading which I think is interesting:

Suppose $a_1,\dots, a_n$ are positive integers, and $\varepsilon$ is a positive real number which you can take to be as small as you like. How many non-overlapping unit hypercubes can you fit into an $n$-dimensional rectangular solid with side lengths $a_i-\varepsilon$?

It's clear that you can't fit $\prod_i a_i$ and that you can fit at least $\prod_i (a_i-1)$. A little playing around shows that you can sometimes fit strictly more than $\prod_i (a_i-1)$. For example, here's a packing of three unit squares into a $(2-\varepsilon)\times(3-\varepsilon)$ rectangle:
squares
If I haven't made a mistake, you can take $\varepsilon$ to be as large as $1-\frac 23 \sqrt 2$.

  • Does anybody know how to find good lower bounds on this number? Using the trick in the above picture, you can effectively get a layer of hypercubes whose length in a given direction is $\sqrt 2 -\frac 12$ instead of 1. Is there a higher-dimensional version of this trick which does better?
  • Does anybody know how to get good upper bounds on this number? In particular, is there an easy way to see that it's never possible to get $\prod_i a_i -1$?
share|improve this question
    
Just to be pedantic: of course, by "non overlapping" you mean that two (hyper)cubes can intersect at most in a subset of their boundary, right? –  Qfwfq Mar 27 '10 at 6:37
3  
@unknown: Yes, that's what I meant, but it doesn't actually matter. If you come up with a packing where there are intersections on the boundary, then after possibly decreasing your ε, you can modify the packing so that there are no intersections at all. –  Anton Geraschenko Mar 27 '10 at 18:45
add comment

2 Answers

up vote 4 down vote accepted

There's a fair bit of literature about efficient packing of squares in squares. See, e.g., Kearney and Shiu, Efficient packing of unit squares in a square, available at http://www.emis.de/journals/EJC/Volume_9/PDF/v9i1r14.pdf, also Walter Stromquist, Packing 10 or 11 unit squares in a square, available at http://www.combinatorics.org/Volume_10/PDF/v10i1r8.pdf

share|improve this answer
2  
One source with plenty of pictures is Erich Friedman's website, which includes the following survey: www2.stetson.edu/~efriedma/papers/squares/squares.html –  j.c. Mar 27 '10 at 10:36
    
All these references are excellent! In particular, Nagamochi's Packing Unit Squares in a Rectangle (available at combinatorics.org/Volume_12/PDF/v12i1r37.pdf) proves that an $(a_1-\varepsilon)\times(a_2-\varepsilon)$ rectangle can hold at most $a_1a_2-2$ unit squares. The results in the references suggest that this is as good an answer as I'm likely to get, so I'm going to accept it. –  Anton Geraschenko Mar 27 '10 at 21:17
add comment

There is a surprising asymptotic result in 2 dimensions, closely related to your question. See [MR0370368] Erdős, P.; Graham, R. L. On packing squares with equal squares. J. Combinatorial Theory Ser. A 19 (1975), 119–123.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.