# Find the number of nonnegative solutions to the equation 6x+8y=500 using combinatorics.

I've been trying to think of a way to solve this problem besides graphing and just to generalize problems of the form ax+by=c using combinatorics. I've thought of using stars and bars method, which led me to this exchange, but the process described here got me an answer of 10 rather than 21, the correct answer. Anyone know anyway to modify this process?

• Can't you just do this normally? Like all solutions are given by $(2 + 4t, 61-3t)$, and $t$ can have only $21$ values, $0 , 1, ..., 20$? – астон вілла олоф мэллбэрг Oct 20 '16 at 3:36

We have to solve $3x+4y=250$ in nonnegative integers. This implies that $250-3x$ should be $\geq0$ and divisible by $4$. The smallest $x\geq0$ that does the trick is $x=2$. If $x'$ is another admissible value then $3(x-x')+4(y-y)=0$, hence $x-x'$ has to be a multiple of $4$. It follows that all admissible $x$ are of the form $$x=2+4k\qquad(k\geq0)\ .$$ The condition $3(2+4k)=3x\leq250$ leads to $12k\leq244$, hence $k\leq20$. It follows that there are $21$ solutions in total.
I think I did this correctly using a "balls in boxes" approach. So, $6x+8y=500$ can be simplified to $3x+4y=250$. Then $x+x+x+y+y+y+y=250$. So there are 7 boxes into which I would like to put 250 balls, but there is the constraint that all boxes labeled $x$ (and $y$) must receive the same number of balls. So, no more than $250/3$ balls may go into each of the $x$ boxes, which means no more than 83 balls into each $x$ box. But if you put 83 balls into each $x$ box, that leaves only 1 ball to be put in all four $y$ boxes... obviously we can't have that. So no more than 82 balls may be put into each $x$ box. We need to reduce by 4 with each step so that each $y$ box receives the same number of balls. Hence, the number of nonnegative solutions to your equation is the number of positive integers $k$ such that $82-4k$ is nonnegative.