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



  • 0_1533617333370_alg.jpg

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