1
$\begingroup$

Find Number of Non negative integer solutions of $x+2y+5z=100$

My attempt:

we have $x+2y=100-5z$

Considering the polynomial $$f(u)=(1-u)^{-1}\times (1-u^2)^{-1}$$

$\implies$

$$f(u)=\frac{1}{(1-u)(1+u)}\times \frac{1}{1-u}=\frac{1}{2} \left(\frac{1}{1-u}+\frac{1}{1+u}\right)\frac{1}{1-u}=\frac{1}{2}\left((1-u)^{-2}+(1-u^2)^{-1}\right)$$

we need to collect coefficient of $100-5z$ in the above given by

$$C(z)=\frac{1}{2} \left((101-5z)+odd(z)\right)$$

Total number of solutions is

$$S(z)=\frac{1}{2} \sum_{z=0}^{20} 101-5z+\frac{1}{2} \sum_{z \in odd}1$$

$$S(z)=540.5$$

what went wrong in my analysis?

$\endgroup$
  • $\begingroup$ I probably do understand your attempt, which is a nice method, but I'm not sure 100% I do. Could you please write more details and explain it better? $\endgroup$ – user126154 Nov 26 '18 at 15:14
  • 1
    $\begingroup$ You get an extra coefficient of $1$ from the $(1-u^2)^{-1}$ term if $100-5z$ is even, which is when $z$ is even. So the final term in your sum should be $\frac{1}{2}\sum_{z \in even}1$ over $z=0$ to $z=20$ which gives you an extra $0.5$ and a final answer of $541$. $\endgroup$ – gandalf61 Nov 26 '18 at 15:55
2
$\begingroup$

An alternative way.

Given $x+2y+5z=100$ and it is clear that $0\le z\le20$.

For any possible values of $z$, $x+2y=100-5z$.

Let us take $p=100-5z\ge0$. Solving the equation $x+2y=p$, $(-p,p)$ is a solution. The general solution of $(x,y)$ is $$x=-p+2q,\ \ y=p-q,\ \ q\in\mathbb{Z}$$

If $p=2k$, then $k=\dfrac p2\le q\le p=2k$.

So, there are $k+1=\dfrac p2+1$ solutions for $(x,y)$

So, we have the following numbers as follows $$p=100,95,90,85,80,75,......,15,10,5,0$$and$$k+1=51,48,46,43,41,38,......,8,6,3,1$$

The total number of solutions are $$4(10+20+30+40)+5(8+6+3+1)+51=541$$

$\endgroup$
  • $\begingroup$ ok nice what is the mistake in my solution $\endgroup$ – Umesh shankar Nov 26 '18 at 15:27
  • $\begingroup$ @keyflex, I don't know why my answer is different from yours. $\endgroup$ – xpaul Nov 26 '18 at 16:05
2
$\begingroup$

I will find number of solutions of equation $5x+2y+z=10 n$ in general:

clearly the positive solutions $x_0, y_0, z_0$ of this equation are corespondent to the solution $x_0+2,y_0, z_0$ of equation $5x+2y+z=10(n+1)$.Clearly for $x=>2$, finding the solutions of $5x+2y+z=10(n+1)$ will lead to finding the solution of first equation,provided we consider $x-2$ in first equation.
If the number of solutions of equation $5x+2y+z=10(n+1)$ is $\phi(n+1)$ and that of equation $5x+2y+z=10n$ is $\phi(n)$ the difference of $\phi(n+1)$ and $\phi(n)$ is equal to the number of solutions of equation $5x+2y+z=10(n+1)$ for $x=0$ and $x=1$. But this equation has $5n+6$ solutions for $x=0$, (i.e. $0=<y=<5n+5)$ and it has $5n+3$ solutions for $x=1$, (i.e $0=<y=<5n+2)$. Therefore we have:

$\phi(n+1)-\phi(n)=10n+9$

We can also search and find that $\phi(1)=10$, so we can write:

$\phi(1)=10$

$\phi(2)-\phi(1)=10\times 1+9$

$\phi(3)-\phi(2)=10\times 2+9$ .

.

.

$\phi(n)-\phi(n-1)=10(n-1)+9$

Summing theses relations gives:

$\phi(n)=5n^2 +4n +1$

In your question $n=10$, therefore number of solutions is $\phi(10)=5.10^2+4.10+1=541$

$\endgroup$
1
$\begingroup$

Note that the number of non-negative integer solutions of the following equation $$ x+y=n $$ is $n+1$. Here $n$ is a non-negative integer. Clearly $5|(x+2y)$. Let $$x+2y=5k\tag{1}$$ where $0\le k\le 20$. For (1), if $k$ is odd, then so is $x$, and if $k$ is even, then so is $x$.

Case 1: $k$ is odd. Let $k=2n-1$ and $x=2m-1$. Then $1\le n\le 10$ and (1) becomes $$ m+y=5n-2 $$ whose number of non-negative integer solutions is $5n-1$.

Case 2: $k$ is even. Let $k=2n$ and $x=2m$. Then $0\le n\le 10$ and (1) becomes $$ m+y=5n $$ whose number of non-negative integer solutions is $5n+1$.

Thus the number of non-negative integer solutions is $$ \sum_{n=1}^{10}(5n-1)+\sum_{n=0}^{10}(5n+1)=551 $$

$\endgroup$
1
$\begingroup$

Given: $x+2y=100-5z$, tabulate: $$\begin{array}{c|c|c} z&x&\text{count}\\ \hline 0&100,98,\cdots, 0&\color{red}{51}\\ 1&\ \ 95,93,\cdots, 1&\color{blue}{48}\\ 2&\ \ 90,88,\cdots, 0&\color{red}{46}\\ 3&\ \ 85,83,\cdots, 1&\color{blue}{43}\\ 4&\ \ 80,78,\cdots, 0&\color{red}{41}\\ \vdots&\vdots&\vdots\\ 17&15,13,\cdots,1&\color{blue}{8}\\ 18&10,8,\cdots,0&\color{red}{6}\\ 19&5,3,1&\color{blue}{3}\\ 20&0&\color{red}{1}\\ \hline &&\color{red}{286}+\color{blue}{255}=541 \end{array}$$

$\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.