2
$\begingroup$

Suppose I have $n$ identical unit squares and I want to use them all to tile a region with minimal perimeter $p(n)$. For instance I guess $p(n^2)=4n$, by arranging them im a $n\times n$ square.

Is there an explicit formula for $p(n)$? Or sharp bounds? How do one prove equalities or bounds for this type of quantities?

I would be happy also with a recursive formula for $p(n)$, like $p(n\cdot m) = f(p(m),p(n))$, but the factorization is not unique and I don't see how to get it easily.

My intuition is that given a certain number $n$, the minimal perimeter region is a rectangle with sides of integer lengths $l$ and $m$, where $l\cdot m=n$ and $(l,m)$ is the pair of integer numbers "closest" (in some sense) to $(\sqrt{n},\sqrt{n})$, that's where number theory could play a role.

I have no clue where to start proving something along these lines, so any hint, comment or reference is welcome!

  • 1
    @nikita2: That would be the asymptotic form for the minimal length of the convex hull; but if you measure the perimeter exactly following the sides of the squares a circular arrangement is actually worse than a square.2012-10-15

1 Answers 1

5

For every x in the range $n^2 \le x < (n+1)^2$ you have $4n \le p(x) \le 4n+4$, so $p(x) = \sqrt{x} + \operatorname{O}(1)$. If you want a closed formula I would try with (putting $t=n^2-x$) $ p(n^2+t) = \begin{cases} 4n \quad&\text{if }t=0\\4n+2 &\text{if }0 < t \le n\\ 4n+4 &\text{if }n < t \le 2n\end{cases}$ which is the perimeter you obtain if you go from the square $n\times n$ to the square $(n+1)\times(n+1)$ tile by tile.

EDIT (Proof sketch) We can assume that the shape with least perimeter is connected (if the shape has two pieces, connecting them by a suitable edge gives a shape with strictly less perimeter than the original).

Now given $x = n^2+t$ with $0\le t \le 2n$ fix a shape that gives the least perimeter $p(x)$. Pick a rectangle with minimal dimensions $a\times b$ containing the shape. The perimeter is at least $2a+2b$, (as it goes all the way from left to right and from top to bottom and back by the other side).

On the other hand $ab \ge x$ because there are at least $x$ tiles inside the rectangle so $ p(x) \ge 2a + 2b \ge 2a + 2x/a $ the right hand side has a single minimum at $a = \sqrt{x}$ but $a$ is an integer so we have $ p(x) \ge 2n + 2x/n = \frac{ 4n^2 + 2t}{n} $ (it is easy to see that $a=n+1$ gives a larger value). If $t = 0$ this gives $p(x) \ge 4n$, if $t \le n$ we have $p(x) > 4n$ but as $p(x)$ is even we have $p(x) \ge 4n+2$ and if $t > n$ we have $p(x) > 4n+2$ so again $p(x) \ge 4n+4$. As we have examples obtaining this bounds we are finished.

  • 0
    that was my guess as well, but does one prove it formally?2012-10-15