How to prove that $\limsup_{n\to\infty}n M_n\geq \frac{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$?
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&gt;0$. 

Then there exist an integer $N$ such that for each $l,l-1&gt;N$, then 

$|C_{n,l}|=|s_l-s_{l-1}|&lt;|C_{n,0}|$

So 

$|M_n|=max\{|C_{n,k}|: k&lt;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&lt;\frac{1}{ln(2)}$
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&gt;0$. 

Then there exist an integer $N$ such that for each $l,l-1&gt;N$, then 

$|C_{n,l}|=|s_l-s_{l-1}|&lt;|C_{n,0}|$

So 

$|M_n|=max\{|C_{n,k}|: k&lt;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&lt;\frac{1}{ln(2)}$