Saudi Arabian Mathematical Competitions, 2015

Notice that because $S$ is divisible by $2013$, $2014$ and $2015$, we have $S \geq 2013 \times 2014 \times 2015$.

Assume that each integer $1, 2, \ldots, 2015$ appears at most $2013$ times in the list of numbers $a_{1}, a_{2}, \ldots, a_{k}$. We have
$$2S \leq a_{1} + \cdots + a_{k} \leq 2013(1 + 2 + \cdots + 2015) < 2013 \times 2014 \times 2015,$$
which is a contradiction.

Therefore, there exists an integer $s$ which appears at least $2014$ times in the list of numbers $a_{1}, a_{2}, \ldots, a_{k}$. Put $2014$ of this number $s$ aside from the list. The sum of the remaining numbers in the list is equal to $2S - 2014s \geq 2S - 2014 \times 2015 > S$.

Start from the empty set and choose randomly $s$ integers $b_{1}, b_{2}, \ldots, b_{s}$ from the remaining numbers in the list. If there exists $1 \leq i \leq s$ such that $b_{1} + b_{2} + \cdots + b_{i}$ is divisible by $s$, put $b_{1}, b_{2}, \ldots, b_{i}$ in the set and put back the other numbers in the remaining list of numbers. If not, by the pigeonhole principle, there exist $1 \leq i < j \leq s$ such that $b_{1} + b_{2} + \cdots + b_{i} \equiv b_{1} + b_{2} + \cdots + b_{j} \pmod{s}$ and therefore $b_{i+1} + b_{i+2} + \cdots + b_{j}$ is divisible by $s$. In this case, put $b_{i+1}, b_{i+2}, \ldots, b_{j}$ in the set and put back the other numbers in the remaining list of numbers. Keep repeating this process whenever the sum of the numbers in the set is less or equal to $S - 2015s$.

Notice that each time the sum of the numbers in the set is divisible by $s$ and each time it increases by a number which is less or equal to $2015s$. Moreover, whenever the sum of the numbers in the set is less or equal to $S - 2015s$ it is always possible to choose randomly $s$ integers from the remaining numbers. Indeed, the sum of the remaining numbers is less or equal to $2S - 2014s - (S - 2015s) = S + s > 2015 \times 2015 \geq 2015s$.

Once the sum $T$ of the numbers in the set is strictly greater than $S - 2015s$, in this case we have $S \geq T > 2015s$. Because both $S$ and $T$ are divisible by $s$, we have $S - T = ms$ where $m \in \{0, 1, 2, \ldots, 2014\}$. Take $m$ from the $2014$ of the number $s$ put aside and put them in the set to obtain a sum equal to $S$.