Consider the following optimization problem:

**Problem:** find a monic polynomial $p(x)$ of degree $n$ which minimizes $\max_{x \in [-1,1]} |p(x)|$. 

The solution is given by Chebyshev polynomials:

**Theorem:** Let $T_n(x) = cos (n \cdot cos^{-1} x)$. Then $(1/2^{n-1}) T_n$ is a monic polynomial of degree $n$ which achieves the above minimum.

The proof of this fact is short and surprisingly free of messy calculations. From the definition of $T_n$ you derive a recurrence relation expressing $T_n$ in terms of $T_{n-1}, T_{n-2}$, which shows that $T_n$ are indeed polynomials. Then
you argue that $(1/2^{n-1}) T_n$ is monic and achieves its extrema $\pm 1/2^{n-1}$ at least $n+1$ times in $[-1,1]$, from which the above theorem easily follows. If you'd like a nice exposition of this argument which does not skip any steps,  <a href="http://www.johndcook.com/ChebyshevPolynomials.pdf">this</a> is short and clear.

However, I don't get much enlightenment from this proof: it feels pulled out of a 
hat. For example, it gives me no clue about which other polynomial optimization problems
have similar solutions. 

**My question:** Is there a natural and motivated sequence of steps which, starting from the above optimization problem, leads to Chebyshev polynomials?

**Update:** I changed the title to better reflect the question I am asking.