Czech and Slovak Mathematical Olympiad

Let $s$ be the sum, $n$ the number and $p$ the integer part of the mean of the numbers on the board. Then we can write
$$\frac{s}{n} = p + \frac{2{,}016}{10{,}000} = p + \frac{126}{625},$$
which gives
$$625(s - pn) = 126n.$$
Numbers $126$ and $625$ are coprime, thus $625 \mid n$. Therefore $n \ge 625$.
The numbers on the board are different, that is
$$p = \frac{s}{n} - \frac{126}{625} \ge \frac{1+2+\cdots+n}{n} - \frac{126}{625} = \frac{n(n+1)}{2n} - \frac{126}{625} = \frac{n+1}{2} - \frac{126}{625} \ge \frac{625+1}{2} - \frac{126}{625} > 312.$$
The integer $p$ is thus at least $313$ and the value of the mean at least $313{,}2016$.
This value can be attained by numbers $1, 2, \ldots, 624$ and $751$. We get
$$\frac{1+2+\cdots+624+751}{625} = \frac{312 \cdot 625 + 751}{625} = 313 + \frac{126}{625} = 313{,}2016.$$