Baltic Way 2023 Shortlist

Answer: $n=32$. We start by showing that such a $32$-gon exists. It remains to prove that this is indeed the smallest possible $n$. We will do that by proving that for all $n<32$ the area $S$ of an $n$-gon with perimeter $P=n$ is smaller than $n$.

At first we note that $P=n$ if and only if all sides of the $n$-gon are of length $1$. From this it follows that $n$ should be an even number as there should be an even number of horizontal and an even number of vertical sides. Denote $n=2m$ and the vertices of the $n$-gon as $A_1{A}_2\dots A_{2m}$. We call a vertex $A_i$ odd (even) if its index $i$ is odd (even).

Now we can consider the sides of the $n$-gon in pairs. Let vertex $A_i$ be located at the point $(x,y)$. Vertex $A_{i+2}$ is then located at $(x\pm 1,y\pm 1)$. It means that by moving from $A_i$ to $A_{i+2}$ (we count vertices modulo $2m$) we have moved by a unit vector in the “diagonal” coordinate system with unit vectors $(1,1)$ and $(1,-1)$. We denote these steps $\to$ and $\leftarrow$, respectively.

Let's start at the vertex $A_1$ and travel around the $n$-gon in $m$ steps by stopping at all odd vertices $A_1\to A_3\to \cdots \to A_{2m-1}\to A_1$. Denote the total number of $\to$ steps as $2a$ and the total number of $\leftarrow$ steps as $2b$ (both of them must be even numbers). Therefore $m=2a+2b$ and $n=4a+4b$, hence $n$ is divisible by $4$. It means that we have to prove that $S<n$ for all $P=n\le 28$.

Let's consider the most “northeastern”, “northwestern”, “southeastern” and “southwestern” vertices of our $n$-gon, denote them $NE,NW,SE,SW$ respectively (see figure). W.l.o.g. assume that $NE$ and at least one more of them are odd. Our $n$-gon is contained in a rectangle whose sides are parallel to vectors $(1,1)$ and $(1,-1)$ and pass through these four vertices. Denote its width and height as $W$ and $H$. Our $n$-gon's area is no larger than $W\cdot H-S_g$ where $S_g$ is the area of the “gray triangles”. It can be computed as half of the area of the “square ring” between outer and inner (gray) rectangles: $$S_g=\frac{WH-(W-\sqrt{2})(H-\sqrt{2})}{2}=\frac{\sqrt{2}(W+H)}{2}-1$$ therefore the area of the $n$-gon is no larger than $S\le WH-\frac{\sqrt{2}(W+H)}{2}+1$. By using the inequality $WH\le \frac{(W+H{)}^2}{4}$ we can transform it into $$S\le \frac{(W+H{)}^2}{4}-\frac{\sqrt{2}(W+H)}{2}+1=\frac{(W+H-\sqrt{2}{)}^2}{4}+\frac{1}{2}.(\ast )$$ Recall that the $NE$ vertex is odd. Assume at first that $SW$ also is odd. Then as travelling from $NE$ to $SW$ uses at most $b$ $\nearrow$ steps, then we conclude that $W\le b\sqrt{2}$. If the vertex $SW$ is even, then the estimation is slightly worse: we can travel in at most $b$ $\nearrow$ steps from $NE$ to one of the neighbours of $SW$ and $SW$ itself is further $\sqrt{2}/2$ away from it in $\nearrow$ direction, so that $W\le b\sqrt{2}+\sqrt{2}/2$.

If $SW$ is even then at least one of vertices $NW$ and $SE$ is odd. In that case for $H$ we get similar estimation $H\le a\sqrt{2}+\sqrt{2}/2$. But if $SW$ is odd then it could happen that both $NW$ and $SE$ are even, in which case we have to do the $\sqrt{2}/2$ correction in both ends what gives us the estimation $H\le a\sqrt{2}+\sqrt{2}$. To summarize, we have two possible cases: $$\{\begin{array}{l}W\le b\sqrt{2}\\ H\le a\sqrt{2}+\sqrt{2}\end{array}\text{or}\{\begin{array}{l}W\le b\sqrt{2}+\frac{\sqrt{2}}{2}\\ H\le a\sqrt{2}+\frac{\sqrt{2}}{2}\end{array}$$ We see that in both cases $W+H\le a\sqrt{2}+b\sqrt{2}+\sqrt{2}$. Now we can plug that into $(\ast )$ to obtain that $$S\le \frac{(a+b{)}^2}{2}+\frac{1}{2}.$$ Recall that the perimeter of our $n$-gon is $4a+4b$. It remains to prove that if $4a+4b\le 28$ then $S<P$ that is $\frac{(a+b{)}^2}{2}+\frac{1}{2}<4a+4b$ if $a+b\le 7$. But this inequality can be rewritten as $(a+b)(a+b-8)<-1$ which is obviously true if $a+b\le 7$.

---

Alternative solution.

The parity arguments in the given solution can be combined: A grid-$n$-gon with perimeter $n$ alternates between horizontal and vertical unit segments, so the number of horizontal segments equals the number of vertical segments. As this common number must be even (#left steps = #right steps, #up steps = #down steps), we have that $n$ is divisible by $4$.

Given the construction for $n=32$, it remains to be shown that it can't be done for $n\le 28$. Viewing the polygon as a collection of unit squares and turning this into a graph by joining two squares that share an edge, this is a variant of the isoperimetric problem in the grid graph with an additional constraint coming from the prescribed number of polygon vertices. Without this constraint we have the following bound.

Lemma 1: For any polygon $P$ with axis-parallel sides, vertices in ${\mathbb{Z}}^2$, area $A$ and perimeter $u$, we have $u\ge 2(a+b)$ where $$a=\max \{x\mid (x,y)\in P\}-\min \{x\mid (x,y)\in P\},\text{ and}$$ $$b=\max \{y\mid (x,y)\in P\}-\min \{y\mid (x,y)\in P\}.$$ Proof. Without loss of generality we have $\min \{x\mid (x,y)\in P\}=\min \{y\mid (x,y)\in P\}=0$. The boundary contains at least $2a$ segments of the form $((x,y),(x+1,y))$ and at least $2b$ segments of the form $((x,y),(x,y+1))$. $\square$

This bound itself is not good enough to rule out all relevant values for $n$, but we can add the following. In the $n$-gon with area $n$ and perimeter $n$, consider the unit squares that are furthest north, east, west and south. Since horizontal and vertical segments on the boundary of the polygon alternate, these are four distinct squares, and they correspond to vertices of degree $1$ in the corresponding subgraph of the grid. Deleting these four squares, we obtain an $n^{\prime }$-gon with area $n-4$, perimeter $n-8$ and $n^{\prime }\ge n-16$. Now Lemma 1 rules out $n\in \{4,8,12,16,20,24\}$ immediately. For instance for $n=24$, we need area $20$ and perimeter $16$, but Lemma 1 provides a lower bound of $18$ for the perimeter. For $n=28$, the reduced polygon has area $24$ and perimeter $20$. This can be achieved, but only with a $6\times 4$-rectangle or a $5\times 5$-square with a corner unit square removed while we would need at least $12$ vertices.