USAMO 2012 Problem 2

A circle is divided into $432$ congruent arcs by $432$ points.  The points are colored in four colors such that some $108$ points are colored Red, some $108$ points are colored Green, some $108$ points are colored Blue, and the remaining $108$ points are colored Yellow.  Prove that one can choose three points of each color in such a way that the four triangles formed by the chosen points of the same color are congruent.

Hints I got (select the whole line to see): rotation, pigeonhole principle, quadruple

Proof:

Consider quadruples ordered clockwise in RGBY, there are $431\times 430\times 429$ possible shapes. There are also a total of $108^4$ ordered RGBY quadruples. If any shape has at least $3$ instances then we are done. However, $\frac{108^4}{431\times 430\times 429}$ is between $1$ and $2$, so the argument doesn't seem to work. Now what?

Interestingly, it does if we are greedier.

First, consider ordered RG arcs. There are $108^2$ of them and $431$ possible lengths, so at least $\lceil \frac{108^2}{431}\rceil=28$ ordered RG arcs have the same length.

Next, consider ordered RGB triangles extended from these $28$ or more ordered RG arcs, there are $28\times 108$ with at most $430$ shapes, so we get at least $\lceil \frac{28\times 108}{430}\rceil=8$ ordered RGB triangles of the same shape.

Finally, we have at least $8\times 108$ ordered RGBY quadruples extended from these $8$ or more ordered RGB triangles falling into at most $429$ shapes, so some shape would have at least $\lceil \frac{8\times 108}{429} \rceil=3$ instances.

Q.E.D.

Note that ceiling operation in each step is essential. Moreover, it proves a stronger result, that the congruent triangles have the same orientation.