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?
What I thought: (a) We will prove the following stronger claim.
Claim: Consider $n$ red points and $n$ blue points around a circle. Then Isabel can split these points into $n$ pairs, each consisting one red point and one blue point so that if she draws segments joining each pair, then the segments do not intersect each other.
Proof: By letting Isabel walking around circle, she can definitely find a pair of adjacent points with different color. Delete this pair and induct down.
The problem follows by coloring the first $n$ elements in $1,1,2,2,3,3,….,n,n$ red and the last $n$ blue.
(b) The answer is yes. Again, color the first $n$ elements in $1,1,2,2,3,3,…,n,n$ red and the last $n$ blue. We place the label so that the color is R,B,R,B,… when read clockwise around the circle. We claim that
Claim: The red segment is always paired with blue segment.
Proof: Label points $A_1, A_2,…., A_{2n}$. Suppose that $A_1$ is paired with $A_k$. Then $A_2,….,A_{k-1}$ must be paired within themselves. So $k-2$ is even which means $1,k$ have different parity and thus have different color.
Who can give me a more complete and formalized solution than this, thank you
Mexico National Olympiad 2019
Best Answer
I didn't understand what you wrote at all.
Here is my solution to the problem.
A) We present the even $n$ case.
Mark the $n$ numbers $ n, n, n-1, n-1, n-2, n-2, \ldots , \lceil \frac{n+1}{2} \rceil, \lceil \frac{n+1}{2} \rceil $.
There must be one of these which is adjacent to an unmarked number. Draw a line segment between these 2, and then ignore them.
Of the remaining $n-1$ marked numbers and $n-1$ unmarked numbers, likewise we can find an adjacent pairing of marked-unmarked. Draw a line segment between these 2, and then ignore them.
Repeat this till we're done pairing all of the numbers.
Clearly, each line segment is tagged with the marked number, so there are exactly $ \lceil \frac{n}{2} \rceil$ of them.
The odd $n$ case is similar, just having to account for the last term. It is left as an exercise to the reader.
B) You made the observation that "A necessary (though not sufficient) condition for these line segments to not intersect, is that they must connect an odd parity to an even parity." This helps greatly with this part.
In the even parity positions, place the numbers $ n, n, n-1, n-1, n-2, n-2, \ldots , \lceil \frac{n+1}{2} \rceil $ (the number of copies of the last term depend on the parity of $n$) in any order.
In the odd parity positions, place the numbers $1, 1, 2, 2, \ldots $ in any order.
Then, clearly for any odd-even pairing, the greatest integer is that on the even parity index. Hence, this positioning uses exactly $ \lceil \frac{n}{2} \rceil $ tags.