Some cells of a checkered plane are marked so that figure $A$ formed by marked cells satisfies the following condition:$1)$ any cell of the figure $A$ has exactly two adjacent cells of $A$; and $2)$ the figure $A$ can be divided into isosceles trapezoids of area $2$ with vertices at the grid nodes (and acute angles of trapezoids are equal to $45$) . Prove that the number of marked cells is divisible by $8$.
Problem
Source: 2018 Belarussian National Olympiad 10.4
Tags: combinatorics, trapezoid, Coloring
Pathological
31.03.2019 19:45
Consider the polygon formed when we draw the midlines of each of the trapezoids. Since every trapezoid's midline is of length $2$ and every trapezoid's area is also $2,$ we need to show that the perimeter of this polygon is divisible by $8.$ Scale down such that every midline is of length $1$ unit, so that we need to show that it's a multiple of $4.$
It's easy to see that this polygon has the properties that:
1. Every side is either vertical or horizontal, and has integer length. Furthermore, they alternate between vertical and horizontal.
2. If a side has even length, then it's adjacent sides go in opposite directions (so neighboring angles sum to $360$). Otherwise they go in the same direction.
We claim that these two conditions are enough to prove that the polygon has a perimeter divisible by $4.$ To do so, if there are two adjacent sides with length more than $2,$ then we can "carve out" or "attach" a $2 \times 2$ square as to strictly decrease the sum of the squares of all sides (clearly perimeter is preserved). In this way, we eventually arrive at a polygon where out of any two adjacent sides, one has length $\le 2$. If there are two adjacent sides of length $1,$ it's easy to see that our polygon is just a $1 \times 1$ square, which has perimeter $4.$ Otherwise, consider a side of length $1,$ and cut out a $1 \times 2$ square from the side of length $1,$ as such:
_
||
||
||
||
turns into
_
||
||
Then, the perimeter is preserved modulo $4$ (decreases by $4$) and the property is still preserved.
Therefore, we need only consider the case where all sides have length at least $2,$ and so as a result of our previous assumption, at least one out of any two adjacent sides has length $2.$ If all side lengths are even, then we're clearly done by scaling down by $\frac12$, and noting that any lattice polygon has even perimeter.
Otherwise, simply consider an odd side and keep carving out $2 \times 2$'s until the odd side has only a length $1$ part left. Then, use the previous operation on sides of length $1$ to strictly decrease the perimeter. Eventually, we know that we must arrive at a $1 \times 1$ square, and we have preserved the perimeter modulo $4$ with each operation, so we're done.
$\square$