Find the minimum value of $x^2+y^2$, where $x,y$ are non-negative integers and $x+y$ is a given positive odd integer Let $k$ be a fixed positive odd integer. Find the minimum value of $x^2+y^2$, where $x,y$ are non-negative integers and $x+y=k$  
My approaches:


*

*Since $k$ is odd, $x$ and $y$ have different parity. I consider, $k=2m+1$, so that $x+y=2m+1$.
I also consider $x$ to be even and $y$ to be odd.
So, $2p+2q+1=2m+1$.
Also, $4p^2+4q^2+4q+1+8pq+4p=4m^2+4m+1$  which apparently doesn't lead me anywhere. 

*$x+y=k$. Then 
$x^2+y^2+2xy=k^2$.
Now I am stuck!
Please help!
 A: Since
$$
x^2+y^2=\frac12\left((x+y)^2+(x-y)^2\right)
$$
the minimum comes when $|x-y|$ is smallest, that is $1$ if $x+y$ is odd. Thus, the minimum is
$$
\frac12\left((x+y)^2+1\right)
$$
A: Assume wlog that $x < y$ (they cannot be equal since $k$ is odd). Let's compare $x^2 + y^2$ to $(x + 1)^2 + (y-1)^2$.
$$
(x + 1)^2 + (y-1)^2  - (x^2 + y^2) =  2x  -2y+ 2
$$
Since $x < y$, the result is non-positive, and as long as $x \neq y-1$, it is strictly negative, mening the net value has decreased. So as long as $x \neq y - 1$, you can do strictly better by increasing $x$ and decreasing $y$. Therefore $x = y - 1$ (or $x = y + 1$) is the optimal value for minimizing the sum of the squares.
A: Starting with $x<y$ and $y\neq x+1$ then $\left(x+1\right)^{2}+\left(y-1\right)^{2}<x^{2}+y^{2}$ so then pair
$\left(x,y\right)$ will not provide the minimal value (pair $\left(x+1,y-1\right)$ does 'better'). This shows
that we need $y=x+1$.
If $k=2n+1$ then $x=n$ and $y=n+1$ give the minimum value $n^{2}+\left(n+1\right)^{2}=\frac{1}{2}\left(k^{2}+1\right)$
In situations like this it is a good habit to pick out a 'small' one (p.e. $k=7$)  and to investigate the candidates $0+7$, $1+6$,... et cetera. Patterns show up that are useful.
