Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
I think it should be $p(n) \sim 2\sqrt{\pi n}$ as $n\to\infty$ –  nikita2 Oct 15 '12 at 13:30
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. –  joriki Oct 15 '12 at 15:03

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
that was my guess as well, but does one prove it formally? –  Ale Zok Oct 15 '12 at 16:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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