Bariz - Problem

Source: Bulgaria National Olympiad 2019

Tags: combinatorics, combinatorial geometry, geometry

k.vasilev

20.04.2019 17:37

Let $P$ be a $2019-$gon, such that no three of its diagonals concur at an internal point. We will call each internal intersection point of diagonals of $P$ a knot. What is the greatest number of knots one can choose, such that there doesn't exist a cycle of chosen knots? ( Every two adjacent knots in a cycle must be on the same diagonal and on every diagonal there are at most two knots from a cycle.)

k.vasilev wrote: Let $P$ be a $2019-$gon, such that no three of its diagonals concur at an internal point. We will call each internal intersection point of diagonals of $P$ a knot. What is the greatest number of knots one can choose, such that there doesn't exist a cycle of chosen knots? ( Every two adjacent knots in a cycle must be on the same diagonal and on every diagonal there are at most two knots from a cycle.) Just a clarification. The text in red didn't take part in the original Bulgarian text as presented in the competition and published afterwards. It was added on a fly during the contest.