# 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: (source)

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? Mar 27, 2010 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. Mar 27, 2010 at 18:45

• 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. Mar 27, 2010 at 21:17