Here is a "proof by physics":
The average of $a_1, \dots, a_n$ is the center of mass of $n$ point masses, each with unit mass, having positions (along the $x$-axis) given by their values, i.e. $a_i$ has mass 1 and position $x = a_i$.
Given $(n+1)$ unit point masses, $a_1 \leq \dots \leq a_{n+1}$, let $u_n$ be the center of mass of the first $n$ points. The center of mass $u_{n+1}$ can be computed by replacing the first $n$ points by a mass of $n$ with position $u_{n}$. Since $a_{n+1} \geq a_n \geq u_n$, the addition of $a_{n+1}$ to the system shifts the center of mass to the right. Hence, $u_{n+1} \geq u_n$.
On the other hand, if $n$ points of unit mass are distributed evenly along the $x$-axis, it is easy to see that the addition of a unit mass at a position to the right of $u_n$ but to the left of $a_n$ will shift the center of the mass to the right (even though the position of the additional mass is to the left of $a_n$). Hence, the converse is false.