# How many unit squares can you pack into a rectangle with nearly integer side lengths?

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:

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$?
-
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
@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

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

-
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

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.

-

http://www2.stetson.edu/~efriedma/mathmagic/0610.html has some answers for small numbers of squares.

-