uniolympiads Ελληνικά

IMC 2022, Day 2, Problem 5

We colour all the sides and diagonals of a regular polygon PP with 4343 vertices either red or blue in such a way that every vertex is an endpoint of 2020 red segments and 2222 blue segments. A triangle formed by vertices of PP is called monochromatic if all of its sides have the same colour. Suppose that there are 20222022 blue monochromatic triangles. How many red monochromatic triangles are there?

Original from the official PDFWe colour all the sides and diagonals of a regular polygon P with 43 vertices either red or blue in such a way that every vertex is an endpoint of 20 red segments and 22 blue segments. A triangle formed by vertices of P is called monochromatic if all of its sides have the same colour. Suppose that there are 2022 blue monochromatic triangles. How many red monochromatic triangles are there?

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Mike Daas, Universiteit Leiden)

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

Solution. 1 Define a cherry to be a set of two distinct edges from K43K_{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−P2M - P, where MM is the number of monochromatic cherries and PP 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 K43K_{43}. By construction the contribution of a polychromatic triangle will vanish, whereas a monochromatic triangle will contribute 6. We conclude that

2M−P=6⋅{number of monochromatic triangles}.2M - P = 6 \cdot \{\text{number of monochromatic triangles}\}.

Consider any vertex vv. Let MvM_v be the number of monochromatic cherries with central vertex vv and PvP_v the number such polychromatic cherries. It then follows that

Mv=20⋅192+22⋅212=421andPv=20⋅22=440.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 vv it holds that 2Mv−Pv=4022M_v - P_v = 402. Adding up all these contributions, we find that

2M−P=43⋅402.2M - P = 43 \cdot 402.

We conclude that there are 43⋅402/6=43⋅67=288143 \cdot 402/6 = 43 \cdot 67 = 2881 monochromatic triangles in total. Since 2022 of these were blue, 859 must be red.

Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?