68. National Mathematical Olympiad

Answer: $\frac{2019(2019-3)}{2}-1=2035151$. Let us consider the more general problem, where $2019$ is replaced with $n\ge 4$. We will prove that in a convex $n$-gon, neither three of which diagonals have a common point, we can color at most $\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 $\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 $n$-gon equals $\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 $\frac{n(n-3)}{2}-1$ knots, without generating a colored cycle. We do it by induction. The base $n=4$ is trivial. Now, let us have a strategy for coloring $\frac{n(n-3)}{2}-1$ of the knots of an arbitrary convex $n$-gon without generating a colored cycle. Consider a convex $(n+1)$-gon $A_1{A}_2\dots A_{n+1}$ and take a “good” coloring for the knots of $A_1{A}_2\dots A_n$. Adding the vertex $A_{n+1}$, we transform the side $A_1{A}_n$ for $A_1{A}_2\dots A_n$ into a diagonal for $A_1{A}_2\dots A_{n+1}$ and we generate additional $n-2$ diagonals $A_{n+1}{A}_i$, $i=2,\dots ,n-1$. Therefore, the diagonal $A_1{A}_n$ contains exactly $n-2$ knots (all corresponding to the additional diagonals) and we color all of them. Finally, we color one more knot on a diagonal through $A_{n+1}$, e.g., the intersection point of $A_{n+1}{A}_2$ and $A_1{A}_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 $$\frac{n(n-3)}{2}-1+(n-1)=\frac{(n+1)(n-2)}{2}-1$$ colored points. Among the freshly colored $n-1$ knots, “neighboring” appears only with respect to the diagonals $A_1{A}_n$ or $A_2{A}_{n+1}$. Furthermore, every other diagonal through $A_{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 $A_1{A}_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.