MathDB

3

Part of 2019 Mexico National Olympiad

Problems(1)

Isabel pairs into segments which do not intersect.

Source: Mexico National Olympiad 2019 Problem 3

11/12/2019
Let n≥2n\geq 2 be an integer. Consider 2n2n points around a circle. Each vertex has been tagged with one integer from 11 to nn, inclusive, and each one of these integers has been used exactly two times. Isabel divides the points into nn 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 ⌈n/2⌉\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 ⌈n/2⌉\lceil n/2\rceil numbers to tag the segments?
Note. For each real number xx, ⌈x⌉\lceil x\rceil denotes the least integer greater than or equal to xx. For example, ⌈3.6⌉=4\lceil 3.6\rceil=4 and ⌈2⌉=2\lceil 2\rceil=2.
Proposed by Victor Domínguez
combinatoricsColoring