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
11.05.2011 03:52
My attempt at a solution.
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.
29.06.2015 01:34
"almost" should be "at most" in question.
06.01.2016 15:48
Well, if you use the end points of the interval, this is easy.
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.