Given $2^{2010} + 1 $ points in the plane, prove that some three of them determine an angle of at least $\frac{2009π}{2010}$
This problem has the following solution:
Proof: split the pairs into 2010 classes, according to the orientation of the line between them. Too many vertices for the complete graph to be the union of 2010 bipartite graphs, so there’s an odd cycle within one class, and this gives the angle we want.
I don’t understand this solution. Can someone clearly explain?
Here's a more complete proof with the same idea.
Draw all edges between the points, coloring them according to the angle the line makes with the $x$-axis: $[0,\frac{\pi}{2010})$ gets one color, $[\frac{\pi}{2010},\frac{2\pi}{2010})$ gets the next, and so on. Here's an example with $3$ playing the role of $2010$:
If edges $PQ$ and $QR$ have the same color, then because lines $PQ$ and $QR$ have nearly the same angle with the $x$-axis, they make nearly the same angle with each other: an angle of less than $\frac{\pi}{2010}$. This means that $\angle PQR$ is either smaller than $\frac{\pi}{2010}$ (when $P$ and $R$ are nearly in the same direction from $Q$), or larger than $\frac{2009\pi}{2010}$ (when $P$ and $R$ are nearly in opposite directions from $Q$). Our goal is to prove that the latter case sometimes happens.
The idea is that if, in a certain color, all such angles are small, then the graph induced by that color is bipartite. Orient each edge $PQ$ to be $\overrightarrow{PQ}$ if the $x$-coordinate of $Q$ is bigger than the $x$-coordinate of $P$. (We can assume that $x$-coordinates are never equal by rotating the picture slightly at the beginning, if necessary.) If we ever see two incident edges oriented $\overrightarrow{PQ}, \overrightarrow{QR}$, then $\angle PQR$ is almost $\pi$ rather than almost $0$. If we don't ever see two incident edges oriented $\overrightarrow{PQ}, \overrightarrow{QR}$, then all vertices are either sources or sinks in this orientation, which induces a bipartition.
Now comes the graph theory. A complete graph on $2^{2010}+1$ vertices cannot be partitioned into $2010$ bipartite graphs. For each bipartite graph, we can pick an $A$-side and a $B$-side, then there are $2^{2010}$ possibilities for whether a vertex is on the $A$-side or the $B$-side of each graph. By pigeonhole, two of the $2^{2010}+1$ vertices are on the same side of the bipartition in each bipartite graph, which means the edge between them is left uncolored.
As a result, one of our color classes is not bipartite, which means it contains an obtuse angle.