1979_Question_3

Re-order the set so that a_1\leq a_2\leq ...\leq a_n
There are \binom{n}{2} unique a_i-a_j for i>j and since all a_k are odd, these differences are all even.

a_r=a_1+(a_2-a_1)+(a_3-a_2)+...+(a_{r}-a_{r-1})
Let a_m-a_{m-1}=d_{m-1}
a_r=a_1+d_1+d_2+...+d_{r-1}
We know that d_1,d_2,...,d_{r-1} are all even and all different \therefore the smallest d_1+d_2+...+d_{r-1} is the sum of the first (r-1) even numbers.
\Rightarrow \sum_{i=1}^{r-1}d_{r}\geq 2+4+...+2(r-1)
\qquad \qquad \; \; \; \;=2(1+2+...+(r-1))=2(\frac{1}{2}r(r-1))
\qquad \qquad \; \; \; \;=r(r-1)

\therefore a_r\geq a_1 + r(r-1)

We also know that a_1 is the smallest integer in the set \therefore a_1\geq 1
\Rightarrow a_r\geq 1+r(r-1)

Hence, \sum_{i=1}^{n}a_i\geq 1+r(r-1)
\qquad \; \; \; \; \; \qquad \; \; \; \;=\sum_{i=1}^{n}1 +\sum_{i=1}^{n}r^2 - \sum_{i=1}^{n} r
\qquad \; \; \; \; \; \qquad \; \; \; \;=n+\frac{1}{6}n(n+1)(2n+1)-\frac{1}{2}n(n+1)
\qquad \; \; \; \; \; \qquad \; \; \; \;=\frac{n}{6} ( 6+(n+1)(2n+1)-3(n+1))
\qquad \; \; \; \; \; \qquad \; \; \; \;=\frac{n}{6}(2n^2+4)
\qquad \; \; \; \; \; \qquad \; \; \; \;=\frac{n}{3}(n^2+2) as required

1 Like