FI-MO 2005 Problem 5

A finite sequence is said to be disorderly, if no two terms of the sequence have their average in between them. For example, $(0, 2, 1)$ is disorderly, for $1 = \frac{0+2}{2}$ is not in between $0$ and $2$ , and the other averages $\frac{0+1}{2} = \frac{1}{2}$ and $\frac{2+1}{2} = 1\frac{1}{2}$ do not even occur in the sequence. Prove that for every $n \in \Bbb{N}$ there is a disorderly sequence enumerating the numbers $0, 1,\ldots , n$ without repetitions.