Number of Integral, Whole Number and Natural Number Solutions - Ravi Handa


  • www.handakafunda.com | IIT Kharagpur


    A very common type of problem that we get in CAT is when we are asked to find out the number of integral solutions to a given equation. I have always found it hard to categorize such sort of problems in a particular category. A case can be made that such questions belong to Number System or Permutation and Combination or even Algebra. Without going into the nomenclature bit, I would like to explain some of these ideas in this post.

    Funda 1: a + b + c + d … = n
    No. of integral solutions will be infinite.

    Let me take a simple case where a + b = 100
    One solution for this would be a = 100 & b = 0
    Another one would be a = 101 & b = – 1
    Another one would be a = 102 & b = – 2
    Another one would be a = 103 & b = – 3
    Another one would be a = 104 & b = – 4
    As you can see, there is not going to be an end to this list and this will have infinitely many solutions.
    To get a finite answer, you need to put in some sort of restrictions on it. One such restriction could be |a| < 100 and |b| < 50
    In such a case, ‘a’ can take any integral value from -99 to 99 whereas ‘b’ can take any value from -49 to 49.
    One solution for this would be a = 51 & b = 49
    Now, we can only decrease the value of ‘b’. So, we will have to increase the value of ‘a’. So,
    Another solution would be a = 52 & b = 48
    Another solution would be a = 53 & b = 47
    Another solution would be a = 54 & b = 46
    .
    .
    Another solution would be a = 99 & b = 1
    So, the total number of solutions in this case is 49.

    Funda 2: a + b + c + d … = n
    No. of whole number solutions will be (n + r - 1) C (r - 1)

    Let us take a simple case, where a + b = 100
    One solution for this would be a = 100 & b = 0
    Another solution for this would be a = 99 & b = 1
    Another solution for this would be a = 98 & b = 2
    Another solution for this would be a = 97 & b = 3
    Another solution for this would be a = 96 & b = 4
    .
    .
    Another solution for this would be a = 0 & b = 100

    So, the total number of solutions in this case is 101. We could have also used the formula for finding out the number of whole number solutions. n = 100 and r = 2 in this case (‘r’ represents the number of variables in the equation in which the sum has to be distributed)

    By applying the formula, we would have got (100 + 2 - 1) C (2 - 1) = 101 C 1 = 101

    I agree that for something as simple as this, we do not need the formula but even for a smaller value with even 3 variables, finding out the cases / solutions without the formula would be extremely hard. In case you do not believe me, try and find out the number of whole number solutions for a + b + c = 10

    By applying the formula, we will get (10 + 3 – 1) C (3 – 1) = 12 C 2 = 12 * 11/2 = 66.
    So, total number of whole number solutions in this case is 66.

    Funda 3: a + b + c + d … = n
    No. of natural number solutions will be (n - 1) C (r - 1)

    Consider, a + b + c + d = 100
    Number of natural number solutions for this would be (100-1) C (4-1) = 99C3 = 99 * 98 * 97/3 * 2 * 1 = 156849

    Funda 4: ax + by = n

    • The integer values of ‘x’ will be in an Arithmetic Progression with a common difference of ‘b’
    • The integer values of ‘y’ will be in an Arithmetic Progression with a common difference of ‘a’

    Let us look at a question from CAT 2003 to understand the application of this idea:

    If x and y are integers then the equation 5x + 19y = 64 has:
    (a) a solution for 250 < x < 260
    (b) no solution for x > 250 and y >-100
    (c) no solution for x < 300 and y < 0
    (d) a solution for -59 < y < -56

    One solution for the equation would be x = 9 & y = 1
    When x will increase y will decrease and their values will be
    x = 9, 28, 47, 66, …
    y = 1, -4, -9, -14, …
    So, the value of y in case of negative integers will always end in 4 or 9. This eliminates option (d)
    There will be a solution for x = 256 & y = -64. This eliminates B & C and makes option (a) as the answer.
    Please note that this idea can also be applied if you are trying to find out whole number solutions or natural number solutions as well.

    Funda 5: ax + by + cz = n

    First of all, it is highly unlikely that you will get something like this in CAT. Even if you do get something like this in the exam, I recommend trying out some other questions because the time you will spend on calculating something like this in the exam might be better used elsewhere. To solve, such questions it is best to take cases. If you select your cases smartly, you will find out the answer a lot faster. Let us try to solve:

    Example: Find out the whole number solutions for 2x + 3y + 5z = 50
    Now, the coefficient of z is the biggest so let us define our cases based upon various values of z which are possible.
    z = 0, 1, 2, 3 .. 10
    If z = 0; 2x + 3y = 50. x will be {1, 4, 7 … 25}. No. of solutions = 9
    If z = 1; 2x + 3y = 45. x will be {0, 3, 6, … 21}. No. of solutions = 8
    If z = 2; 2x + 3y = 40. x will be {2, 5, 8 … 20}. No. of solutions = 7
    If z = 3; 2x + 3y = 35. x will be {1, 4, 7, … 16}. No. of solutions = 6
    If z = 4; 2x + 3y = 30. x will be {0, 3, 6 … 15}. No. of solutions = 6
    If z = 5; 2x + 3y = 25. x will be {2, 5, 8, 11}. No. of solutions = 4
    If z = 6; 2x + 3y = 20. x will be {1, 4, 7, 10}. No. of solutions = 4
    If z = 7; 2x + 3y = 15. x will be {0, 3, 6}. No. of solutions = 3
    If z = 8; 2x + 3y = 10. x will be {2, 5}. No. of solutions = 2
    If z = 9; 2x + 3y = 5. x will be {1}. No. of solutions = 1
    If z = 10; 2x + 3y = 0. x will be {0}. No. of solutions = 1
    Total number of solutions = 9 + 8 + 7 + 6 + 6 + 4 + 4 + 3 + 2 + 1 + 1 = 51 solutions.

    If you did not agree with me earlier that such questions should not be attempted in CAT, may be you would agree with me after reading the solution.


Log in to reply
 

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