Concepts & Solved Questions On Finding Number Of Integral/Positive/Non-Negative Solutions - Vikas Saini

[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 = 91

Find 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 = 1771

Find 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 = 884

Further Read :

Finding Number of Positive & Non-Negative Integral Solutions For a + b + c + ... = N & Its Applications

Permutation & Combination Concepts by Gaurav Sharma - Part (2/2)

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 = 902

Number of integral solutions of |x| + |y| < 7
Sol : 1 + 4 * (1 + 2 + 3 .. + 6) = 85

Number of integral solutions of |x| + |y| ≤ 7
Sol : 1 + 4 * (1 + 2 + 3 .. + 6 + 7) = 113

Type 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
= 44

Total = 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+3-1)C(3-1)
= 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
= (136-21-1)/6 + 8
= 114/6 + 8
= 19 + 8
= 27

In 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
= 171

Type 5 : ax + by = n

There are infinite integral solutions. So we will get questions asking for positive or non-negative solutions.

Find one solution of x. Then the other solutions can be listed as an Arithmetic Progression with common difference as the co-efficient 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 co-efficient 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 co-efficient 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 non-negative 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
= 4

Type 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 = 0

a/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)/2

Please 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 = 24

Find 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 = 11

Type 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 = 24

Number 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 = 18

Further Read : https://www.mbatious.com/topic/94/number-of-solutions-for-equations-involving-difference-sum-of-perfect-squares-hemant-malhotra

https://www.mbatious.com/topic/848/theory-of-equations-difference-of-squares-anubhav-sehgal-nmims-mumbai

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) * 4

When 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 + 4

Examples :

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 = 12

Further Read : https://www.mbatious.com/topic/849/theory-of-equations-sum-of-squares-anubhav-sehgal-nmims-mumbai

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 = 45

Find 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)(x-2) + 2/(x-2)(x-3) + 3/(x-3)(x-1) = 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.

2-2x-3x^2 / 2-5x-6x^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(b-a)}]

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+(4-3)4}
= 4/(x+3)(x+7)

Find sum of five terms of the series 1/(x^2-3x+2) + 1/(x^2-5x+6) ....
1/(x-1)(x-2) + 1/(x-2)(x-3)
S5 = (1 + 1 + 1 + 1 + 1) / (x-1) {x-1+(-3+2)5}
= 5 / (x-1)(x-6)

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+(3-2)x18}
= 18 / 2 x 20
= 18 / 40

Short cut - 5

(b-a)/(x+a)(x+b) + (c-b)/(x+b)(x+c) + .... + (z-y)/(x+y)(x+z)
Sum = (z-a)/(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/100

Kindly point out any errors/improvements in this article to me or to MBAtious team. You can also suggest any concept that is missing here.