I cannot find the general formula for least perimeter when a specific number of squares are given

Question

A figure is formed by placing $N$ unit squares squares on the plane. Squares may share a common edge, but they may not otherwise overlap. What is the minimum perimeter of the figure?

Through drawing all the possible cases, I got that

a. For a square number $N^2$, the least perimeter is $4\cdot N$.

b. For $N^2-1$, the least perimeter isn't greater than $4\cdot N$.

But this does not satisfy for example $8$ number of tiles. So it seems to work as long as we keep the shape convex.

At last I can only say that for $K$ tiles, where $K$ is less than or equal to $N^2$, the least perimeter isn't greater than $4\cdot N$.

It can be of any shape, all matters is that the perimeter should be minimum. The individual pieces are squares

Answer 1

I have tried examples and derived at this function:

If k is a perfect square,

$ P_{k+1} = P_{k+2} = .... = P_{k+ \sqrt k} = P_k + 2$

$P_{k+ \sqrt k + 1} = P_k + 4$

For all other values of k, $ P_k = 4*\lceil {\sqrt k} \rceil$

Though i am not sure, but for small examples my formula seems to be correct.

Answer 2

Examples lead me to believe that the answer is $$ P_k= \begin{cases} 4n,&n(n-1)< k\le n^2,\\ 4n+2,&n^2<k\le n(n+1) \end{cases} $$ but I have nothing like a proof.

Answer 3

The basic idea is to solve a simpler problem " Given a perimeter value $p$, how large a shape can you make with perimeter $p$?" Using the solution to that problem, try to estimate $P_N$.

The answer is $$P_N = 2\lceil2\sqrt{N}\rceil $$ The problem is the content of a paper :

F. Harary and H. Harborth. Extremal animals. J. Combin. Inform. System Sci., 1:1–8, 1976. ( unfortunately I can't seem to find a soft copy of the same )

You can read the solution of a related problem in this paper

I'm giving a brief outline of the proof:

Denote the area and perimeter of a polymino $P$ by $Ar(P)$ and $Pr(P)$ respectively. Define $\sigma(p) = \max\{ Ar(A): Pr(A) = p\}$ to be the maximum area obtainable by a polymino of perimeter $p$. We want to find $\pi(n) = \min\{Pr(A): Ar(A) = n\}$, the minimum perimeter of a $n$-polymino. We can compute $\sigma(p)$ to be $$ \sigma(4k) = 4k^2, $$ $$ \sigma(4k+2) = 4k^2 - 4k $$ Now, we can show that: $$ \pi(n) = \min \{ p : \sigma(p) \ge n\} $$ Considering two mutually disjoint cases $p = 4k$ and $p = 4k+2$, Its straightforward to get $\pi(k) = 2\lceil2\sqrt{k}\rceil$