The size of a set of closed intervals with integer endpoints, which are either disjoint or nested Let $n>1$ be an integer. Let $M$ be a set of closed intervals. Suppose that the endpoints $u$ and $v$ of each interval $[u,v] \in M$ are natural numbers satisfying $1\le u < v \le n$  and moreover, for any two "distinct" intervals $I, I' \in M$, one of the following possibilities occurs: $I \cap I' = \emptyset$ or $I \subset I'$ or vice versa. Prove that 
$$|M| \le n-1$$ 
Source:  Problem 1.3.2 in Invitation to Discrete Mathematics (2nd Ed.) by Matoušek and Nešetřil.
 A: By strong induction on $n$. Consider the maximal intervals, call the size of the interval $[a,b]$(which is $b-a+1$) the number of integers in $[a,b]$.  If there are $k$ such intervals they split the numbers into $k,k+1$ or $k+2$  independent zones with sizes $a_1,a_2\dots a_k$ (The best case is when it splits into $k$ zones). such that $a_1+a_2+\dots a_k\leq n$. By the induction hypothesis there can be at most $a_i-2$ in each interval(because the maximal interval has already been taken), so the maximum sum possible is $n-2k$ which is maximized when $k$ is $1$: The max is achieved when the intervals form a chain under inclusion.
This problem reminded me of the rainbow bird from Iran problem
A: Consider the set family $M=\{[k,n]\}_{k=1}^{n-1}$. $M$ is a set family with $n-1$ sets and satisfies your set relations: it has the intersection property because it is a nested set family. Now any other interval of the form $[u,v]$ with $v\ne n$ will intersect non trivially with $[u+1,n]$ and not be a proper subset. So $[u,v]\not\in M$. Thus the bound is sharp.
