This is killed by the known fact that a positive integer can be expressed as a sum of three squares if and only if it is not of the form $4^k(8\ell + 7)$. See e.g. http://www.proofwiki.org/wiki/Integer_as_Sum_of_Three_Squares. Then either $m=1$ or $m=2$ (or both) work.

I think this is too large a note, they can have not enough change at the olympiad. The problem is indeed far simpler. First we should find any integral $y_1$, $y_2$, $y_3$, not all zeroes, such that $p$ divides $y_1^2+y_2^2+y_3^2$. In fact, we can take $y_3=1$; then one of $(p+1)/2$ possible residues of $y_1^2$ coincides with one of $(p+1)/2$ possible residues of $-1-y_2^2$. Now each $y_i$ can be replaced by $x_i= y_i\pmod p$ so that $|x_i|<p/2$. These $x_i$ satisfy the condition.

teps wrote: Prove that for all odd prime numbers $p$ there exist a natural number $m<p$ and integers $x_1, x_2, x_3$ such that: \[mp=x_1^2+x_2^2+x_3^2.\] We prove that for all odd prime bumbers $p$ there exist a natural number $m<p$ and integers $x,y$ such that: $x^{2}+y^{2}+1=mp$ Proof: Case1. If $p=4k+1$.So there exists an integer $|x|<p$, such that $p|x^{2}+1$.We will take $y=o$. So $x^{2}+1=mp$ and $x^{2}+1<p^{2} => o<m<p $ Case2. If $p=4k+3$ So $(\frac{-1}{p})=-1$. Let k-integer, such that $(\frac{k}{p})=1$ and $(\frac{k+1}{p})=-1$. So $(\frac{-k-1}{p})=1$. Let $y^{2}\equiv\ k(\bmod p)$ and $x^{2}\equiv\ -(k+1)(\bmod p) => x^{2}+y^{2}+1=mp$ We take integers $x,y$ such that $0<x,y<\frac{p-1}{2} => 0<m<p$

Alternative solution: First we prove that we can always choose $x_i\le \frac{p-1}{2}$, thus we can always have $\sum{x_i}\le \frac{3}{4}(p-1)^2< p(p-1).$ Plugging in $x_3=0$ we get that $mp=x_1^2+x_2^2$, thus $\left(\frac{-1}{p}\right)=1.$, which means that for every $p=4k+1$ there exists such $m$. Now for the case $p=4k+3$, we can plug $x_3=1$, and so we have to prove that there always exist $x_1, x_2$ such that $x_1^2+x_2^2\equiv -1 \pmod{p}$. Lets assume otherwise. We know that if $k$ is quadratic residue, then $-k$ is a quadratic nonresidue. We know that $1$ is a quadratic residue (modulo every prime), thus $-2$ cannot be, then $2$ has to be q.r., so $-3$ cannot be q.r., so $3$ has to be q.r., ...$\frac{p-1}{2}$ has to be q.r. So if we don't arrive at a contradiction by now, we can take $x_1^2\equiv x_2^2\equiv \frac{p-1}{2}$, thus $x_1^2+x_2^2\equiv p-1\equiv -1\pmod{p}$. $\blacksquare$

It is straight forward from Cauchy Davenport .Isn't it.Obviously $\frac{3p-1}{2}$ is bigger than p and so all residues mod $p$ can be written as sum of squares of $x_{i}^2$ for $i=1,2,3$ choosing all posibilities.So 0 is also there .Now it remains to prove $m<p$. See we can choose $x_{i} \leq \frac {p-1}{2}$. So sum of their squares is less than $p^2$ and so obviously $m<p$.

These overly complex solutions make me sad Here is an extremely elementary solution, requiring only the knowledge that there are $\frac{p+1}{2}$ squares modulo $p$ which is not even hard to prove. First, I claim there exist integers $x,y$ such that $1^2 + x^2 + y^2 \equiv 0 \pmod{p}$. This is clearly true, as let $Q$ be the set of squares modulo $p$. Then $|Q| = |-1 - Q| = \frac{p+1}{2}$, hence as $Q, -1-Q \subset \mathbb{Z}_p$ which has cardinality $p < 2 \left ( \frac{p+1}{2} \right )$ it follows $Q \cap (-1-Q) \neq \emptyset$. Therefore there exists some $x,y$ such that $x^2 \equiv -1 - y^2 \pmod{p} \implies x^2 + y^2 + 1 \equiv 0 \pmod{p}$. Now note that we can restrict $0 \le x,y < p$. Furthermore we can restrict $0 \le x,y < \frac{p}{2}$ because of the fact $x^2 \equiv (p-x)^2 \pmod{p}$ for all $x$. But then $1 + x^2 + y^2 < \frac{p^2}{2} + 1$. Hence if we let $1 + x^2 + y^2 = mp$, then $m < \frac{p}{2}$ and the result follows.