Photo Credit: Flickr
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|
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)
Sometimes they can be referred to as the non-negative integral solutions
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.
It is also important to understand why this formula works but I will reserve that idea for another post.
Funda 3: a + b + c + d … = n
No. of natural number solutions will be (n-1) C (r-1)
Sometimes they can be referred to as the positive integral solutions
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
(b) no solution for x > 250 and y >-100
(c) no solution for x
(d) a solution for -59
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.
Ravi Handa, an alumnus of IIT Kharagpur, has been teaching for CAT and various other competitive exams for around a decade. He currently runs an online CAT coaching and CAT Preparation course on his website http://www.handakafunda.com