Concepts & Solved Questions On Finding Number Of Integral/Positive/NonNegative Solutions  Vikas Saini

Integral solutions  Solution can be any integer { ..., 2, 1, 0, 1, 2 ...}
Non negative solutions  Solution can be any whole number {0, 1, 2, 3 ...}
Positive solutions  Solution can be any natural number {1, 2, 3 ...}Type  1 : a + b + c + ... (r terms) = n
Non negative integer solutions = (n + r  1) C (n  1)
Positive integer solutions = (n  1) C (r  1)
Special cases :
Number of possible solutions for (a, b, c) when a + b + c = N and a > b > c ≥ 0 is [(n^2 + 6)/12]
Number of possible solutions for (a, b, c) when a + b + c = N and a ≥ b ≥ c ≥ 0 is [(n^2 + 6)/12] + [n/2] + 1
Examples:
Find the positive integer solutions of a + b + c = 15
Sol : (15  1) C (3  1) = 14C2 = 91Find the non negative integer solutions of a + b + c = 16
Sol : (16 + 3  1) C (3  1) = 18C2 = 153 ways.Find the non negative integer solutions of a + b + c + d = 20
Sol : (20 + 4  1) C (4  1) = 23C3 = 1771Find the possible solutions for a + b + c = 100 if
a) a > b > c ≥ 0
b) a ≥ b ≥ c ≥ 0
Sol:
a) [(100^2 + 6)/12] = 833
b) 833 + [100/2] + 1 = 884Further Read :
https://www.mbatious.com/topic/1000/solvedexamplesontheapplicationofabcntypeofequation
https://www.mbatious.com/topic/73/permutationcombinationconceptsbygauravsharmapart22
Type 2 : x + y = n
Number of integer solutions of
x + y = n > 4n
x + y < n > 1 + 4 * (1 + 2 ... + (n  1))
x + y ≤ n > 1 + 4 * (1 + 2 ... + n)
x + y + z = n > 4n^2 + 2
w + x + y + z = n > 8n/3 * (n^2 + 2)
Examples:
Number of integral solutions of x + y + z = 15
Sol : 4 * 15^2 + 2 = 902Number of integral solutions of x + y < 7
Sol : 1 + 4 * (1 + 2 + 3 .. + 6) = 85Number of integral solutions of x + y ≤ 7
Sol : 1 + 4 * (1 + 2 + 3 .. + 6 + 7) = 113Type 3 : x * y = N
If N is not a perfect square : Positive integer solutions = (Number of Factors of N)/2
If N is a perfect square : Positive integer solutions = (Number of Factors of N + 1)/2 (for one case, x = y)
Total integer solutions will be Positive Integer Solutions * 2
Examples:
How many ways can 36 be expressed as a product of 2 natural numbers?
Sol : 36 = 2^2 * 3^2
Number of factors = 3 * 3 = 9
Positive integer solutions = (9 + 1)/2 = 5
(1,36), (2, 18), (3, 12), (4, 9), (6, 6)How many ways can 27 be expressed as a product of 2 integers?
Sol: 27 = 3^3
Number of factors = 4
Total Integer solutions = 2 * 4 = 8
(1,27), (3,9), (9,3), (27,1), (1,27), (3,9), (9,3), (27,1)In how many ways can a number 6084 be written as a product of two different positive factors?
Sol: 6084 = 2^2 * 3^2 * 13^2
Number of factors = 3 * 3 * 3 = 27
Positive Integer solutions = (27 + 1)/2 = 14 pairs.
Note, 6084 is a perfect square so we will have a case where both factors are same.
So removing that case, 6084 can be written as a product of two different positive factors in 14  1 = 13 ways.In how many ways can 840 be written as the product of 2 positive numbers?
Sol: 840 = 2^3 * 3 * 5 * 7
Number of factors = 4 * 2 * 2 * 2 = 32
So we can have 32/2 = 16 distinct pairs whose product is 840.Type 4 : x * y * z = N
Say, N = p1^a * p2^b * p3^c * ...
Number of ordered positive solution = (a+2)C2 * (b+2)C2 * (c + 2)C2 ...
Number of integral ordered integral solution = 4 * Number of ordered positive solution
Examples:
In how many ways 72 can be written as product of 3 positive integers
72 = 2^3 * 3^2
no of ordered solution = (3+2)C2 * (2+2)C2
= 5C2 * 4C2
= 10 x 6
= 60.We have to remove aab & aaa cases.
aab cases
2^(0+0) b
2^(1+1) b
(2 * 3)^(1+1) b
3^(1+1) b
aab cases = 4.
this 4 cases can be written in 3!/2! = 3 ways.aaa = 0 cases.
Total positive solution = [(60  3 * 4) / 3!] + 4
= [(60  12)/6] + 4
= (48/6) + 4
= 12 ways.(1,1,72),(2,2,18 ),(3,3,8 ),(6,6,2),(1,2,36),(1,3,24),(1,4,18 ),(1,6,12),(1,8,9),(2,3,12),(2,4,9),(3,4,6).
In how many ways 72 can be written as product of 3 integers ?
72 = 2^3 * 3^2
Total ordered solution = 4 * (3+2)C2 * (2+2)C2
= 4 * 5C2 * 4C2
= 4 * 10 * 6
= 240.N = ABC
N = (A)(B )C
N = (A)B(C)
N = A(B )(C)It means N can be written in 4 ways, that is why we multiplied by 4.
we need to remove aab & (a)(a)b.
we have seen aab cases above.
now (a)(a)b cases
(1)^(0+0) b
(2)^(1+1) b.
(3)^(1+1) b.
{(2)(3)}^2 b
total cases = 4 + 4 = 8 cases.(240  3 * 8 )/3! + 8
= (240  24)/6 + 8
= 216/6 + 8
= 36 + 8
= 44Total = 44 ways.
In how many ways 3^15 can be written as product of 3 positive integers?
3^15 = 3^(a+b+c)
a + b + c = 15.
total solution = (15+31)C(31)
= 17C2
= 17 * 16/2
= 136.aab cases
(0,0,15)(1,1,13),(2,2,11),(3,3,9),(4,4,7),(6,6,3),(7,7,1)aaa cases
(5,5,5)we will remove both cases.
so number of ways = (136  3 * 7  1)/3! + 7 + 1
= (136211)/6 + 8
= 114/6 + 8
= 19 + 8
= 27In how many ways 343000 can be written as product of 3 integers?
343000 = 2^3 * 5^3 * 7^3
total ordered solution =4 * (3+2)C2 * (3+2)C2 * (3+2)C2
= 4 * (5C2)^3
= 4 * (10)^3
= 4 * 1000
= 4000.aab cases : 7
(a)(a)b cases = 7
(a)(a)a cases = 1
aaa cases = 1.
total solutions = (4000  3 * 7  3 * 7  3 * 1  1)/3! + 7 + 7 + 1 + 1
= (4000  21  21  3  1)/3! + 16
= (4000  46)/3! + 16
= 3954/6 + 16
= 659 + 16
= 675.If question would have been asked just for positive integers.
then ordered solution = (3+2)C2 * (3+2)C2 * (3+2)C2
= 5C2 * 5C2 * 5C2
= 1000.aab cases = 7
aaa cases = 1
total solution = (1000  3 * 7  1)/3! + 7 + 1
= 978/6 + 8
= 163 + 8
= 171Type 5 : ax + by = n
There are infinite integral solutions. So we will get questions asking for positive or nonnegative solutions.
Find one solution of x. Then the other solutions can be listed as an Arithmetic Progression with common difference as the coefficient of y which can be easily counted. No need to learn any trick or formula for this type. It is best to learn with examples
Examples:
Positive integral solutions of 2x + 3y = 30.
Sol : put x = 1, y = 28/3 (not a positive integer solution)
put x = 2, y = 26/3 (again, not a positive integer solution)
put x = 3, y = 24/3 = 8 (a positive integer solution!)
From here increase x as step of coefficient of y (3). value of y will decrease as step of coefficient of x (2)
So x = 3, y = 8
x = 6, y = 6
x = 9, y = 4
x = 12, y = 2
x = 15, y = 0 (from here it is not a positive integer solution. So we can stop listing and start counting)
So we have 4 positive integer solutions for the given equation.Non negative integer solutions of 2x + 3y = 20
Sol : put x = 1, y = 18/3 = 6 (non negative integer solution!)
From here increase x as step of coefficient of y (3). value of y will decrease as step of coefficient of x (2)
x = 1, y = 6
x = 4, y = 4
x = 7, y = 2
x = 10, y = 0
x = 13, y = 2 (from here it is not a non negative integer solution. So we can stop listing and start counting)
So we have 4 non negative integer solution for the given equation.Positive solutions of 3x + 4y = 17
Sol : put x = 1, y = 14/4 (not a positive integer solution)
put x = 2, y = 11/4 (again, not a positive integer solution)
put x = 3, y = 8/4 = 2 (a positive integer solution)
now we can see the next possibility is x = 3 + 4 = 7 for which y will be negative. So from x = 3 no more positive integer solutions exist.
So we have only one positive integer solution for the given equation.Short cut  If for ax + by = N, either of a or b can divide N, then number of nonnegative solutions = [N/LCM(a,b)] + 1
Example : 2x + 3y = 20
as 20 can be divided by 2, Non negative integer solutions = [20/LCM(2,3)] + 1
= [20/6] + 1
= 3 + 1
= 4Type 6 : a⁄x ± b⁄y = 1/n
a/x + b/y = 1/k.
T = Factors of (a * b * k^2)
Total Integer solution = 2T  1.
positive solution = T
negative solution = 0a/x  b/y = 1/k.
T = Factors of (a * b * k^2)
Total Integer solution = 2T  1.
positive solution = (T  1)/2
negative solution = (T  1)/2Please watch this video lecture by Amiya sir for a better understanding of the concept
Examples
Find total integral solutions and positive solutions of 8/x + 7/y = 1/3
T = Factors of (56 * 9) = Factors of (7 * 2^3 * 3^2) = 2 * 4 * 3 = 24
Total integer solutions = 2T  1 = 47
Positive solutions = T = 24Find total integral solutions of 2/x  1/y = 1/3
T = Factors of (2 * 1 * 9) = Factors of (2 * 3^2) = 2 * 3 = 6
Total integer solutions = 2T  1 = 11Type 7 : x^2  y^2 = N
If N = 4k + 2 form, no integer solution exist.
For other cases, refer the table below
N is Odd/Even? N is Perfect Square? Positive Integral Solutions Total Integer Solutions Odd Yes [(Number of factors of N)  1] / 2 4 * Positive Integer Solutions + 2 Even Yes {[Number of factors of (N/4)]  1 } / 2 4 * Positive Integer Solutions + 2 Odd No (Number of factors of N) / 2 4 * Positive Integer Solutions Even No [Number of factors of (N/4)] / 2 4 * Positive Integer Solutions Examples :
Number of integral solutions of x^2  y^2 = 288
Here, N is even and Not a perfect square.
So Positive Integral Solutions = [Number of factors of (N/4)] / 2 = [Number of factors of 72] / 2 = 12/2 = 6
Total integral solutions = 4 * Positive Integral Solutions = 4 * 6 = 24Number of integral solutions of x^2  y^2 = 900
Here, N is even and is a perfect square.
So Positive Integral Solutions = {[Number of factors of (N/4)]  1 } / 2
= {[Number of factors of 225]  1 } / 2 = (9  1)/2 = 4
Total Integer Solutions = 4 * Positive Integer Solutions + 2 = 4 * 4 + 2 = 18Further Read : https://www.mbatious.com/topic/94/numberofsolutionsforequationsinvolvingdifferencesumofperfectsquareshemantmalhotra
Type 8 : x^2 + y^2 = N
If N has a prime factor of the form (4k + 3), which is not raised to an even power then no integer solution exist.
Example : a^2 + b^2 = 7 has no integer solution as 7 (which is in the form 4k + 3) is not raised to an even power.
When N is not a perfect square
Number of ordered positive integral solutions = Number of factors of N ignoring the presence of (4k + 3) primes and 2
Total integral solutions = (Ordered Positive integral solutions) * 4When N is a perfect square
Number of ordered positive integral solutions = Number of factors of N minus 1 ignoring the presence of (4k + 3) primes and 2
Total integral solutions = (Ordered Positive integral solutions) * 4 + 4Examples :
Number of integral solutions of x^2 + y^2 = 246
246 = 2 * 3 * 41
3, which is of the form (4k + 3) is not raised to an even power here. So no integer solution exist.Number of integral solutions of x^2 + y^2 = 25
25 = 5^2
Number of ordered positive integral solutions = 3  1 = 2
Total integral solutions = 2 * 4 + 4 = 12Further Read : https://www.mbatious.com/topic/849/theoryofequationssumofsquaresanubhavsehgalnmimsmumbai
Special case : Number of integral solutions of x^2 + y^2 ≤ r^2 (a circle of radius r) is approximately equal to its Area = [πr^2]
This is just an approximation, it is safe to go with the Gauss's formula :
Number of integral solutions of x^2 + y^2 ≤ r^2 = 1 + 4[r] + 4 * [(Summation i = 1 to R] √(r^2  i^2)] (looks bit complicated but it is very easy once you solve couple of questions)
Example :
Find the number of integer solutions for x^2 + y^2 ≤ 16
Total Integral solutions = 1 + 4 * 4 + 4 * (3 + 3 + 2) = 1 + 16 + 32 = 49
This includes 4 boundary cases : (0, 4), (0, 4), (4, 0), (4, 0)
So if the question asked for x^2 + y^2 < 16, we have to remove the boundary cases.
In which case, total integral solutions = 49  4 = 45Find the number of integer solutions for x^2 + y^2 < 25
Total Integral solutions of x^2 + y^2 ≤ 25 = 1 + 4 * 5 + 4 * (4 + 4 + 4 + 3 + 0) = 1 + 20 + 60 = 81
Now we need to find the boundary conditions (which is basically the integral solutions of x^2 + y^2 = 25)
(0, 5), (0, 5), (5, 0), (5, 0), (3, 4), (4, 3), (4, 3), (3, 4), (3, 4), (4, 3), (3, 4), (4, 3)
Total 12 boundary points.
So x^2 + y^2 < 25 has 81  12 = 69 integral solutions.Bonus:
Some Algebra tricks that might come handy during exams.
Short cut  1
If [m/(x+a) (x+b)] + [n/(x+b)(x+c)] + [o/(x+c)(x+a)] = 0.
then x =  (mc + na + ob)/(m + n + o)or
x = n * vanished number / (n1 + n2 + n3)
Here n = numerator.Examples:
1/(x 1)(x2) + 2/(x2)(x3) + 3/(x3)(x1) = 0.
By direct formula
x =  [1 * (3) + 2 * (1) + 3 * (2)] / (1 + 2 + 3)
x =  (11)/6
x = 11/6.1/(x^2+3x+2) + 5/(x^2+5x+6) + 3/(x^2+4x+3) = 0
1/(x+2)(x+1) + 5/(x+2)(x+3) + 3/(x+1)(x+3) = 0
x =  [ 1 * 3 + 5 * 1 + 3 * 2 ] / ( 1 + 5 + 3)
x =  14/9.Short cut  2
1/xy + 1/xz = 1/xw + 1/yz
if x, y, z & w are in Arithmetic progression then last term + 2 * second last term = 0.Examples:
1/(x+2)(x+3) + 1/(x+2)(x+4) = 1/(x+2) (x+5) + 1/(x+3)(x+4)
Here 2, 3, 4, 5 are in AP.
So last term + 2 * second last term = 0.
(x+5) + 2(x+4) = 0
x + 5 + 2x + 8 = 0
x = 13/3.1/(x+1)(x+3) + 1/(x+1)(x+5) = 1/(x+1)(x+7) + 1/(x+3)(x+5)
1, 3, 5, 7 are in AP.
So (x+7) + 2(x+5) = 0.
x + 7 + 2x + 10 = 0.
x = 17/3.Short cut  3
If ax^2 + bx + c / dx^2 + ex + f = ax+b / dx+e
then c / d = ax+b / dx+e.Examples:
3x^2+5x+8 / 5x^2+6x+12 = 3x+5/5x+6
8 / 12 = 3x+5 / 5x+6
2 / 3 = 3x+5 / 5x+6
10x+12 = 9x+15
x = 3.22x3x^2 / 25x6x^2 = 3x+2 / 6x+5
here (3x^2+2x)+2 / (6x^2+5x)+2 = 3x+2 / 6x+5
3x+2/6x+5 = 2/2
3x+2 = 6x+5
x = 1.(x+2)(x+3)(x+11)= (x+4)(x+5)(x+7)
(x+2)(x+3)/(x+4)(x+7) = (x+4)/(x+11)
x^2+5x+6 / x^2+11x+28 = x+4/x+11
6/28 = (x+5)/(x+11)
3 / 14 = (x+5) / (x+11)
3x + 33 = 14x + 70
11x = 37
x = 37/11.Short cut  4
To find the sum of given series y/(x+a)(x+b) + z/(x+b)(x+c) .....
Sn = [{y + z......(n times)}/ (x+a) {x+a+n(ba)}]Examples:
Find sum of four terms of the series 1/(x+3)(x+4) + 1/(x+4)(x+5) + 1/(x+5)(x+6) ....
S4 = (1 + 1 + 1 + 1)/(x+3) {x+3+(43)4}
= 4/(x+3)(x+7)Find sum of five terms of the series 1/(x^23x+2) + 1/(x^25x+6) ....
1/(x1)(x2) + 1/(x2)(x3)
S5 = (1 + 1 + 1 + 1 + 1) / (x1) {x1+(3+2)5}
= 5 / (x1)(x6)Find the sum of 1/(2 * 3) + 1/(3 * 4) + 1/(4 * 5) ... + 1/(19 * 20)
Here Terms = 19  1 = 18.
S18 = (1 + 1 .. 18 times) / 2 x {2+(32)x18}
= 18 / 2 x 20
= 18 / 40Short cut  5
(ba)/(x+a)(x+b) + (cb)/(x+b)(x+c) + .... + (zy)/(x+y)(x+z)
Sum = (za)/(x+a)(x+z)Examples:
Find the sum of 1/(7 * 8) + 2/(8 * 10) + 14/(24 * 10)
Sum = (1 + 2 + 14) / (7 * 24)
= 17/168.Find the sum of 3/(7 * 10) + 9/(10 * 19) + 27/(19 * 46) + 99/(46 * 145)
Sum = (3 + 9 + 27 + 99) / (7 * 145)
= 138 / 1015.Evaluate 3/4 + 5/36 + 7/144 + 9/400 ....19/8100
By direct formula
3/(4 * 1) + 5/(4 * 9) + 7/(9 * 16) + 9/(16 * 25) ... 19/(81 * 100)
= 3 + 5 + ... 19 / (1 * 100)
= (3 + 19) * 9 / (2 * 100)
= 99/100Kindly point out any errors/improvements in this article to me or to MBAtious team. You can also suggest any concept that is missing here.