How to prove that $\limsup_{n\to\infty}n M_n\geq 1/\ln 2$ for the following sequence? Let $(x_i)_i$ be a sequence of distinct numbers in $[0,1]$.
Note that $[0, 1] \setminus \{x_1, \cdots, x_{n-1} \}$ can be written as a disjoint union of non-empty and non-singleton intervals $C_{n, k}$.
Let $M_n \equiv \max_k |C_{n,k}|$.
How do I prove that $\limsup\limits_{n \to \infty} n M_n\geq 1/\ln 2$?
 A: Shown by N. G. de Bruijn and P. Erdős in $1949$ (I've found it in TAoCP vol. $2$ exercise $3.5.20$).
Let $\ell_n^{(1)}\geqslant\ell_n^{(2)}\geqslant\dots\geqslant\ell_n^{(n)}$ be the lengths of the intervals (that form $[0,1]\setminus\{x_1,\dots,x_{n-1}\}$). Then (the crucial observation) for any $1<k\leqslant n$ we have $\ell_n^{(k)}\leqslant\ell_{n+1}^{(k-1)}$. By induction, for any $1\leqslant k\leqslant n$ we have $\ell_n^{(k)}\leqslant\ell_{n+k-1}^{(1)}=M_{n+k-1}$. Let $L_n=\max\{kM_k:n\leqslant k<2n\}$; then $$1=\sum_{k=1}^n\ell_n^{(k)}\leqslant\sum_{k=1}^n M_{n+k-1}\leqslant L_n\underbrace{\sum_{k=1}^n\frac1{n+k-1}}_{\to\,\ln2\text{ as }n\to\infty},$$ giving $\limsup\limits_{n\to\infty}L_n\geqslant1/\ln 2$, which implies the claimed $\limsup\limits_{n\to\infty}nM_n\geqslant1/\ln2$.
A: If the sequence is strictly increasing then the limit is always $\infty$. 
So the sequence is convergent and Cauchy.
Let $|C_{n,0}|=s_1-0=s_1>0$. 
Then there exist an integer $N$ such that for each $l,l-1>N$, then 
$|C_{n,l}|=|s_l-s_{l-1}|<|C_{n,0}|$
So 
$|M_n|=max\{|C_{n,k}|: k<N\}\geq |C_{n,0}|=s_1$ for each $n\in \mathbb{N}$
This means 
$n|M_n|\geq ns_1\to \infty$
In general I think it is not true and 
 a counter-example can be the following:
You consider the succession:
$\{1, \frac{1}{2},\frac{1}{4},\frac{3}{4}, \frac{1}{8},\frac{3}{8},\frac{5}{8}\dots\}$
You can observe that, fixed $k\in \mathbb{N}$ , for $n=k+2^k$ the set $[0,1]$ is divided into $2^k$ parts of diameter $\frac{1}{2^k}$, for example:


*

*k=0:


Then $n=1$, that means 
$[0,1]/ \{1,\frac{1}{2}\}=[0,\frac{1}{2})\cup(\frac{1}{2},1)$


*k=1:


Then $n=3$, that means 
$[0,1]/\{1,\frac{1}{2},\frac{1}{4},\frac{3}{3}\}=[0,\frac{1}{4})\cup (\frac{1}{4},\frac{1}{2})\cup (\frac{1}{2},\frac{3}{4})\cup (\frac{3}{4},1)$
Thus if you consider the subsequence 
$\{s_{k+2^k}\}_{k\in\mathbb{N}\cup\{0\}}$ 
you have 
$|C_{k+2^k, i}|=\frac{1}{2^k}$ for each $i$ so
$|M_{k+2^k}|=\frac{1}{2^k}$ 
By contradiction, if 
$\lim sup_{n\to \infty}n|M_n|\geq \frac{1}{ln(2)}$
Then each subsequence verifies that inequality, but 
$\lim sup_{k\to \infty}(k+2^k)|M_{k+2^k}|=$
$= \lim sup_{k\to \infty}\frac{(k+2^k)}{2^k}=0+1=1<\frac{1}{ln(2)}$
