Packing Unit Squares in a Rectangle

Hiroshi Nagamochi


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.

Full Text: