Set Average

Relevant wiki: Extremal Principle - Problem Solving

Let $S = \{a_k\}_0^N$ , where $a_k \in \mathbb Z$ , $a_0 = 0$ is the minimum and $a_N=2015$ is the maximum. Then the average of elements of $S$ is given by $\overline{a_k} = \dfrac { \sum_{k=1}^N a_k}N$ . Since two elements 0 and 2015 are already fixed, we can find the minimum $\overline{a_k}$ by including some $n$ smallest elements from 1, 2, 3, ... to then take the average by dividing the sum by $n+2$ . Then $\overline{a_k}$ is given by:

$\begin{aligned} \overline{a_k} & = \frac {\sum_{k=1}^n k + 2015}{n+2} \\ & = \frac {\frac 12n(n+1)+2015}{n+2} \\ & = \frac 12 \left(\frac {n(n+1)+4030}{n+2}\right) \\ & = \frac 12 \left(\frac {n(n+2)-n-2+4032}{n+2}\right) \\ & = \frac 12 \left(n-1+\frac {4032}{n+2}\right) \\ & = \frac 12 \left({\color{#3D99F6}n+2+\frac {4032}{n+2}}-3\right) & \small \color{#3D99F6} \text{By AM-GM inequality: } n+2+\frac {4032}{n+2} \ge 2 \sqrt{4032} \\ & \ge 61.99803147 & \small \color{#3D99F6} \text{Equality occurs when: }n \approx 61.5 \end{aligned}$

Upon checking, we find that $\overline{a_k}_{min} = \boxed{62}$ , when $n=61, 62$ .

The trick is to add the smallest possible integers (i.e. 1, 2, 3, etc.) as long as the number added is less than the current average.

If we add the integers up to $n$ , we end up with $n + 2$ elements in the set, with a total of $1 + 2 + \cdots + n + 2015 = \tfrac12n(n+1)+2015.$ One way to approach this problem is by solving the quadratic equation $\text{average} = \frac{\tfrac12n(n+1)+2015}{n+2} = n,$ but I will pursue a method of successive approximation.

If we take $n = 0$ (so that the set only contains two integers) the average is obviously equal to $2015/2 = 1007\tfrac12$ . Adding all integers up to $n = 1007$ gives the next approximation: an average of $509\,543/1010 = 504.998$ . Therefore we try the next approximation with $n = 505$ , and so on. The table shows the successive steps:

$\begin{array}{r|r|r} n & \text{sum} & \text{average} \\ \hline 0 & 2017 & 1008.50 \\ 1007 & 509\,543 & 504.99 \\ 504 & 129\,275 & 255.48 \\ 255 & 34\,655 & 134.84 \\ 134 & 11\,060 & 81.32 \\ 81 & 5\,336 & 64.29 \\ 64 & 4\,095 & 62.05 \\ 62 & 3\,095 & 62.00 \\ \hline \end{array}$

Thus the average is exactly $\boxed{62}$ , for the set $\{0,1,2,\dots,61,62,2015\}$ . Of course, removing 62 from the set would not affect the average.