Taiwan IMO Selection Camp

Let $a_k$ denote the number of isosceles triangles, among all isosceles triangles, whose three vertices include exactly $k$ colors. Then the problem is equivalent to proving $a_3 \ge 1$.

We use proof by contradiction. Suppose $a_3 = 0$. Consider the set
$$X = \{(\Delta, E) : \Delta \text{是等腰三角形}, E \text{是 } \Delta \text{的一邊}, E \text{的兩端點不同色}\}.$$

Let us translate that set definition properly:
$$X = \{(\Delta, E) : \Delta \text{ is an isosceles triangle}, E \text{ is a side of } \Delta, \text{ the two endpoints of } E \text{ have different colors}\}.$$
Let us count the number of elements in $X$ in two different ways:

– First, for each triangle:

* A triangle with only one color must have no edges whose endpoints are of different colors.
* A triangle with exactly two colors has exactly $2$ edges whose endpoints are of different colors.
* By assumption, there are no triangles with three colors.

Combining the above, $|X| = 2a_2$.

– On the other hand, choose any two vertices $A, B$; since $(n, 3) = 1$, we know that $AB$ is a side of exactly $3$ isosceles triangles. If we let $b, c, d$ denote the number of vertices of the three colors respectively, then the number of edges whose two endpoints have different colors is $bc + bd + cd$, so $|X| = 3(bc + bd + cd)$.

However, by the assumption of the problem, $b, c, d$ are all odd, so $3(bc + bd + cd)$ is odd, and thus it cannot equal $2a_2$, a contradiction! Therefore $a_3 \ge 1$.