$A$ and $B$ are two identical convex polygons, each with an area of $2015$. The polygon $A$ is divided into polygons $A_1, A_2,...,A_{2015}$, while $B$ is divided into polygons $B_1, B_2,...,B_{2015}$. Each of these smaller polygons has a positive area. Furthermore, $A_1, A_2,...,A_{2015}$ and $B_1, B_2,...,B_{2015}$ are colored in $2015$ distinct colors, such that $A_i$ and $A_j$ are differently colored for every distinct $i$ and $j$ and $B_i$ and $B_j$ are also differently colored for every distinct $i$ and $j$. After $A$ and $B$ overlap, we calculate the sum of the areas with the same colors. Prove that we can color the polygons such that this sum is at least $1$.
Problem
Source: 2015 JBMO TST - Macedonia, Problem 5
Tags: polygon, Coloring, combinatorics, 2015
socrates
03.03.2016 15:29
Up! Up!
elVerde
08.03.2016 00:36
Fix $A$'s coloring and consider the set $C$ of all $2015!$ possible and distinct colorings of $B$.
For each $c\in C$, let $f(c)$ be the sum of the areas with the same colors after $A$ and $B$ overlap.
Once the polygons $A$ and $B$ overlap we get a new polygon $P$ that gets even further subdivided, as the result of the overlapping of the divisions of both $A$ and $B$. Suppose that $P$ is divided into a total of $n\geq 2015$ polygons. Call these $n$ polygons regions. Each region is the intersection of some $A_i$ and $B_j$ and the pairwise disjoint union of the regions is $P$. Make the convention each region has the same color as the underlying $A_i$.
For each $B_k$, consider the nonempty territory of all regions it covers - that is, all regions that result from the intersection of some $A_i$ with this $B_k$. Since there are $2015$ colors, we know that, running through all colorings $c\in C$, $B_k$ will have a given color in exactly $\tfrac{2015!}{2015}=2014!$ such colorings. Therefore, for each region in the territory of $B_k$, we know there are exactly $2014!$ colorings in $C$ for which $B_k$ will have the same color as that region. It follows that the contribution of that region to the sum $\sum\nolimits_{c\in C}f(c)$ is exactly $2014!$ times its own area. Going through all regions of $B_k$ it follows that the contribution of $B_k$ to the same sum is exactly $2014!\cdot\text{area}(B_k)$. Going through all $B_k$ yields
\begin{align*}
\sum_{c\in C}f(c)
&=2014!\cdot\text{area}(B_1)+2014!\cdot\text{area}(B_2)+\cdots+2014!\text{area}(B_{2015})\\
&=2014!\cdot\text{area}(B)=2015!.
\end{align*}If the task in the problem were impossible, then for every coloring $c\in C$ we would have $f(c)<1$, giving $\sum_{c\in C}f(c)<|C|=2015!$, a contradiction.