Singapore Mathematical Olympiad (SMO)

The minimum value $\frac{1}{2}n(n+1)$ is achieved by letting $x_k = k$ for $1 \le k \le n$. To prove the inequality, it suffices to prove that
$$x_1^3 + \cdots + x_n^3 \ge (x_1 + \cdots + x_n)^2,$$
since $x_1 + \cdots + x_n \ge 1 + 2 + \cdots + n = n(n+1)/2$.
We may assume that $x_1 < x_2 < \cdots < x_n$. Let's prove the above inequality by induction on $n$. It is clear that the inequality holds when $n=1$. Let $n>1$, and assume $x_1^3 + \cdots + x_n^3 \ge (x_1 + \cdots + x_n)^2$. Now
$$\sum_{k=1}^{n} x_k^3 - \left( \sum_{k=1}^{n} x_k \right)^2 = \left[ \sum_{k=1}^{n-1} x_k^3 - \left( \sum_{k=1}^{n-1} x_k \right)^2 \right] + x_n \left\{ x_n^2 - x_n - 2 \sum_{k=1}^{n-1} x_k \right\}.$$
The induction hypothesis implies that the first bracket on the right hand side of this equality is nonnegative.
Next observe that $x_n \ge n$. As $x_k < x_{k+1}$, we have $x_k \le x_{k+1} - 1 \le \cdots \le x_n - (n-k)$, when $1 \le k < n$. Thus the term inside the second bracket on the right hand side of this equality satisfies
$$x_n^2 - x_n - 2 \sum_{k=1}^{n-1} x_k \ge x_n^2 - x_n - 2 \sum_{k=1}^{n-1} (x_n - n + k) = x_n^2 - x_n - 2 \sum_{k=1}^{n-1} x_n + n(n-1) \\ \ge x_n^2 - x_n - 2(n-1)x_n + n(n-1) = (x_n - n + 1)(x_n - n) \ge 0$$