On a circle, 2022 points are chosen such that distance between two adjacent points is always the same. There are $k$ arcs, each having endpoints on chosen points, with different lengths. Arcs do not contain each other. What is the maximum possible number of $k$?
Problem
Source: Turkey TST 2022 P5 Day 2
Tags: combinatorics, combinatorics proposed
13.03.2022 17:05
Sketch of the solution (will add details later) Answer: $1011$ Proof of the bound: Let the selected arcs be $a_1,a_2,...,a_k$ First, observe that by decreasing the length of all arcs clockwise by $1$, we can assume the length of the smallest arc is $1.$ After that, let's number the points on the circle (like $1,2,..,2022$), viewed clockwise, with the starting point of the arc of length $1$ being $1$ and ending point $2$. If the starting point of the arc $a_t$ is $i_t$ and the end point is $j_t$, let's show this arc as $(i_t,j_t)$ unless if $i_t\geq j_t$ show this arc as $(i_t,j_t+2022).$ (while doing this we are starting from point $1$ and looking clockwise.) Now we can say that the lenght of the arc $a_t$ is equal to $j_t-i_t.$ WLOG assume $a_1=(1,2)$ Now, due to the conditions given in the problem: The start or end points of any two different arcs cannot be the same. There is no arc $a_t=(i_t,j_t)$ with $j_t \geq 2022.$ (otherwise arc $a_t$ would contain arc $a_1$) Now assume the contarary and WLOG say $1=i_1\leq i_2\leq i_3\leq ... \leq i_{1012}$ which implies $2=j_1\leq j_2\leq ... \leq j_{1012}.$ Since all arcs have different lengths, there must be a arc $a_s$ with a length greater than $1011$ between these 1012 arcs, thus $\implies j_s-i_s\geq 1012$. Finally we can get a contradiction because $ j_{1012}\geq j_{1011}+1 \geq ...\geq j_s +1012-s \geq i_s+1012+1012-s \geq i_{s-1} +1013+1012-s\geq ...\geq i_1+s+1011+1012-s=2024$ Example for $k=1011$: $(1,2),(2,4),...,(i,2i),...(1011,2022)$
22.12.2022 20:30
The answer is $k=1011$. Let's number the points with $1, 2 \dots ,2022$. Choose $1$ length arc from point $1$, $2$ length arc from point $2$ and so on to $1011$ length arc from point $1011$. This gives the desired $k=1011$, since every problem condition is satisfied. Suppose $k \geq 1012$. Let the length of shortest arc be $e$ and the longest one $f$. $f \geq e+1012$, because every arc has a different length. WLOG suppose the starting point for the shortest arc is $1$ and lengths are sorted in $1 \rightarrow 2022$ direction, cause we can always change them, if they are not, since the changed one would also satisfy the conditions, if the original one did. Now let $b_i$ be the ending point of the $i$-th arc. $b_1 = e+1$. Since every arc's length is at least $1$ more than last one's, the difference between ending points can't be less than $2$, because the small arc would be contained in the big arc. Hence $b_i \geq b_{i-1} + 2 \geq b_{i-2} + 4 \geq \dots \geq b_1 + 2i - 2 = e + 2i - 1$. $b_{last} \geq b_{1012} \geq e+2023 > 2022+e \implies$ the longest arc contains the shortest arc, which is a contradiction. $\blacksquare$