# Finding the sum of all solutions

$2x + 3y = n$ has exactly $2011$ non-negative integral solutions. Determine the SUM of the possible values of $n$.

-
By "integral solutions", I assume you mean pairs $(x,y)\in(\Bbb Z^{\geq 0})^2$? I initially thought that you meant triples $(x,y,n)\in(\Bbb Z^{\geq 0})^3$, in which case your statement would be patently false.... – Cameron Buie Dec 20 '12 at 4:51

The integer solutions to $2x+3y=1$ are given by

\left\{\begin{align*} &x=-1+3k\\ &y=1-2k \end{align*}\right.

for $k\in\Bbb Z$, so the integer solutions to $2x+3y=n$ are given by

\left\{\begin{align*} &x=-n+3k\\ &y=n-2k \end{align*}\right.

for $k\in\Bbb Z$. Clearly $n>0$, so $x\ge 0$ iff $3k\ge n$ iff $k\ge\frac{n}3$, and $y\ge 0$ iff $2k\le n$ iff $k\le\frac{n}2$. Thus, for a given $n>0$ you get one solution to $2x+3y=n$ in non-negative integers for each integer $k$ satisfying $$\frac{n}3\le k\le\frac{n}2\;.\tag{1}$$

$(1)$ is equivalent to $$\left\lceil\frac{n}3\right\rceil\le k\le\left\lfloor\frac{n}2\right\rfloor\;,$$

so there are $\left\lfloor\frac{n}2\right\rfloor-\left\lceil\frac{n}3\right\rceil+1$ solutions. Thus, you’re looking for the sum of all positive integers $n$ such that

$$\left\lfloor\frac{n}2\right\rfloor-\left\lceil\frac{n}3\right\rceil+1=2011$$ or, equivalently,

$$f(n)\triangleq\left\lfloor\frac{n}2\right\rfloor-\left\lceil\frac{n}3\right\rceil=2010\;.$$

Clearly $$f(n)\approx\frac{n}2-\frac{n}3=\frac{n}6\;,$$ so the desired values of $n$ will be near $6\cdot2010=12060$. One of these values is $12060$, since $f(12060)=6030-4020=2010$. Now note that

\begin{align*} f(k+6)&=\left\lfloor\frac{k+6}2\right\rfloor-\left\lceil\frac{k+6}3\right\rceil\\ &=\left(\left\lfloor\frac{k}2\right\rfloor+3\right)-\left(\left\lceil\frac{k}3\right\rceil+2\right)\\ &=\left\lfloor\frac{k}2\right\rfloor-\left\lceil\frac{k}3\right\rceil+1\\ &=f(k)+1 \end{align*}

for all $k$, so each arithmetic progression with constant difference $6$ contains exactly one term $n$ such that $f(n)=2010$, and there are therefore exactly $6$ such values of $n$. From here you should have no trouble finding the $6$ values of $n$ such that $f(n)=2010$ and their sum.

-

Let us verify for $n=m[2,3]+k$ where $0\le k<[2,3]$

If $k=0\implies 2x+3y=6m\implies 3(2m-y)=2x,$ so $y$ must even $=2z$(say), So, $x=3(m-z)\implies 0\le z\le m$ so $z$(hence $y$) can assume $m+1$ values in non-negative integers.

If $k=1\implies 2x+3y=6m+1\implies 3(y-2m)+1=2x,$ so $y$ must odd $=2z+1$(say), where $z\ge 0$ So, $x+1=3(m-z)\implies (m-z)\ge 1\implies 0\le z\le m-1$ so $z$(hence $y$) can assume $m$ values in non-negative integers. $\implies n=6(m+1)+1=6m+7$ will have $m+1$ solutions in non-negative integers.

So, we observe that $6m,6m+2,6m+3,6m+4,6m+5,6m+7$ will have $m+1$ solutions in non-negative integers.

-
A big hint for what looks like homework, but well done. +1 – Ross Millikan Dec 20 '12 at 5:42
This doesn’t work: for $n=2m=4020$, for example, there are only $671$ solutions, not $2011$. – Brian M. Scott Dec 20 '12 at 6:17

Hint: if $n$ is odd, one solution will have $y=1, x=\frac {n-3}2$ Others will differ by adding $2$ to $y$ and deducting $3$ from $x$ a number of times-what is the maximum number of times allowed? If $n$ is even, what is the base solution?

-