A circle is divided into $2n$ equal by $2n$ points. Ali draws $n+1$ arcs, of length $1,2,\ldots,n+1$. Prove that we can find two arcs, such that one of them is inside in the other one.
Problem
Source: Iran Second Round 2015 - Problem 5 day 2
Tags: combinatorics, Iran
09.05.2015 15:36
Induction on $n$.Base case $n=1$ is trivial.Suppose opposite. For $2$ arcs $i,j$ define $f(i,j)=0$ if one is contained in another and else $f(i,j)=1$. Now,place $1$ somewhere.Since no arc contains $1$,the problem is equivalent that we place arcs $2,3...n+1$ on a segment of lenght $2n-1$ units.Now,we can move all endpoints(endpoint of an arc on the segment is it rightmost point) by $1$ to the left and the end of the segment of $2n-1$.By this moving,$f(i,j)$ doesn't change,so the problem is equivalent with placing arcs $1,2...n$ on a segment of lenght $2*(n-1)$, and just turn this segment into a circle by connecting its endpoints and we have our problem for $n-1$.
09.06.2015 23:45
Proof by contradiction. Consider all arcs to run clockwise around the circle. Let A and B be the arcs of length $n+1$ and $1$ respectively, and assume that A and B start at positions $0,t$ clockwise. Any arc that starts a position $0<k<t$ must end at a unique point between positions $n+2,t$ inclusively. That makes for $t-n-1$ possible arcs. There can only be $2n-t-1$ arcs starting between $t+1,2n-1$ inclusively, for a total of $n-2$ other arcs, besides A,B, which is one short.