22
$\begingroup$

How can I find the number of integral solution to the equation

$|x | + | y | + | z | = 10.$

I am using the formula,

Number of integral solutions for $|x| +|y| +|z| = p$ is $(4P^2) +2 $, So the answer is 402.

But, I want to know, How we can find it without using formula.

any suggestion !!!

Please help

  • 0
    yes !!! sir... any help will be appreciate...2012-10-28

8 Answers 8

36

The number $n_1(k)$ of solutions of $|x|=k$ is quite obviously given by $n_1(k)=\begin{cases}2&\text{if }k>0\\1&\text{if }k=0\\0&\text{if }k<0.\end {cases}$ Then the number of solutions $n_2(k)$ of $|x|+|y|=k$ can by obtained as $n_2(k)=\sum_{i\in\mathbb Z}n_1(i)\cdot n_1(k-i)=\begin{cases}2+(k-1)\cdot 4+2=4k& \text{if }k>0\\1&\text{if }k=0\\0&\text{if }k<0.\end{cases}$ Finally, the number $n_3(k)$ of solutions of $|x|+|y|+|z|=k$ is (using $\sum_{i=1}^n i=\frac{n(n+1)}2$) $n_3(k)=\sum_{i\in\mathbb Z}n_2(i)\cdot n_1(k-i)\\=\begin{cases}2+2\sum_{i=1}^{k-1}4i + 4k=2+4k(k-1)+4k=4k^2+2& \text{if }k>0\\1&\text{if }k=0\\0&\text{if }k<0.\end{cases}$


In general, the number of solutions of $|x_1|+\cdots +|x_m|=k$ is given by $n_m(k)=\begin{cases}P_m(k)&\text{if }k>0\\1&\text{if }k=0\\0&\text{if }k<0,\end{cases}$ where $P_m$ is some polynomial of degree $m-1$. The $P_m$ can be obtained recursively, e.g. via the relations $P_m(X+1)-P_m(X)= P_{m-1}(X)+P_{m-1}(X+1)$ $P_m(1)=2m$

  • 0
    @bodacydo please have a look at : http://en.wikipedia.org/wiki/Convolution2012-10-30
5

I give a geometric derivation, we want to count all integral points lying on surface $|x|+|y|+|z|=P$. Actually in 3D space, in every octant, the shape of surface is triangle shape.

For example, if $P=4$, then the shape in the first octant would be $ \begin{array}[ccccccccc] \ & & & &Q(0,0,4)& & & &\\ & & &D(0,1,3))& &D(1,0,3)& & &\\ & &D(0,2,2)& &S(1,1,2)& &D(2,0,2)& &\\ &D(0,3,1)& &S(1,2,1)& &S(2,1,1)& &D(3,0,1)&\\ Q(0,4,0)& &D(1,3,0)& &D(2,2,0)& &D(3,1,0)& &Q(4,0,0)\\ \end{array} $ where $Q$ denotes the points that should be shared by 4 octants, $D$ denotes the points that should be shared by 2 octants and $S$ denotes the points belongs only to this octants.

So for the total octants, the number of points with S is $n_S=8\cdot\frac{(P-1)(P-2)}{2}=4P^2-12P+8$

the number of points with D is $n_D=8\cdot\frac{3(P-1)}{2}=12P-12$

the number of points with Q is $n_Q=8\cdot\frac{3}{4}=6$

So the total number would be $n=n_S+n_D+n_Q=4P^2+2$

5

I'll give an argument for computing the number of integer solutions of $\sum_{i=1}^n|x_i|=k$ for any $n,k\in\Bbb N$, then specialize it for $n=3$.

First the number of solutions of $\sum_{i=1}^nx_i=k$ with all $x_i\geq0$ is $\binom{k+n-1}{n-1}$: first draw $k+n-1$ vertical strokes, then for $n-1$ of them cross them with a horizontal stroke, turning them into $+$ signs, to obtain a decomposition $x_1+x_2+\cdots+x_n$ of $k$ with each of the $x_i$ in unary notation (possibly with no strokes at all, representing $0$).

This counts the purely non-negative solutions to the original problem. To include solutions where $x_i<0$ for some $i$, we record the subset of the positions $i$ where this happens, and then replace each such negative $x_i$ by $-1-x_i$, making it non-negative. The result is a solution to the non-negative problem above, but with $k$ diminished by the number of originally negative $x_i$ (because of the term $-1$ used for each one). Thus we get the number $ \sum_{j=0}^n\binom nj\binom{k+n-1-j}{n-1} $ of solutions to $\sum_{i=1}^n|x_i|=k$, where the binomial coefficient on the left counts the subsets of negative entries, and the one on the right counts the number of solutions of the corresponding non-negative problem. This summation does not appear to be of the type that can be reduced to a single binomial coefficient (as it would if the sum were alternating).

For $n=3$ one gets $\sum_{j=0}^3\binom3j\binom{k+2-j}2$, which gives concretely $ \frac{(k+2)(k+1)+3(k+1)k+3k(k-1)+(k-1)(k-2)}2 =4k^2+2. $

4

This is very similar to Marc's answer, but since I was deriving it when he posted, I decided to keep going and post it anyway.

First count the number of solution to $ x+y+z=k, x,y,z\geq 1. $ By usual bars and stars argument, this is ${k-1\choose 2}$. Now by symetry, each of these solution is in fact $2^3$ solution allowing $\pm j$ in each variable.

Now count the number of solution to $ x+y+z=k, $ where exactly one of the variable is $0$. Using similar techniques and symetry arguments, on gets $ {3\choose 1}{k-1\choose 1}2^2. $

Finally the number of solution to $ x+y+z=k, $ where exactly $2$ are $0$ is given by $6$, for you have $3$ choices for the non-zero variable and $2$ choices for its sign.

This give

$ \sum_{i=0}^{2}{3\choose i}{k-1\choose 2-i}2^{3-i}=4k^2+2 $

This generalized to $ \sum_{i=0}^{n-1}{n\choose i}{k-1\choose n-1-i}2^{n-i}; $

1

A sketch of derivation goes like this: (I did it on paper but perhaps missed some pluses or minuses). Also this approach is not a generic one.

Given the problem we know bound on each variable is $p$. Now if we assume we know $x = p$ then y and z can only be 0. If x is p-1, y and z $\in (0,1)$ which makes 4 cases (not 8 since +0 is same as -0). Similarly for x=p-2 we have y and z $\in (0,1,2)$ making 8 cases. You sum this all till you have x=1, Then double it for considering -ve values of x and finally add, x = 0 case, you would get the formula. :)

Not elegant way at all, though there is clear trend in these additions, but would work.

0

I think it must 8 times the number of intergral solution to equation: $x+y+z=10$ So the result is : $8C_{12}^2=528$

0

(1) z=0, $40$ patterns

z=1, $36$

z=2, $32$

・・・

z=9,$4$

but z=10,$2$ the total is $S=2(4+8+\dots+36)+40+2=402$

(2) Another counting

There are 8 areas by plus and minus of x,y,z, 40 patterns at x=0, 2 patterns at y=z=0, therefore

$40+8*10C2+2=402$

0

x+y+z=10

  1. No. of integral solution when all are positive -> 9C2 = 36
  2. No. of integral solution when all are negative -> 12C2 = 66
  3. No. of integral solution when any one of them is negative = 10C2 = 45

Since there will be 3 cases, total solution possible = 45 * 3 = 135

  1. No. of integral solution when two of them are negative = 11C2 = 55

Since again there will be 3 cases, total solution possible - 55*3 = 165

Total solution possible = 36+66+135+165 = 402

I am using the formula when n identical things are to be distributed among r persons, each one of whom receives at least 1 item is (n-1)C(r-1).

Am i wrong in this method ?

  • 0
    Welcome to MSE. Please use [MathJax](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference).2017-08-31