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 \pmod 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 \pmod p$ gives the relation $p \mid (x-y)(x+y)$ and so $x \equiv y \pmod p$ or $x \equiv -y \pmod 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
$$\left\lfloor \frac{(p^2 + 1)/2}{(p + 1)/2} \right\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
$$\left\lfloor \frac{(p^2 + 1)/2}{(p + 1)/2} \right\rfloor = p,$$
what was to be shown.