There are $n$ points on a circle ($n>1$). Define an "interval" as an arc of a circle such that it's start and finish are from those points. Consider a family of intervals $F$ such that for every element of $F$ like $A$ there is almost one other element of $F$ like $B$ such that $A \subseteq B$ (in this case we call $A$ is sub-interval of $B$). We call an interval maximal if it is not a sub-interval of any other interval. If $m$ is the number of maximal elements of $F$ and $a$ is number of non-maximal elements of $F,$ prove that $n\geq m+\frac a2.$
Problem
Source: Iran TST 2011 - Day 1 - Problem 3
Tags: combinatorics unsolved, combinatorics
ninjaturtle
11.05.2011 03:52
My attempt at a solution.
Consider the graph $G$ on $n$ points induced by maximal intervals of $F$. Then each vertex has degree at most $2$ (in fact, if at a vertex $v$ there are two maximal intervals, then they must be in different directions). Starting from a vertex and travel in both directions, we can see that the graph $G$ breaks up into connected components, where each component is either a path, or a cycle. Call those paths m-paths (an m-path can consist of a single point). Now we start adding non-maximal intervals. Assume we have $k$ m-paths. We'll show that there are at most $2k$ non-maximal intervals. Since the number of maximal intervals are $n-k$, we are done. We call endpoints of m-paths endvertices.
Claim 1: Each non-maximal interval connects at least one endvertex. For if $CD$ is non-maximal, and $C,D$ are not endvertices, there must be maximal intervals $Cx,Cy$ and $Dx,Dy$, all distinct (because $CD$ itself is not maximal), and two of them must contain $CD$.
We say that a non-maximal interval $CD$ is bad to $C$ if $C$ is an endvertex and there is a maximal interval $Cx$ such that $Cx \supset CD$. If $C$ is an endvertex and $CD$ is not bad to $C$ then we say $CD$ is good to $C$. Thus if $C$ is a trivial m-path then $CD$ is good to $C$.
Claim 2: If $CD$ is bad to $C$ then $D$ is an endvertex and $CD$ is good to $D$. If not then there exists an interval $Dy$ such that $Dy \supset DC$ but $CD \subset Cx$ already.
Hence if at each endvertex $v$, we count the number of non-maximal intervals that are good to $v$, take the sum which we call $S$, we would have $S \geq a$ ($a$ is the number of non-maximal intervals). Consider an m-path $P$. If $P$ consists of a single vertex $p$, then there are at most $2$ non-maximal intervals connecting $p$, because otherwise we would have a non-maximal interval contained in another non-maximal interval. Thus the contribution of $P$ to $S$ is at most $2$. If $P$ has two endvertices $A,B$ then each of them has only one good interval. That is because there is a maximal interval $Ax$ already, then the good non-maximal interval $Ay$ must point to the other direction. The same for $B$. In this case, the contribution of $P$ to $S$ is also at most $2$. Thus $S \leq 2k$, hence $a \leq 2k$ as desired.
sumita
19.05.2011 12:36
Define a chain on the circle as follows: $I_{1}\subset I_{2}\subset ....\subset I_{n}$ where $I_{i}$ is an arc on circle with length $i$. Easily the number of chain is $n2^{n-2}$ Now define$ \Lambda_{1}$ the subset of chains which contains a maximal element and $\Lambda_{2}$ the subset of chains which containes a non-maximal element and no maximal element. We have $\Lambda_{1}\cap \Lambda_{2}=\emptyset$ and any two member of $\Lambda_{1}$ and $\Lambda_{2}$ are disjoint. Easily we have $|\Lambda_{1}|=m2^{n-2}$ and $|\Lambda_{2}|=a2^{n-3}$. But we have $|\Lambda_{1}|$+$|\Lambda_{2}|\leq n2^{n-2}$ which solves the problem.
trigocu
29.06.2015 01:34
"almost" should be "at most" in question.
toto1234567890
06.01.2016 15:48
Well, if you use the end points of the interval, this is easy.
sabbasi
07.02.2016 22:09
Create a multigraph $G$ on the vertices of the circle with a red edge between vertices $u$ and $v$ corresponding to a non-maximal arc, and blue edge corresponding to a maximal arc. It is not difficult to see that each vertex has red degree at most $2$ and blue degree at most $2$. Furthermore, if a vertex is adjacent to $2$ non-maximal arcs or $2$ maximal arcs, then these two arcs must be in different directions (clockwise and counterclockwise). Now let $A$ be the set of vertices with blue degree $2$, $B$ with blue degree $1$ and $C$ with blue degree $0$. Consider some arbitrary red edge between vertices $u$ and $v$. If $u,v \in A$, then there are maximal arcs going both directions (clockwise and counterclockwise) from each of $u$ and $v$, so $uv$ is contained in two maximal arcs, contradiction. Let $B' \subseteq B$ be the set of all vertices in $B$ which are connected by a red edge to a vertex in $A$. We make two claims about the vertices in $B'$ which I think are easy to prove but annoying to write down, and I can discuss them further if someone wants a proof or has a counterexample. i) Each vertex in $B'$ is connected by a red edge to at most one vertex in $A$ ii) Two vertices in $B'$ cannot be connected by a path of red edges going through vertices in $B$ So now, delete every red edge adjacent to a vertex in $C$. We will delete at most $2|C|$ edges like this. By i) and ii), it is easy to see that there are at most $|B|$ red edges adjacent to a vertex in $B$. So we get $m = |A| + \frac{|B|}{2}$ and $\frac{a}{2} \le \frac{|B|}{2} + |C|$, so $m+ \frac{a}{2} \le |A|+|B|+|C| = n$, as desired.