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.

I have a linear equation in four variable

$ a + b + c + d = 10$

given that $a, b, c, d > 0$ and $a,b,c,d <= 6$ and $a,b,c, d$ are integer

what are total possible solution ?

share|improve this question
    
@Clayton - yes! –  AppDeveloper Jan 30 '13 at 23:38

3 Answers 3

up vote 1 down vote accepted

Let's first enumerate the solutions with $a \le b \le c \le d$.
You must have $d \ge 10/4 = 2.5$, so $d = 3$, $4$, $5$ or $6$.

With $d=6$, $a+b+c=4$, and it's easy to see that $a=1$, $b=1$, $c=2$.

With $d=5$, $a+b+c=5$, and you could have $a=1$, $b=1$, $c=3$ or $a=1$, $b=2$, $c=2$.

With $d=4$, $a+b+c=6$, and you could have $a=1$, $b=1$, $c=4$, or $a=1$, $b=2$, $c=3$ or $a=2$, $b=2$,$c=2$.

With $d=3$, $a+b+c=7$, and you could have $a=1$, $b=3$,$c=3$ or $a=2$,$b=2$,$c=3$.

Thus the solutions with $a \le b \le c \le d$ are $[a,b,c,d] = [1,1,2,6]$, $[1,1,3,5]$, $[1,2,2,5]$, $[1,1,4,4]$, $[1,2,3,4]$, $[2,2,2,4]$, $[1,3,3,3]$, $[2,2,3,3]$. Take all permutations of those and you get all the positive integer solutions.

share|improve this answer
    
This is too painful. 7 is close enough to 10 that you should consider counting the complement. –  Calvin Lin Jan 30 '13 at 23:59

Hint: Use the Principle of Inclusion and Exclusion. In a general solution of positive integers $w + x + y + z = 10$, notice that at most one of the them can be at least 7.


Additional Hint: If $a\geq 7$, there is only 1 solution.

Hence, by PIE, there are ${9 \choose 3} - 1 - 1 - 1 - 1 = 80$ solutions.


For Poseidonium. Assuming we want to solve $a+b+c+d = 20, a, b, c, d \leq 6$.

Let sets $A, B, C, D$ be the ways such that $a \geq 7$, etc. By PIE, we have

$$|A \cup B \cup C \cup D| = \sum |A| - \sum |A\cap B| + \sum |A \cap B \cap C| - |A \cap B \cap C \cap D|$$

This is equal to $ 4 \times { 13 \choose 3} - 6 \times {7 \choose 3} + 6 \times {1 \choose 3} - 0 = 934$. Hence, the number of ways is ${19 \choose 3} - |A \cup B \cup C \cup D| = 35$.

[I would have approached this by solving $w + x + y + z = 4$, using the substitution $w =6-a$ etc, subject to $0 \leq w \leq 5$, which is clearly a non-restriction since the sum is only 4, thus there are ${4+3 \choose 3} = 35$ solutions.]

share|improve this answer
    
a lil more help? –  AppDeveloper Jan 30 '13 at 23:46
    
@AppDeveloper Do you know what PIE is? Have you applied it before? –  Calvin Lin Jan 30 '13 at 23:55
    
@Poseidonium Thanks! Strangely I'm not used to the positive integer version, and much more familiar with the $\geq 0$ complicated version lol. –  Calvin Lin Jan 31 '13 at 0:03
    
@Poseidonium Do you mean replace 10 by 30? If so, I'd do it directly by saying there are no solutions. –  Calvin Lin Jan 31 '13 at 1:03
    
@Poseidonium I've shown how to 'properly' apply PIE using $a+b+c+d = 20$ as an example. –  Calvin Lin Jan 31 '13 at 1:11

I would do by a combinatorial approach.

Let's say you have 10 books a bookshelf and you have 3 stands to partition the books. (a/b/c/d books and each / being the stand)

You don't put stands next to each other. (a,b,c,d > 0)

You don't want a partition bigger than 6.. (a,b,c,d <= 6)

We further break it down into simpler parts and slowly work to our solution.

Part 1

If we are not restricted to a maximum of 6 books, we can put the 3 dividers between any 2 books and that gives us 9 options, ie. ${}^9{C_3}=84$

Unfortunately, this is not our answer as there will be some cases when the partitioning has more than 6 books.

Part 2 (which are the cases which are not acceptable?)

If there is more than 6, it has to be the partitions of 1/1/1/7, 1/1/7/1, 1/7/1/1 or 7/1/1/1.

So, there are 4 unacceptable cases

Answer

There are 80 way to partitition as required. In other words, there are 80 solutions to your algebraic question.

share|improve this answer

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.