20
$\begingroup$

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 (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$?
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Qfwfq
    Mar 27, 2010 at 6:37
  • 3
    $\begingroup$ @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. $\endgroup$ Mar 27, 2010 at 18:45

3 Answers 3

7
$\begingroup$

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

$\endgroup$
3
8
$\begingroup$

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.

$\endgroup$
1
4
$\begingroup$

https://erich-friedman.github.io/mathmagic/0610.html has some answers for small numbers of squares.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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