5
$\begingroup$

Consider $$2x+y+z=16$$ how many distinct, non-negative triples of $\lbrace{x,y,z|x,y,z\in \mathbb Z\rbrace}$ are there that satisfy the equation?

I assumed that in this question, the role of combinatorics play a vital role, so I thought of it in this order: if the triples did not have to be distinct, there would be $16$ options the first time a number is chosen, $16$ the second time a number is chosen, and $16$ the third time a number is chosen, hence there are $16^3$ permutations where repetition is allowed.

Then, when repetition is not allowed, the first time a number is chosen there $16$ options, then there are $15$ options, and then $14$, but from here not another number is chosen, so assuming there are $16!$ permutations is senseless. Therefore the remaining $13!$ permutations need to be discounted, hence there are $\displaystyle \frac{16!}{(16-3)!}$ permutations when repetition is not allowed.

So does this imply there are $3360$ possible triples? This is more or less where I encountered the flaw in my logic:

When the first number is chosen, there aren't actually $15$ remaining numbers to choose from. Because say for example you choose $y$ to be $16$, then both $x$ and $z$ must be $0$, i.e. there is actually only one choice once the first number has been chosen, and one choice once the second number has been chosen. But, what if we let $x=9$? Well, this wouldn't work at all as when $x=9$, $2x=18$, which means there are no non-negative values of $y,z$ that can satisfy the equation, hence $x$ actually has its own range; $0 \leq x \leq 8$

More or less here I kind of set aside the combinatorics approach and assumed a very basic approach: listing values. Given that $x$ has the smallest range of each of the variables, I let $x$ be the independent variable and $y,z$ be the dependant variables:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\\hline y & 0\leq y \leq 16 & 0 \leq y \leq 14 & 0 \leq y \leq 12 & 0 \leq y \leq 10 & 0 \leq y \leq 8 & 0 \leq y \leq 6 & 0 \leq y \leq 4 & 0 \leq y \leq 2 & y=0 \\\hline z & 0\leq z \leq 16 & 0 \leq z \leq 14 & 0 \leq z \leq 12 & 0 \leq z \leq 10 & 0 \leq z \leq 8 & 0 \leq z \leq 6 & 0 \leq z \leq 4 & 0 \leq z \leq 2 & z=0\\\hline T & 17 & 15 & 13 & 11 & 9 & 7 & 5 & 3 & 1\\\hline \end{array}

(Note; a prerequisite in each entry is that $y+z=16-2x$. Also; the $T$ in the bottom row signifies the total number of permutations provided all the conditions, including the prerequisite, are met)

From the table, the total number of distinct, non-negative triples of $\lbrace{x,y,z|x,y,z\in\mathbb Z\rbrace}$ that satisfy the equation $2x+y+z=16$ is a mere $81$.

From all of what you've just read, I have only two questions: the first of which is obviously is this answer correct, and the second of which is, arguably more obviously, how can what I've written be expressed mathematically provided it is correct?

Any responses are very appreciated, thank you.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Just to note that the analysis from the questioner above assumes that "distinct" means $x \ne y$, $y \ne z$, $x \ne z$, but the answers below do not assume this constraint. So the answer depends on how we interpret "distinct". $\endgroup$ – gandalf61 Oct 6 '17 at 10:12
  • $\begingroup$ @gandalf61 So would it be best to remove the misleading word "distinct" ? $\endgroup$ – Peter Oct 6 '17 at 10:14
  • $\begingroup$ I've actually adjusted my interpretation of what is meant by "distinct" given that those answering are actually more along the right lines. It is not impossible for $x=y=z$, but otherwise this means a distinct $x,y,z$ separately, whereas for one triple to be distinct from the next, only one value actually needs to differ if the remaining two are the same. So I'll keep the word there, but I'll edit the question to display the correct interpretation. @gandalf61 $\endgroup$ – joshuaheckroodt Oct 6 '17 at 10:17
3
$\begingroup$

For $x=0$ , the possible values of $y$ are $0$ to $16$, so $17$ possible values.

For $x=1$ , the possible values of $y$ are $0$ to $14$, so $15$ possible values.

$\cdots$

For $x=8$ , the possible values of $y$ are $0$ to $0$, so $1$ possible value.

In total , there are $$1+3+5+7+9+11+13+15+17=\color\red{81}$$ distinct triples.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ This is something I didn't think to consider if I'm very honest, that two of the values of the triple can be similar. I have actually been assuming that by "distinct" they mean each of the values must be different, not each of the triples themselves. Interesting, thank you. $\endgroup$ – joshuaheckroodt Oct 6 '17 at 10:06
5
$\begingroup$

we can use generating function to find the number of solution for the problem that you have stated.

That is you will have to find the coefficient of $x^{16}$ in the following products of g.f

$(1+x^2+x^4+..)(1+x+x^2+x^3+...)^2$

The number of solutions is $\boxed{81}$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Nice, does this also work for, lets say, $3x+4y+5z=91$ ? $\endgroup$ – Peter Oct 6 '17 at 10:21
  • 1
    $\begingroup$ Yes, but the generating function is $(1+x^3+x^6+...)(1+x^4+x^8+...)(1+x^5+x^{10}+...)$ and the coefficient is $x^{91}$ $\endgroup$ – Satish Ramanathan Oct 6 '17 at 10:23
5
$\begingroup$

Note that $y + z$ must be even. Hence, $y$ and $z$ are either both even or both odd.

When they are both even (say $y = 2c_1$ and $z = 2c_2$), the equation reduces to $x + c_1 + c_2 = 8$. The number of non-negative integer solutions in this case is $\binom{10}{8}$. When they are both odd (say $y = 2c_1 + 1$ and $z = 2c_2 + 1$), the equation reduces to $x + c_1 + c_2 = 7$. The number of non-negative integer solutions in this case is $\binom{9}{7}$.

Thus, we get a total of $\binom{10}{8} + \binom{9}{7} = 81$ solutions.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ How have you computed to what the equation reduces to provided both $y, z$ are odd or both $y,z$ is even? $\endgroup$ – joshuaheckroodt Oct 6 '17 at 11:05
  • 1
    $\begingroup$ @joshuaheckroodt, in the even case, you would get $2x + 2c_1 + 2c_2 = 16$ which is same as $x + c_1 + c_2 = 8$. The odd case is similar. $\endgroup$ – iamwhoiam Oct 6 '17 at 11:44
4
$\begingroup$

More generally, the equation $y+z=2n-2x$ has $2n-2x+1$ non negative solutions for all $x=0,1,\dots, n$. Therefore the number of non negative solutions is $\sum_{x=0}^n(2n+1-2x)$, that is the sum of all odd numbers in the interval $[1,2n+1]$ which is equal to $(n+1)^2$.

|cite|improve this answer
$\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.