-1
$\begingroup$

I want to solve the following problem:

$7x+8y+10z=38$

such that $x, y$ and $z$ are non-negative integers

and $x+y+z \le 5$

Also, if I have a starting solution of $x=2$, $y=3$, and $z=0$, is there any way to generate the other solutions?

$\endgroup$
3
  • $\begingroup$ with this small space, it's feasible to go through all possible (x,y,z) tuples and evaluate the function $f(x,y,z)=7x+8y+10z$ with all possible values x,y,z \in [0..5], given that there is only 6*6*6 different alternative parameter combinations. Once you generated the tuples, you need to filter out the tuples which do not satisfy the 2 conditions. $\endgroup$ – tp1 Jun 10 at 17:57
  • $\begingroup$ Thanks tp1. But I want to understand the solution method so that I can be able to solve large problem of such kind. Evaluating all possible values will work with such small problems but not the large ones. $\endgroup$ – user321821 Jun 10 at 18:22
  • $\begingroup$ A general algorithm is described in this answer $\endgroup$ – Bill Dubuque Jun 10 at 21:40
0
$\begingroup$

$$7x+8y+10z=38\tag{1}$$

An argument $mod$ $2$ shows that $x$ is even, then let $x=2m.$

$7x+8y+10z\equiv 38 \pmod{7} \implies y+3z\equiv 3 \pmod{7}.$
Hence let $y = -3z+7n+3.$

Substitute $x = 2m$ and $y = -3z+7n+3$ to equation $(1)$, then we get $14m-14z+56n = 14.$
Hence we get $z = m+4n-1.$

Finally, we get $(x,y,z)=(2m, -3m-5n+6, m+4n-1).$
$m,n$ are integers. $y$ is non negative if $3m+5n \le 6.$

Thus, solutions corresponding to $(m,n)=(0,1),(1,0),(2,0)$ are $(x,y,z)=(0, 1, 3),(2, 3, 0),(4, 0, 1).\\$

Another approach:
An argument mod 2 shows that $x$ is even, then $x$ must be $0 , 2$ or $4.$

$\bullet\ \pmb{x=0}:$

$7x+8y+10z=38 \implies 8y+10z=38.$

$8y+10z\equiv 38 \pmod{5} \implies y\equiv 1 \pmod{5}.$

Hence we get $y=1$ and $z=3.$

$\bullet\ \pmb{x=2}:$

$7x+8y+10z=38 \implies 8y+10z=24.$

$8y+10z\equiv 24 \pmod{5} \implies y\equiv 3 \pmod{5}.$

Hence we get $y=3$ and $z=0.$

$\bullet\ \pmb{x=4}:$

$7x+8y+10z=38 \implies 8y+10z=10.$

$8y+10z\equiv 10 \pmod{5} \implies y\equiv 0 \pmod{5}.$

Hence we get $y=0$ and $z=1.$

$\endgroup$
2
  • $\begingroup$ Thanks Tomita. Is there any way to know if we have a unique solution or no solutions at all? $\endgroup$ – user321821 Jun 11 at 14:37
  • $\begingroup$ If you're just looking for the solution, the easiest way is brute force search: $0\le(x,y,z)\le5.$ $\endgroup$ – Tomita Jun 11 at 23:19

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