Packing unit squares in a rectangle

Hiroshi Nagamochi

The electronic journal of combinatorics, Tome 12 (2005)

Résumé

For a positive integer $N$, let $s(N)$ be the side length of the minimum square into which $N$ unit squares can be packed. This paper shows that, for given real numbers $a,b\geq 2$, no more than $ab -(a+1-\lceil a\rceil) -(b+1-\lceil b\rceil)$ unit squares can be packed in any $a'\times b'$ rectangle $R$ with $a' < a$ and $b' < b$. From this, we can deduce that, for any integer $N\geq 4$, $s(N)\geq \min\{\lceil \sqrt{N} \rceil, \sqrt{N -2 \lfloor \sqrt{N}\rfloor +1 }+1\}$. In particular, for any integer $n\geq 2$, $s(n^2)=s(n^2-1)=s(n^2-2)=n$ holds.

Détail

DOI : 10.37236/1934

Classification : 52C15
Mots-clés : rectangle, square, square packing