Olympiad Maths Prep

Library / /2 of 2

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Bulgaria

A convex 20192019-gon is given, for which no three diagonals intersect in a point. An intersection point of two diagonals, internal for the given polygon will be called “knot”. Two knots are called “neighbors” if they share a common diagonal. A closed path between neighboring knots, such that no three consecutive knots share a diagonal, will be called “cycle”. Find the maximal number of knots that can be colored, such that there exists no colored cycle (that is a cycle, containing only colored knots)?

Solution

Answer: 2019(20193)21=2035151\frac{2019(2019-3)}{2} - 1 = 2035151.
Let us consider the more general problem, where 20192019 is replaced with n4n \ge 4. We will prove that in a convex nn-gon, neither three of which diagonals have a common point, we can color at most n(n3)21\frac{n(n-3)}{2} - 1 of the knots without generating a colored cycle.

First, we prove an estimate from above, i.e., that the number of colored knots needs to be less than n(n3)2\frac{n(n-3)}{2}. Assume the contrary and let us consider a planar graph, with vertices corresponding to the polygon diagonals and edges corresponding to the colored knots. Since the number of diagonals in a convex nn-gon equals n(n3)2\frac{n(n-3)}{2}, the edges in the constructed graph outnumber the vertices, thus the graph contains a cycle. But it is easy to see that there is a one-to-one correspondence between the cycles in the constructed graph and the colored cycles in the polygon. Hence, there exists a colored cycle, which is a contradiction.

Now, it remains to show a strategy for coloring n(n3)21\frac{n(n-3)}{2} - 1 knots, without generating a colored cycle. We do it by induction. The base n=4n=4 is trivial. Now, let us have a strategy for coloring n(n3)21\frac{n(n-3)}{2} - 1 of the knots of an arbitrary convex nn-gon without generating a colored cycle. Consider a convex (n+1)(n+1)-gon A1A2An+1A_1A_2\dots A_{n+1} and take a “good” coloring for the knots of A1A2AnA_1A_2\dots A_n. Adding the vertex An+1A_{n+1}, we transform the side A1AnA_1A_n for A1A2AnA_1A_2\dots A_n into a diagonal for A1A2An+1A_1A_2\dots A_{n+1} and we generate additional n2n-2 diagonals An+1AiA_{n+1}A_i, i=2,,n1i=2,\dots,n-1. Therefore, the diagonal A1AnA_1A_n contains exactly n2n-2 knots (all corresponding to the additional diagonals) and we color all of them. Finally, we color one more knot on a diagonal through An+1A_{n+1}, e.g., the intersection point of An+1A2A_{n+1}A_2 and A1A3A_1A_3. (Due to the convexity of the polygon, it is clear that all considered intersection points are internal, thus are indeed knots!) Overall, we end up with
n(n3)21+(n1)=(n+1)(n2)21 \frac{n(n-3)}{2} - 1 + (n-1) = \frac{(n+1)(n-2)}{2} - 1
colored points. Among the freshly colored n1n-1 knots, “neighboring” appears only with respect to the diagonals A1AnA_1A_n or A2An+1A_2A_{n+1}. Furthermore, every other diagonal through An+1A_{n+1} contains at most one colored knot, i.e., it doesn’t generate any “neighboring” relations. It is straightforward to observe that in order to exist a colored cycle, given that the coloring of the knots of A1A2...AnA_1A_2...A_n is acyclic, at least two of the freshly colored knots should be part of this cycle, which is impossible due to construction. Induction is completed and so is the proof.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.