Argentine National Olympiad 2016

Consider the problem for a circle of length $n$ divided into unit arcs by $n$ black points, and $d$ arcs of lengths $1$, $2$, ..., $d$ with black endpoints such that none of them contains another. We show that the maximal admissible $d$ equals $\lfloor \frac{n+1}{2}\rfloor$; here $\lfloor \cdot \rfloor$ denotes the integer part of a number.

All arcs considered below have black endpoints. We say that an arc $\text{overarc}PQ$ has start $P$ (or starts at $P$) if $Q$ can be reached from $P$ by going along the arc in counterclockwise direction. The meaning of "$\text{overarc}PQ$ has end $Q$ (or ends at $Q$)" is analogous.

Let ${\gamma }_1,\dots ,{\gamma }_d$ be arcs on the circle with lengths $1$, $2$, ..., $d$ such that none of them contains another. Consider the shortest arc ${\gamma }_1=\text{overarc}AB$, starting at $A$, and the longest one ${\gamma }_d=\text{overarc}CD$, starting at $C$. Let $X$ be the set of black points on arc $\text{overarc}BC$ with start $B$, excluding its end $C$. Let $Y$ be the set of black points on arc $\text{overarc}DA$ with end $A$, excluding its start $D$. Finally let $Z$ be the set of black points on the closed arc ${\gamma }_d=\text{overarc}CD$. Then each black point belongs to exactly one of $X$, $Y$ and $Z$.

Now observe that every arc ${\gamma }_m$ with $1<m<d$ satisfies exactly one of the following conditions: (1) ${\gamma }_m$ starts in $X$; (2) ${\gamma }_m$ ends in $Y$. Clearly (1) and (2) do not hold simultaneously, otherwise ${\gamma }_m$ contains arc ${\gamma }_d=\text{overarc}CD$. Suppose that (1) does not hold. Then ${\gamma }_m$ starts in $Y\cup Z$, that is, in the arc $\text{overarc}CA$ with start $C$. Hence ${\gamma }_m$ also ends in the same arc $\text{overarc}CA$, or else ${\gamma }_m$ contains ${\gamma }_1=\text{overarc}AB$. In addition ${\gamma }_m$ does not end in ${\gamma }_d=\text{overarc}CD$. Otherwise ${\gamma }_m$ also starts in ${\gamma }_d$, hence ${\gamma }_d$ contains a ${\gamma }_m$. In conclusion ${\gamma }_m$ ends in $Y$, i.e., condition (2) holds. This completes the justification.

Let there be $x$ arcs ${\gamma }_m$ satisfying (1), $1<m<d$. They start at different points of the set $X$, or else some of them contains another. Hence $x\le |X|$. Analogously, if $y$ is the number of arcs ${\gamma }_m$ satisfying (2), $1<m<d$, then $y\le |Y|$. By the reasoning above $x+y=d-2$, therefore $d-2=x+y\le |X|+|Y|=n-|Z|=n-d-1$. This gives the upper bound $d\le \lfloor \frac{n+1}{2}\rfloor$.

For odd $n=2k+1$ we have $\lfloor \frac{n+1}{2}\rfloor =k+1$, and $d=k+1$ is admissible. Label the black points $1$, ..., $2k+1$ in counterclockwise direction and consider $k+1$ arcs ${\gamma }_1,\dots ,{\gamma }_{k+1}$ with lengths $1$, ..., $k+1$. For each $m=1,\dots ,k+1$ place arc ${\gamma }_m$ so that it starts at point $m$. It is immediate that this configuration satisfies the requirements. We mention only that arc ${\gamma }_{k+1}$ ends at point $1$, hence it does not contain arc ${\gamma }_1$. Thus $d=k+1$ is admissible, implying that so are all smaller natural numbers. In conclusion the solution to the problem for $n=2k+1$ are the numbers $1$, $2$, ..., $k+1$, yielding $1$, $2$, ..., $500$ as the answer to the original question.

Similarly, for even $n=2k$ we have $\lfloor \frac{n+1}{2}\rfloor =k$, and $d=k$ is admissible. The example for $d=k$ is analogous. Label the black points $1$, $2$, ..., $2k$ in counterclockwise direction and consider $k$ arcs ${\gamma }_1,\dots ,{\gamma }_k$ with lengths $1$, $2$, ..., $k$. For $m=1,\dots ,k$ place arc ${\gamma }_m$ so that it starts at point $m$. This configuration satisfies the requirements. So the solution for $n=2k$ are the numbers $1$, $2$, ..., $k$.