OMM 2019 Problem 3

Let $n\geq 2$ be an integer. Consider $2n$ points around a circle. Each vertex has been tagged with one integer from $1$ to $n$ , inclusive, and each one of these integers has been used exactly two times. Isabel divides the points into $n$ pairs, and draws the segments joining them, with the condition that the segments do not intersect. Then, she assigns to each segment the greatest integer between its endpoints.

a) Show that, no matter how the points have been tagged, Isabel can always choose the pairs in such a way that she uses exactly $\lceil n/2\rceil$ numbers to tag the segments.

b) Can the points be tagged in such a way that, no matter how Isabel divides the points into pairs, she always uses exactly $\lceil n/2\rceil$ numbers to tag the segments?

Note. For each real number $x$ , $\lceil x\rceil$ denotes the least integer greater than or equal to $x$ . For example, $\lceil 3.6\rceil=4$ and $\lceil 2\rceil=2$ .

Proposed by Victor Domínguez