IMC 2022 · Day 2 · P5

Hint: Call two connecting edges a cherry. Double-count cherries.

Define a cherry to be a set of two distinct edges from $K_{43}$ that have a vertex in common. We observe that a monochromatic triangle always contains three monochromatic cherries, and that a polychromatic triangle always contains one monochromatic cherry and two polychromatic cherries. Therefore we study the quantity $2M - P$, where $M$ is the number of monochromatic cherries and $P$ is the number of polychromatic cherries. By observing that every cherry is part of a unique triangle, we can split this quantity up into all the distinct triangles in $K_{43}$. By construction the contribution of a polychromatic triangle will vanish, whereas a monochromatic triangle will contribute 6. We conclude that $$2M - P = 6 \cdot \{ \text{number of monochromatic triangles} \}.$$ Consider any vertex $v$. Let $M_v$ be the number of monochromatic cherries with central vertex $v$ and $P_v$ the number such polychromatic cherries. It then follows that $$M_v = \frac{20 \cdot 19}{2} + \frac{22 \cdot 21}{2} = 421 \quad \text{and} \quad P_v = 20 \cdot 22 = 440.$$ In other words, for any vertex $v$ it holds that $2 M_v - P_v = 402$. Adding up all these contributions, we find that $$2M - P = 43 \cdot 402.$$ We conclude that there are $43 \cdot 402 / 6 = 43 \cdot 67 = 2881$ monochromatic triangles in total. Since 2022 of these were blue, 859 must be red.