9
$\begingroup$

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

polygon

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.

$\endgroup$
3
  • 2
    $\begingroup$ Try the Wayback machine for the link to AE2011 $\endgroup$ May 8, 2020 at 9:16
  • $\begingroup$ @JeffZeitlin Thank you, the only result is from 2018 but it shows the task correctly. I'll update the question $\endgroup$
    – melfnt
    May 8, 2020 at 9:20
  • $\begingroup$ guys thank you for all the answers: I really don't know which one to accept $\endgroup$
    – melfnt
    May 9, 2020 at 13:24

5 Answers 5

11
$\begingroup$

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? :)

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ Just for the trivial case, $n=3$ is also impossible. Else it's perfect. You beat me to it! $\endgroup$ May 8, 2020 at 9:19
  • 2
    $\begingroup$ I'm not really interested in worms because they take a lot of space :) $\endgroup$
    – melfnt
    May 8, 2020 at 9:24
  • 2
    $\begingroup$ aww, look, they can bend their tails! :3 i.imgur.com/TjajyZ9.png $\endgroup$
    – athin
    May 8, 2020 at 9:29
  • $\begingroup$ are you sure this is the optimal way to use the space? $\endgroup$
    – melfnt
    May 8, 2020 at 9:53
  • $\begingroup$ The even more trivial case for n=0 could be considered possible. $\endgroup$ Jun 25, 2020 at 17:30
6
$\begingroup$

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

Image

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$:

enter image description here
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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you, this is awesome! Two questions: you show that in some cases it is not possible to stat from a rectangle with area A = n+floor( (n-2)/4 ) but how can you be sure that it is always possible to start from a rectangle with area A+1? Maybe a larger rectangle is needed (area A+2 or A+3...). Second question: with this solution the higher density achievable is n/A = 4/5 for large n (if I made the calculation well). However other answers suggest that the higher density achievable is 2/3. Why does this gap exist? $\endgroup$
    – melfnt
    May 8, 2020 at 14:38
  • $\begingroup$ If the A is even then you can make a 2 by A/2 rectangle and you can prove that A/2 is large enough for the construction to always work. If A is such that the construction fails, then A must be odd, and the construction will then work for the even area A+1. The exact formulation of when you need that increase is a bit tricky, so I've handwaved it a bit. I don't think the other answers prove that 2/3 is the highest density possible for every construction method, only that it is the limit for their particular method. $\endgroup$ May 8, 2020 at 14:54
2
$\begingroup$

Here are solutions for 6, 8 and 12:

enter image description here

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.

$\endgroup$
3
  • $\begingroup$ This is correct, what about the general case? $\endgroup$
    – melfnt
    May 8, 2020 at 9:23
  • 1
    $\begingroup$ I saw @athin already answered that. As for the bonus question: I don't understand it right now: given $n$, do you want a formula for the smallest possible enclosing rectangle? Or do you have a rectangle size in mind and want to know the maximum $n$ that fits? $\endgroup$
    – Glorfindel
    May 8, 2020 at 9:26
  • $\begingroup$ The first thing you said $\endgroup$
    – melfnt
    May 8, 2020 at 9:52
1
$\begingroup$

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:

solutions for n=6, 8, 12 by @Glorfindel

 

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? :) answer for generic n by @Athin

 

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:

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

Thank you for your replies!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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