The checkered plane is painted black and white, after a chessboard fashion. A polygon $\Pi$ of area $S$ and perimeter $P$ consists of some of these unit squares (i.e., its sides go along the borders of the squares). Prove the polygon $\Pi$ contains not more than $\dfrac {S} {2} + \dfrac {P} {8}$, and not less than $\dfrac {S} {2} - \dfrac {P} {8}$ squares of a same color. (Alexander Magazinov)
Problem
Source: Stars of Mathematics 2011 - Juniors - Problem 3
Tags: geometry, perimeter, combinatorics proposed, combinatorics
11.10.2012 09:16
Here is my solution given in the contest: Let $x_i,\ i=\overline{0;4}$ be the number of the black cells of the polygon with $i$ neighbors inside the polygon. Let $y_i,\ i=\overline{0;4}$ be the number of the white cells of the polygon with $i$ neighbors inside the polygon. We apparently have $4x_4+3x_3+2x_2+x_1$ white cells. But white cells with $k$ neighbors was counted $k$ times. And the white cells have only black neighbors. So we have $4x_4+3x_3+2x_2+x_1=4y_4+3y_3+2y_2+y_1$. Now I will calculate $S$ and $P$. The cells with $k$ neighbors have $4-k$ exists outside the polygon, so they participate at the perimeter with $4-k$ sides. Therefore ${P=4(x_0+y_0)+3(x_1+y_1)+2(x_2+y_2)+(x_3+y_3)}$ and obviously ${S=x_0+x_1+x_2+x_3+x_4+y_0+y_1+y_2+y_3+y_4}$. Now we have these relations and the conclusion becomes an easy inequality.
11.10.2012 16:54
Another approach: Since there are $S$ squares in total, either statement follows from the other; we'll prove the upper bound. Let $A$ be the number of pairs of unit squares in $\Pi$ that share a side, or the number of "adjacencies" between squares in $\Pi$ (these squares are of course oppositely colored). Then since each square has $4$ sides, it can contribute to at most $4$ "adjacencies", \[\min(B, W) \ge \frac{A}{4}\] Also, we can write $P = 4S - 2A$, since each square contributes $4$ to the total perimeter unless it shares a side with another square in $\Pi$, in which case the side was double counted. Then \[\frac{S}{2} + \frac{P}{8} = \frac{S}{2} + \frac{4S - 2A}{8} = S - \frac{A}{4} \ge S - \min(B, W)\] as desired. Interestingly, the term "polygon" here is unnecessary; "collection of unit squares" would suffice.