0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – астон вілла олоф мэллбэрг Oct 20 '16 at 3:36
1
$\begingroup$

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 don't think that there is a combinatorial standard formula for this problem, since such formulas do not take divisibility questions into account. In general problems of the above kind are solved using the euclidean algorithm for the gcd of the involved data.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.