A polygon (not necessarily convex) on the coordinate plane is called plump if it satisfies the following conditions: $\bullet$ coordinates of vertices are integers; $\bullet$ each side forms an angle of $0^\circ$, $90^\circ$, or $45^\circ$ with the abscissa axis; $\bullet$ internal angles belong to the interval $[90^\circ, 270^\circ]$. Prove that if a square of each side length of a plump polygon is even, then such a polygon can be cut into several convex plump polygons. (A. Yuran)
Problem
Source: 2019 Belarus Team Selection Test 5.3
Tags: combinatorics, analytic geometry
02.09.2019 23:52
Call a lattice point tasty if its $x-$ and $y-$ coordinates have the same parity. Call a plump polygon with all squares of side lengths even special. We'll prove that any special plump polygon can be cut into more than one convex plump polygons, by induction on the area of the polygon. Such an induction is possible because the area of the polygon must be an integer divided by two by Shoelace. The base cases when the area of the polygon is $<4$ will be ignored, as they are trivial. Now, let's assume that the induction hypothesis holds when the area of the plump polygon is $<x$, where $x$ is some integer divided by two. Suppose now that we have a special plump polygon of area $x.$ First, shift this polygon so that one of the vertices coincides with the origin of the Cartesian plane. Now, since the polygon is special, we know that every one of its vertices is tasty. Call a line of the form $y = x+2k$ for some $k \in \mathbb{Z}$ tangy and a line of the form $y = -x + 2k$ for some $k \in \mathbb{Z}$ wangy . Since the area of the polygon is at least $4$, there either exists a tangy line for which there is a part of the polygon with nonzero area on each side of it, or there exists a wangy line with such a property. WLOG there exists such a tangy line, say $\ell$. Then, observe that $\ell$ intersects a horizontal/vertical side of the polygon at a tasty point. Furthermore, every other side of the polygon is either tangy or wangy, and so $\ell$ intersects there lines at tasty points as well. Therefore, this line splits the polygon into at least two polygons, each of which still only has tasty vertices and is also plump. This clearly then implies that these smaller polygons are special as well, and so we can just apply the inductive hypothesis on these special plump polygons of smaller area. The induction is complete. $\square$