Belarusian Mathematical Olympiad

It is clear that the set of boundary cells of the polygon $A$ can be divided into trapezoids so that you can go from any of them to another, going only through the sides of the trapezoids. We call a polygon satisfying this condition good. We will prove by induction on $k\ge 2$ the following statement: if the area of a good polygon is $S\le 4k+1$, then $S\equiv 1(\mathrm{mod}4)$.

The induction base is $k=2$. It is easy to see that there are at least $4$ trapezoids, and if there are exactly $4$ of them the polygon is a square $3\times 3$. If there are at least $5$ trapezoids, then the area $S\ge 2\cdot 5>2\cdot 4+1$.

The step of the induction. Suppose that the statement is true for $k=n-1\ge 2$. Let us prove it for $k=n$, i.e. for any good polygon with the area $S\in [4(n-1)+2;4n+1]$.

Consider any side $AB$ of a good polygon, both adjacent angles to which are equal to $90^{\circ }$. Such side always exists, for example the lowest horizontal side of a polygon. Let $AB=3$ and the polygon is not a square $3\times 3$. Then two trapezoids adjacent to $AB$ are restored uniquely and it is possible to cut off the rectangle $3\times 4$ from the polygon and get a good one again. It is clear that with such a cut, the remainder of dividing $S$ by $4$ will not change.



Now let's assume that the good polygon has no sides of length $3$ (If the side of the polygon is $3$, then clearly both of its adjacent angles are $90^{\circ }$). Then to the neighboring sides there are at least $2$ adjacent trapezoids (otherwise their length is $3$). Let $AB=l$. If the rectangle $CABD$ (see the fig.) of the size $l\times 4$ has no border cells except those that have common points with the polyline $CABD$, then this polygon can be cut off, and we get a good polygon again by moving the trapezoids adjacent to $AB$ by $4$ cells up (similar to the case $AB=3$).



Suppose that the rectangle $CABD$ contains other boundary cells. Color some cells of the plane in $2$ colors, as in the figure. Then all boundary cells of the form $\square$ have color $1$, of the form $\square$ have color $2$ (since from each cell of the first type the cell of the second is located through one). Consider all the boundary cells inside the rectangle $CABD$ and choose the lower one that has no common points with the polyline. Then some adjacent cell to it on the left or right should be the boundary cell, otherwise the border will not split into trapezoids (if this cell is colored, it contains part of the trapezoid with horizontal bases, otherwise the cell is not lower, and if not, the trapezoid containing this cell cannot have vertical bases for the same reasons). Of the two adjacent boundary cells at least one is crossed by the diagonal of the trapezoid. Without loss of generality, we assume that it has the form $\square$ (it is dashed in the figure). Then it has color $1$ and is located two cells higher than the color $2$ cell of the $\square$ type adjacent to $AB$, otherwise it cannot be located inside $CABD$ which is true for any of its inner color $1$ cells. Then it is clear that the part of this cell is contained in the trapezoid, located to the right of it.



Now we will make cuts, as shown in the figure, thus cutting the polygon into $2$ parts. The area of the polygon is $(4a+1)+(4b+1)+3\equiv 1(\mathrm{mod}4)$, as required.