AoPS - Problem

Source: China Team Selection Test 2016 Test 3 Day 2 Q5

Tags: combinatorics, graph theory, combinatorial geometry

buzzychaoz

26.03.2016 13:35

Let $S$ be a finite set of points on a plane, where no three points are collinear, and the convex hull of $S$, $\Omega$, is a $2016-$gon $A_1A_2\ldots A_{2016}$. Every point on $S$ is labelled one of the four numbers $\pm 1,\pm 2$, such that for $i=1,2,\ldots , 1008,$ the numbers labelled on points $A_i$ and $A_{i+1008}$ are the negative of each other. Draw triangles whose vertices are in $S$, such that any two triangles do not have any common interior points, and the union of these triangles is $\Omega$. Prove that there must exist a triangle, where the numbers labelled on some two of its vertices are the negative of each other.

Lemma: along the convex hull, either there are an odd number of segments going $1\rightarrow -2$ or $2\rightarrow -1$. Proof: Imagine moving along the path from $A_i$ to $A_{i+1008}$. The number at the vertex changes sign an odd number of times, so $\#(1\rightarrow -2)+\#(-1\rightarrow 2)+\#(2\rightarrow -1)+\#(-2\rightarrow 1)$ is odd, by assumption (that there are no edge linking $1,-1$ or $2,-2$). Now one of $\#(1\rightarrow -2)+\#(-1\rightarrow 2)$, $\#(2\rightarrow -1)+\#(-2\rightarrow 1)$ is odd, so by re-labeling assume it is the former which is odd. But $\#(1\rightarrow -2)+\#(-1\rightarrow 2)$ odd along half the perimeter means that $\#(1\rightarrow -2)$ is odd along the whole perimeter, by the "anti-symmetry" condition. So WLOG $\#(1\rightarrow -2)$ is odd along the perimeter. We now consider the type of permissible triangles. Since in each triangle there must be two vertices that share the same magnitude, hence they must be of the same sign (otherwise done). Thus in each triangle there are two vertices with the same value, and thus each triangle has an even number of segments with endpoints $1,-2$. Count the number $N$ of segment-triangle pairs, where the segment has endpoints $1,-2$ and the segment is at the boundary of the triangle. Grouping by segments, $N$ is odd, but grouping by triangles $N$ is even. Contradiction.