Austrian Mathematical Olympiad

The idea is to choose from the $\frac{p^2+1}{2}$ square numbers $p$ numbers that are in the same residue class modulo $p$. Obviously, the sum of these $p$ numbers is then divisible by $p$ and thus the arithmetic mean is an integer. It is known that the square numbers do not run through all residue classes modulo $p$, but only through $1+\frac{p-1}{2}=\frac{p+1}{2}$ ones. (On the one hand, this is the residue class $0$ if one squares a number divisible by $p$. Because of $a^2\equiv (p-a{)}^2(\mathrm{mod}p)$, the squares of numbers $a$ that are not divided by $p$ run through a maximum of half of the $p-1$ nonzero residue classes. On the other hand, $x^2\equiv y^2(\mathrm{mod}p)$ gives the relation $p\mid (x-y)(x+y)$ and so $x\equiv y(\mathrm{mod}p)$ or $x\equiv -y(\mathrm{mod}p)$. Therefore, the squares of numbers $a$, which are not divisible by $p$, run through exactly half of the $p-1$ residue classes different from zero.) We now divide the $\frac{p^2+1}{2}$ square numbers into the $\frac{p+1}{2}$ residue classes that correspond to square numbers. Because of the pigeon hole principle, there is therefore a residue class, that contains at least $$\lfloor \frac{(p^2+1)/2}{(p+1)/2}\rfloor$$ numbers. Because of $$\frac{(p^2+1)/2}{(p+1)/2}=\frac{p^2+1}{p+1}=\frac{p^2+p}{p+1}-\frac{p-1}{p+1}=p-\frac{p-1}{p+1}$$ and $0<\frac{p-1}{p+1}<1$ it follows that $$\lfloor \frac{(p^2+1)/2}{(p+1)/2}\rfloor =p,$$ what was to be shown.