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
Problem
Source: Mexico National Olympiad 2019 Problem 3
Tags: combinatorics, Coloring
MarkBcc168
13.11.2019 13:40
(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,\hdots,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,\hdots,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,\hdots, A_{2n}$. Suppose that $A_1$ is paired with $A_k$. Then $A_2,\hdots,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.
The claim implies that the tagged number must be in $\left\lfloor\frac{n}{2}\right\rfloor,\left\lfloor\frac{n}{2}\right\rfloor+1,\hdots,n$ hence we are done.
gnoka
14.11.2019 17:37
Wrong Note. 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$. Fixed, thanks! ~dj
Letteer
29.11.2019 14:45
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)
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.