An $n$-sided polygon with area $n$

Question

Here is a $10$-sided polygon which area is $23$ (i.e. it contains exactly 23 unit squares).

Can you draw a polygon with:

• $6$ sides and area $6$?
• $8$ sides and area $8$?
• $12$ sides and area $12$?

What about a polygon with $13$ sides and area $13$?

The polygons cannot contain holes; all the sides must be drawn over the unit grid lines.

Can you find a constructive approach to draw any polygon with $n$ sides and area $n$?

Bonus question:

As you can easily see there are many solutions for each $n$. Among all polygons that fulfill the requirements for a fixed $n$, which one is the "smallest" one? i.e. which one can be inscribed in the rectangle with the lowest area?

Source: this puzzle is based on a task from Algorithmic Engagements 2011. The link points to the wayback machine website because recently someone bought the main.edu.pl internet domain and replaced the original website with an online casino.

Answer 1

Are all $n$ possible?

No. Trivially, $n \leq 2$ is impossible. For odd $n$, it's also impossible because the polygon must have an even number of sides (the sides alternately change from horizontal and vertical.) So we are only dealing with even $n \geq 4$.

Then is it possible to construct them?

Sure thing! Are you interested in worms btw? :)

Answer 2

A straightforward construction that maintains density 2/3+$\epsilon$, since the other parts already have satisfactory answers:

Specifically,

$n=4k$ has density $\frac{2k}{3k-1}$ and $n=4k+2$ has density $\frac{2k+1}{3k+1}$.

EDIT: Asymptotic density $\frac{4}{5}$ inspired by Jaap's answer, for any $n \geq 8$:

Densities: $\frac{4}{5}-\frac{2}{5k}$ for $n=4k-2$, $\frac{4}{5}$ for $n=4k$.

I believe this is close to optimal because

the number of edges you can add without constructing incredibly irregular (and lower-density) shapes increases with perimeter, and so keeping cells and edges equal restricts the ratio between area and perimeter, which constrains the dimensions of the rectangle accordingly.

Answer 3

Here is a solution method that I think will give the minimal bounding rectangle.

Suppose we want to create a polyomino with $n$ sides and area $n$.

Suppose you start with a filled rectangle, with an area that is yet to be determined. It has 4 sides. We then take away as few cells as possible until the number of sides has reached the value we want.
If you remove a corner cell, the number of sides is increased by $2$.
If you remove any other boundary cell, the number of sides is increased by $4$.
It is impossible to create more than $4$ extra sides by the removal of one cell.
Therefore, if $n$ is a multiple of $4$, the best we could do is to remove $\frac{n-4}{4}$ non-adjacent boundary cells, and if $n$ is even and not a multiple of $4$ the best we could do is remove one corner cell and $\frac{n-6}{4}$ non-adjacent boundary cells.
We want the remaining area to be $n$, so the ideal optimal solution would be to start with a rectangle of area $n+\frac{n-4}{4}$ (if $4|n$) or $n+\frac{n-6}{4}+1$ (otherwise). These two expressions can be combined as $n+\lfloor \frac{n-2}{4}\rfloor$.

For example:

Sometimes this is possible. For example n=8 needs area 8+1=9, and n=42 needs an area of 42+10=52:

 XXX
 XXX
 X X
 
 X.X.X.X.X.X.X
 XXXXXXXXXXXXX
 XXXXXXXXXXXXX
 X.X.X.XXXXXX.

This does not always work, unfortunately.

The ideal optimal area sometimes does not make a rectangle from which you can take the required number of cells. In particular, the area could be a prime number, and a rectangle of width $1$ can't have boundary cells removed from it. This happens for example with $n=6$. The ideal would be a rectangle of area 7 with one corner cell removed, but that is impossible. In this case you have to use a rectangle of area $8$, and remove a 2-cell corner.
By enlarging the prime area by $1$ you get an even area, and that will always allow you to make a rectangle from which you can remove the required number of boundary cells.

There are also some non-prime cases that fail, for example $n=136$ has an ideal rectangle area of $169=13\times13$, but there is not enough room to remove 33 non-adjacent boundary cells. Again, by increasing it by 1 you can make a $2\times85$ rectangle from which you can easily take out 34 cells (32 single cells and one adjacent pair). I think that if the ideal area is the product of two primes $pq$ and they satisfy $(p-5)(q-5)>9$, then the construction fails.

So the optimal rectangle area is $n+\lfloor \frac{n-2}{4}\rfloor$, except if that number is prime or the product or two large primes, then you need an area of $n+\lfloor \frac{n-2}{4}\rfloor+1$.

This is not entirely rigorous, as I have not proved that the exact conditions in which the slightly larger rectangle area is needed.

Answer 4

Here are solutions for 6, 8 and 12:

As for 13,

this is impossible since the only possible angles are +90 and -90 degrees, so following the edge you always end up at +90 or -90 after 13 corners.

Answer 5

^{There are a lot of high-quality answers here and each one of them replies to one or more specific part of the original question, but unfortunately no answer addresses all the question. Since I don't know which one to accept I decided to post this Community-wiki answer that summarizes all the (pre)existing ones.}

Can you draw a polygon with:

• 6 sides and area 6?
• 8 sides and area 8?
• 12 sides and area 12?

Example of solutions from @Glorfindel's answer:

 

What about a polygon with 13 sides and area 13?

From @Athin's answer (but also @Glorfindel's):

No [it is not possible to construct the requested polygons for each $n$]. Trivially, n≤2 is impossible. For odd n, it's also impossible because the polygon must have an even number of sides (the sides alternately change from horizontal and vertical.) So we are only dealing with even n≥4.

 

Can you find a constructive approach to draw any polygon with $n$ sides and area $n$?

Again from @Athin's answer:

Sure thing! Are you interested in worms btw? :)

 

Bonus question: As you can easily see there are many solutions for each $n$. Among all polygons that fulfill the requirements for a fixed $n$, which one is the "smallest" one? i.e. which one can be inscribed in the rectangle with the lowest area?

Proof for the smallest bounding rectangle from @Jaap Scherphuis's answer:

Suppose you start with a filled rectangle, with an area that is yet to be determined. It has 4 sides. We then take away as few cells as possible until the number of sides has reached the value we want.
If you remove a corner cell, the number of sides is increased by $2$.
If you remove any other boundary cell, the number of sides is increased by $4$.
It is impossible to create more than $4$ extra sides by the removal of one cell.
Therefore, if $n$ is a multiple of $4$, the best we could do is to remove $\frac{n-4}{4}$ non-adjacent boundary cells, and if $n$ is even and not a multiple of $4$ the best we could do is remove one corner cell and $\frac{n-6}{4}$ non-adjacent boundary cells.
We want the remaining area to be $n$, so the ideal optimal solution would be to start with a rectangle of area $n+\frac{n-4}{4}$ (if $4|n$) or $n+\frac{n-6}{4}+1$ (otherwise). These two expressions can be combined as $n+\lfloor \frac{n-2}{4}\rfloor$.

This does not always work, unfortunately.

The ideal optimal area sometimes does not make a rectangle from which you can take the required number of cells. In particular, the area could be a prime number, and a rectangle of width $1$ can't have boundary cells removed from it. This happens for example with $n=6$. The ideal would be a rectangle of area 7 with one corner cell removed, but that is impossible. In this case you have to use a rectangle of area $8$, and remove a 2-cell corner.
By enlarging the prime area by $1$ you get an even area, and that will always allow you to make a rectangle from which you can remove the required number of boundary cells.

There are also some non-prime cases that fail, for example $n=136$ has an ideal rectangle area of $169=13\times13$, but there is not enough room to remove 33 non-adjacent boundary cells. Again, by increasing it by 1 you can make a $2\times85$ rectangle from which you can easily take out 34 cells (32 single cells and one adjacent pair). I think that if the ideal area is the product of two primes $pq$ and they satisfy $(p-5)(q-5)>9$, then the construction fails.

So the optimal rectangle area is $n+\lfloor \frac{n-2}{4}\rfloor$, except if that number is prime or the product or two large primes, then you need an area of $n+\lfloor \frac{n-2}{4}\rfloor+1$.

A way to build polygons with asymptotically optimal density for any $n>8$, from @AxiomaticSystem's answer:

Densities: $\frac{4}{5}-\frac{2}{5k}$ for $n=4k-2$, $\frac{4}{5}$ for $n=4k$.

Thank you for your replies!