Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Or rather,how do we derive the formula? –  user43081 Oct 28 '12 at 12:30
    
yes !!! sir... any help will be appreciate... –  ram Oct 28 '12 at 12:36
add comment

6 Answers

up vote 33 down vote accepted

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

share|improve this answer
    
nice solution. It is easy to think that there is sort of convolution but to write them down in a systematic way is really good. –  Seyhmus Güngören Oct 28 '12 at 13:04
    
Very nicely done indeed! –  LieX Oct 28 '12 at 13:09
1  
@SeyhmusGüngören What does convolution mean in this context? (I'm new to this concept.) –  bodacydo Oct 30 '12 at 17:57
    
@bodacydo please have a look at : en.wikipedia.org/wiki/Convolution –  Seyhmus Güngören Oct 30 '12 at 20:46
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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}; $$

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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