Macedonian Junior Mathematical Olympiad

Question

Let A and B be two identical convex polygons, each having area 2015. The polygon A is divided into polygons A_1, A_2, , A_2015 with positive area, and the polygon B into polygons B_1, B_2, , B_2015 with positive area. The polygons A_1, A_2, , A_2015, B_1, B_2, , B_2015 are colored with 2015 colors, in such a way that A_i is colored differently from A_j and B_i is colored differently from B_j, for i j. After overlapping the polygons A and B, we calculate the sum of the areas of the parts that have the same color. Prove that there exists a coloring of the polygons for which this sum is at least 1.

Accepted Answer

After the overlapping of the polygons we get

C_{ij} = A_{i} \cap B_{j}

,

i, j \in {1, 2, \dots, 2015}

. The polygons

B_{1}, B_{2}, \dots, B_{2015}

can be colored in

2015!

ways.

Let a coloring of

A_{1}, A_{2}, \dots, A_{2015}

be given. For an arbitrary coloring of

B_{1}, B_{2}, \dots, B_{2015}

which we denote by

n

, let

O_{n}

be the sum of the areas of the parts from the two polygons colored with the same color.

Then

O_{n} = \sum_{i, j = 1}^{2015} c_{ij} P (C_{ij})

, where

c_{ij} = 1

if

A_{i}

and

B_{j}

are colored with the same color and

c_{ij} = 0

in the other cases. We get that

\sum_{n = 1}^{2015!} O_{n} = \sum_{i, j = 1}^{2015} d_{ij} P (C_{ij})

, where

d_{ij}

is the number of colorings of

B_{1}, B_{2}, \dots, B_{2015}

in which

A_{i}

and

B_{j}

have the same color. It is obvious that

d_{ij} = 2014!

. According to that,

\sum_{n = 1}^{2015!} O_{n} = \sum_{i, j = 1}^{2015} d_{ij} P (C_{ij}) = 2014! \cdot 2015 = 2015!

.

Finally, from

O_{1} + O_{2} + \dots + O_{2015!} = 2015!

it follows that there exists

k \in {1, 2, \dots, 2015!}

for which

O_{k} \geq 1

, which was to be proven.