Concepts & Solved Questions On Finding Number Of Integral/Positive/Non-Negative 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 = 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 :

    https://www.mbatious.com/topic/1000/solved-examples-on-the-application-of-a-b-c-n-type-of-equation

    https://www.mbatious.com/topic/73/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 SolutionsTotal Integer Solutions
    OddYes[(Number of factors of N) - 1] / 24 * Positive Integer Solutions + 2
    EvenYes{[Number of factors of (N/4)] - 1 } / 24 * Positive Integer Solutions + 2
    OddNo(Number of factors of N) / 24 * Positive Integer Solutions
    EvenNo[Number of factors of (N/4)] / 24 * 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.


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.