Quant Boosters by Sabyasachi Mishra, CAT 100 percentiler.

Sabyasachi Mishra scored a perfect 100 percentile in CAT 2015 and opted for the deferred admission at IIM A. He graduated from IIT Kharagpur and is currently working as a consultant in EXL Analytics.
Q1) Find the sum of all the three digit numbers that contain only 1, 2, 3 or 4. It can contain the digits more than once in the same number too.
Say a 3 digit number is abc.
Now there are 4 ways to choose a, 4 ways for b and 4 ways for c = > There are 4 *4 * 4 = 64 threedigit numbers that can be made using 1,2,3 and / or 4.
Let’s write all these numbers one below another to add them up. Now each digit would appear 16 times in ones place.
Their sum = 16 *(1 + 2+ 3 + 4) = 160
Similarly the tens place would add up to 160 and the hundreds place too.
So the actual sum = 160 (1 + 10 + 100) = 160 * 111 = 17760
Q2) What is the Probability of selecting 3 numbers from 150 such that no two are consecutive?
Imagine you have three 0s and 45 1s.
Every sequence you make would look somewhat like this.
10111111101111 … 1011 or 10011111 … 1011
Let’s say after every sequence, I put one 1 after the first zero and another 1 after the second zero.
Now I have a sequence of 50 digits, all in the form of 1 or 0. And no two zeroes are consecutive.
Now 1 represents notchosen and 0 represents chosen. So, I have picked three numbers between 1 and 50 such that no two of them are consecutive. (each 1 or 0 representing the status of numbers from 1 to 50 in order)
The question simplifies into finding the number of ways three 0s and 45 1s can be arranged = > (48! / 45! 3!) or (48 C 3)
Now ways of selecting 3 numbers of the 50 = 50 C 3
Probability = 48C3 / 50C3 = 48 * 47 * 46 / 50 * 49 * 48 = 47 * 46 / 50 * 49 = 0.88245
Q3) how many numbers are there from 1 to 1000 which are not divisible by the digits 2, 3 and 5?
A) 166
B ) 266
C) 375
D) 366
Yes, this can be solved using a Venn diagram and intersections. But, if you are going to solve it in an exam, I would suggest a better and faster approach.
Here, in our case LCM of 2,3 and 5 is 30.
So, we can say that, if we write from 1 to 30 and find out the pattern, the same would be repeated across sets of 30 numbers thereafter.
Step 1
Write all numbers from 1 to 30
Step 2
Start with 2, the smallest divisor and cross out the numbers that are divisible. Then move to the next smallest one, in this case 3, circle out the numbers divisible by 3. And then do it for 5, use squares. The sheet would look like this.
Step 3
Now that you need the numbers that are not divisible by either of these factors, let’s list them out.
Step 4
Finding the answer
1000 = 30 * 33 + 10
So, the numbers not divisible by 2,3 or 5 would be 8 * 33 + 2 = 264 + 2 = 266
Note:
 This method can also be used to find the number of numbers between ranges that are divisible by specific factors. We need to start the count from the smallest number in the range and then list down a series of consecutive numbers (total count = LCM of factors)
 This method can also be used to find the number of numbers divisible by 2,3 and 5. In that case, instead of listing down the left ones, list down the crossed / highlighted ones.
 This method works faster when you have to do it on a small subset and extend the results. If the LCM is more than 100 or the factors are large numbers, Venn diagram method would be the way to go ahead.
Q4) How many AP can be formed with common difference 1 and sum is 840?
Sum of an AP can be written as (n/2)*(2a + (n1)d)
Given:
 In our case, d = 1
 n is a natural number
 a is an integer
Analysis:
So, our equation now reduces to 2na+n(n1) = 840 * 2 = 1680
= > n^2 + (2a  1)n  1680 = 0
Using the quadratic formula we can say that
n = [ – (2a – 1) +/ root( ( 2a – 1)^2 – 4 (1) ( 1680)] / 2
So, this is clear that for an integral value of a, there would be one positive n and one negative n = > For one integral value of a, there would be one possible n.
(This makes sense as when we define the start point of the AP, the length inevitably gets fixed as the sum is constant)So, our question now changes to find the integral solutions of a.
From simple observation, we can say a can both be odd or even.
(2a1)^2 + 4*1680 has to be a perfect square.
Lets say 2a 1 = x
now, x^2 + 4 * 1680 = y^2
(Keep in mind that y is positive all the time because when we take the square root while solving a quadratic equation we only use the absolute value)y^2  x^2 = 4 * 1680
(yx)(y+x) = 2a * 2b where ab = 1680
If we find all solutions of ab = 1680 where a > 0, b > 0 then y would always be positive and x can be positive or negative.
1680 = 2^4 * 3 * 5 * 7
So, (4+1) * 2 * 2 * 2 = 40 factorsSo, a can be any of these 40 and b would be 1680 / a.
There are 40 cases.
(Keep in mind that we are already counting the cases where x is negative as when b < a, x is negative)So, x can have 40 values = > 2a 1 has 40 possible values and hence a has 40 possible integral values = > n can have 40 values
= > There are 40 possible cases of writing an AP with common difference 1 where the sum would be 840.
Q5) How many numbers below 100 can be written as a difference of squares of natural numbers in only one way?
Let’s say x= a^2  b^2 = > x = (a+b)(ab)
If x has to be written as the difference of squares of two natural numbers in only one way, then there must be only one way to write x as (a+b) * (ab) where (a+b) > (ab).
> means that b can’t be zero and hence, (a+b) != (ab)Now, (a+b) and (ab) will either both be odd or both be even.
 Case : Both (a+b) and (ab) are odd
x = odd * odd = > odd
If x is an odd number, it can always be represented as 1 * x. If x has more than one factor(excluding one and x itself), say two factors then x= c*d can always be written. So, we have to find x where x is either an odd prime or x is the square of an odd prime.
x= k^2 (k being an odd prime) can be factorized as 1* k^2 or k*k.
k*k would mean x = k^2  0^2 (not allowed as 0 is not a natural number)
We have 25 prime numbers less than 100, hence 24 cases(excluding 2) and 9,25,49 as squares of odd primes = > 27 cases in all  Case : Both (a+b) and (ab) are even
x = even * even = > even
x = 2a * 2b = > x = 4 * (ab) & x < = 100
= > ab < = 25 where a!=b & a and b are both natural numbers
Lets say K=ab, K should be represented as ab in only one way. Similar to the above logic (except that numbers can be even too). K can be prime numbers or prime squares. So, k = 2,3,5,7,11,13,17,19,23 or 4,9
= > 11 cases in all
So there are 27 + 11 = 38 numbers between 1 and 100 which can be represented as the difference of natural squares in only one way.
Q 6) How many three digit numbers are there whose sum of digits is divisible by 5?
Lets say the 3 digit no. is abc.
 Case 1  two of them are zero = > 1
Only one possible number 500.  Case 2 one of them is zero = > 4 * 8 + 2 * 1 =34
a can’t be zero. So, a + b or a+c is divisible by 5.
For a = 1, the other one could be 4 or 9
a = 2, the other could be 3 or 8
Except for a=5 rest each case has two possiblities = > 4 numbers each
For 5 ther’s 550 or 505 = > 2 numbers  Case 3 none of them is zero = > 6 + 36 + 61 + 36 + 6 = 145
Sum of all three digits can vary between 3 and 27 as none of them is zero. So, the sum can be 5,10,15,20 or 25 Sum is 5 = > 6 cases
1 + 1 +3 = 5 = > 3 numbers
1 + 2 + 2 = 5 = > 3 numbers  Sum is 10 = > 3*4 + 6*4 = 36 cases
1 + 1 + 8 = > 3 numbers
1 + 2 + 7 = > 6 numbers
1 + 3 + 6 = > 6 numbers
1 + 4 + 5 = > 6 numbers
2 + 2 + 6 = > 3 numbers
2 + 3 + 5 = > 6 numbers
2 + 4 + 4 = > 3 numbers
3 + 3 + 4 = > 3 numbers  Sum is 15 = > 15 + 18 + 18 + 9 + 1 = 61 cases
1 + (5 + 9) / (6 + 8 ) / (7 + 7) = > 6, 6, 3 numbers = 15
2 + (4 + 9) / (5 + 8 ) / (6 + 7) = > 6, 6, 6 numbers = 18
3 + (3 + 9) / (4 + 8 ) / (5 + 7) / (6 + 6) = > 3, 6, 6, 3 numbers = 18
4 + (4 + 7) / (5 + 6) = > 3, 6 numbers = 9
5 + 5 + 5 = > 1 number = 1  Sum is 20 = > 3 + 6 + 9 + 12 + 6 = 36 cases
2 + 9 + 9 = > 3 numbers = 3
3 + 8 + 9 = > 6 numbers = 6
4 + (7 + 9) / (8 + 8 ) = > 6,3 numbers = 9
5 + (6 + 9) / (7 + 8 ) = > 6, 6 numbers = 12
6 + (6 + 8 ) / (7 + 7) = > 3, 3 numbers = 6  Sum is 25 = > 3 + 3 = 6 cases
9 + 8 + 8 = > 3 numbers = 3
9 + 9 + 7 = > 3 numbers = 3
 Sum is 5 = > 6 cases
145 + 34 + 1 = 180
So, there are 180 such numbers.There is also this easier alternate method that is a bit difficult to visualize if you are encountering such a question for the first time. But, here it goes.
You can say that in every consecutive 10 numbers where only the ones place is changing, there would be exactly 2 such numbers whose digits’ sum is divisible by 5.
I can have (100  109), (110  119) … (990  999) i.e. 90 such cases as there are 900 3 digit numbers. And hence, there would be 90 * 2 = 180 such numbers.
Q7) How many natural numbers between 1& 100 have exactly 4 factors?
Every number x can be represented in this manner.
x = (a1 ^ b1) * (a2 ^b2) * (a3^b3) … where a1, a2, a3 are all prime numbers
Number of factors of x = (1+b1)*(1+b2)*(1+b3) …
Now, we know that 4 = 2*2 or 1*4
So, all numbers which have 4 factors would either be in the form of
 a^3 where a is a prime; Factors would be 1,a,a^2 & a^3
 a * b where a and b are both primes; Factors would be 1,a,b & ab
Prime cubes between 1 and 100 are 8 and 27. So, 2 cases.
Cases
 For a=2, b = 3,5,7,11,13,17,19,23,29,31,37,41,43,47 = > 14 cases
 For a=3, b=5,7,11,13,17,19,23,29,31 = > 9 cases
 For a=5, b=7,11,13 = > 3 cases
So total possible cases = 2+14+9+3 = 28
Q8 ) What are the last two digits of 168^1057?
Think of this as (160+8 )^1057.
When you expand this term, the last two digits of all terms would be 00 except 8^1057 and 1057 * 8^1056 *160. (Binomial expansion used)
The second term clearly would be …60, 0 due to 160 and 6 due to multiplication of 8^1056 = (8^4)^264 = 6^254 by 6.
For, the first term
8^1 = 08 Case 1
8^2 = 64
8^3 = 12
8^4 = 96
8^5 = 68 Case 2
8^6 = 44
8^7 = 52
8^8 = 16
8^9 = 28 Case 3
8^10 = 24
8^11 = 92
8^12 = 36
8^13 = 88 Case 4So, we can say multiplying 8 by 8^4 adds 6 to tens place.
8^1057 = 8 * (8^4)^264 = > adding 6 264 times to the tens place i.e. 0 and keeping the units place as 8 = > last 2 digits are 48.
So, last 2 digits overall = 48 + 60 = 08
P.S. You can figure out the trend of last 2 digits by solving upto Case 3.
Also generally (x^4)^y follows a pattern for all x, where y keeps increasing by 1. So, you could directly see the trend for (8^4), (8^4)^2, (8^4)^3 and deduce from that.