2IIM's blog on cracking the quant section of the CAT. Frequent posts on interesting questions, tips, shortcuts in math.

Mar 9, 2015

CAT Online Class - Interesting one from Number Systems

Question
Actually, this is not a CAT preparation question. This is way tougher than what one can expect to see in CAT. I saw it on some Olympiad paper. But this is a wonderful question to think about one very interesting property. Anyway, let us get to the question -

A six-digit number has digits 'abcabd', where a, b, c, d take values from 0 to 9. Further we know that d = c + 1 and that this number is a perfect square. Find the number. If there is more than one number possible, find all such numbers.

Answer
183184, 328329, 528529, 715716

Explanation
This is a fabulous question. It bears repeating that this is far far tougher than what we are likely to see in CAT. Nevertheless we will look at this question in order to discuss one key idea.

Now, 'abcabd' is a perfect square. So, say, 'abcabd' = x^2
Now, 'abcabd' = 'abcabc' + 1. So, 'abcabc' = x^2 - 1

After this, we are halfway there to the solution

'abcabc' = (x +1) (x - 1)

Now, 'abcabc' = 'abc' * 1001. Or, 'abcabc' = 'abc' * 1001. This is the key idea that is very vital in a bunch of questions.

'abc' * 1001 = 'abc * 7 * 11 * 13 = (x - 1) (x + 1)

So, between x -1 and x + 1, we need to account for 7, 11 and 13 as factors. Wherever this works, we are through. Now, x - 1 or x + 1, either number alone cannot be a multiple of 7, 11 and 13. So, one of these two should be a multiple of one of the three primes and the other should be a multiple of the other two.

So, of the two numbers one can be a multiple of 7 and the other 143. or,
one can be a multiple of 11 and the other 91. or,
one can be a multiple of 13 and the other 77,

After this we are down to trial and error; but a very scientific form of trial and error.

Let us say, we are picking two numbers such that one is a multiple of 7 and the other of 143. Since 143 is the far larger number, it helps to look for multiples of  143 and see if we can spot the scenario where the other number is a multiple of 7.

If one number were 143, the other would have to  be 145 or 141. Neither is a multiple of 7. This does not work.

If one number were 286, the other would have to  be 284 or 288. Neither is a multiple of 7. This does not work either.

If one number were 429 (143 * 3), the other would have to  be 427 or 429. 427 is a multiple of 7. Houston, we have an answer!

(x -1) * (x + 1) = 427 * 429 works. 427 * 429 = 183183. Or, 183184 is a perfect square. 428 * 428.

Now, all we need to do is check out all other variants. But having said that, even this can be a very time-consuming process. So, let us see if we can fine-tune this a touch. If one number is a multiple of 143, the other number should be a multiple of 7. So, the first number  + 2 or first number -2 should be a multiple of 7. If we say the first number were k, then either k + 2 or k - 2 should be a multiple of 7. In that case, we are through. or, k divided by 7 should give us a remainder of 2 or 5.

Now, 143 divided by 7 gives us a remainder of 3. This is why this does not work

2 * 143 divided by 7 will give us a remainder of 6. This does not work either
3 * 143 divided by 7 will give us a remainder of 9, which is same as 2. This works. This is what gave us the solution 183184
4 * 193 gives us a remainder of 12, which is same as 5. This should also work. Let us check this out. 4 * 143 = 572. 574 is a multiple of 7. Or, 572 * 574 will be a multiple of 1001.
572 * 574 = 328328. or, 328329 = 573 *573. We have got our second possibility!!

183184 and 328329 are both perfect squares.

Now, let us move to 5 * 143. This divided by 7 gives us a remainder of 15, which is same as 1. This does not work either

Let us move to 6 * 143. This divided by 7 gives us a remainder of 18, which is same as 4. This does not work either

7 * 143 = 1001. That is a 4-digit number, so we do not have to worry about this.

So, we have got two solutions so far. With the numbers being divided as product of 143 and of 7. Let us move to the combination of the numbers being broken as product of 91 and 11.

Now, let us go directly to the remainder approach. 91 divided by 11 gives us a remainder of 3. We need to find some multiple of 91 that on division by 11 gives us a remainder of either 2 or 9. (Why? scroll up to see this. We are looking for numbers that differ by 2 which between them account for all factors of 1001)

1 * 91 divided by 11 will give us a remainder of 3. This does not work.
2 * 91 divided by 11 will give us a remainder of 6. This does not work.
3 * 91 divided by 11 will give us a remainder of 9. This should work. Let us check this out. 273 is a multiple of 91, 275 is a multiple of 11. 273 * 275 should be a multiple of 1001. 273 * 275 = 75075. 75076 is 274 * 274. But this does not count because it has only 5 digits. Close, but no cigar. Let us take this further

4 * 91 divided by 11 will give us a remainder of 12, which is same as 1 This does not work.
5 * 91 divided by 11 will give us a remainder of 15, which is same as 4 This does not work either
6 * 91 divided by 11 will give us a remainder of 18, which is same as 7 This does not work either
7 * 91 divided by 11 will give us a remainder of 21, which is same as 10 This does not work either
8 * 91 divided by 11 will give us a remainder of 24, which is same as 2. Hello, do we have our third number here?!

8 * 91 = 728. 726 is a multiple of 11. 728 * 726 should be a multiple of 1001. 726 * 728 = 528528. 528529 = 727*727. So, our third number is 528529.

Let us go further, but quicker from now on.

9 * 91 divided by 11 will give us a remainder of 27, which is same as 5 This does not work.
10 * 91 divided by 11 will give us a remainder of 30, which is same as 8 This does not work either.

We do not need to worry about 11 * 91 as that is 1001.

Now, let us move on to numbers that break as 77p * 13q.

We need a multiple of 77 that when divided by 13 gives a remainder of either +2 or + 11. 77 divided by 13 gives a remainder of 12, or -1.

77 * 2, on division by 13 will give us a remainder of -2. This should work. But this will be a waste of time as it will result in a 5-digit number.

So, let us evaluate 77 * 3. This gives a remainder of -3. Not good enough.
Straight away, we can sense that the next number that will work for us is 77 * 11, where we get a remainder of -11, which is nothing but + 2.

77 * 11 = 847. 845 is a multiple of 13. 845 *847 is a multiple of 1001. 847 * 845 = 715715. 846 *846 = 715716 is our fourth number. 

No other possibility exists.

There are 4 possible numbers - 183184, 328329, 528529 and 715716. Fantabulous question to nail down the fact that 1001 = 7 * 11 * 13. 

Since you have been brilliant and diligent enough to get through this far to the solution, I am going to leave you with another nugget. 'abcdabcd' = 'abcd' * 10001.

This 10001 is not prime. It is a product of two primes. Which two? It is not for nothing that we at 2iim say CAT preparation can be fun.

Again, for the nth time, let me reiterate that the above question is way tougher than what we will find in CAT. If you want questions (lots of them) at or around CAT level, visit the questionbank.








Dec 20, 2014

CAT Linear Equations

Question
A system of equations has 3 equations
3x + 4y + 5z = 11, 4x + 5y + 3z = 14 and 2x + 3y + kz = 6.
If the system of equations has no solution, find k.

Explanation
This is a very interesting question. If we can generate one of the equations from the other two, we can then say that the system has infinite solutions. If we can generate one of the equations from the other two, but with the constant part alone being different, this would be akin to having parallel lines when we are dealing with 2 variables and that would result in the system having no solutions. So, lets look for that.

So, we need to find some way where a(3x + 4y + 5z) + b(4x + 5y + 3z) =  2x + 3y + kz.
We need to find k. In other words, we need to find a, b such that a(3x + 4y) + b(4x + 5y ) =  2x + 3y . Then said a, b would give us k.

Or, we are effectively solving for
3a + 4b = 2
4a + 5b = 3

Subtracting one from the other, we get a + b = 1. 3a + 3b = 3. Or, b = -1. a = 2.

Now, k = 5a + 3b = 10 -3 = 7.

If k = 7, this system of equations would result in no solutions.

If k were 7, the system of equations should be 3x + 4y + 5z = 11, 4x + 5y + 3z = 14 and 2x + 3y + 7z = 6.
First equation * 2 - second equation would give us the equation 2x + 3y + 7z = 8.

Now, 2x + 3y + 7z cannot be 6 and 8 at the same time. So, this system of equations has no solution.

Yeah, the more mechanical, rather deceptively straight-forward-looking determinant method is also there. But where is the joy in that.





Oct 31, 2014

CAT Preparation Online - Permutation and Combination

Question
Product of the distinct digits of a natural number is 60. How many such numbers are possible?

Explanation
60 = 2^2 * 3 * 5

60 cannot be written as a product of two single digit numbers. SO, the number in question should either have 3 or more digits.

Three-digit numbers
The digits could be 345 or 265
Digits being 345 - there are 3! such numbers
There are six numbers for each of these outlines. So, there are 3! + 3! = 12 three-digit numbers

Four-digit numbers
The digits could be 1345, 1265 or 2235.
Digits being 1345 - there are 4! such numbers
Digits being 1265 - there are 4! such numbers
Digits being 2235 - this is not possible as digits have to be distinct.

So, there are totally 24 + 24 four-digit numbers possible. 48 four-digit numbers.

Total number of numbers = 12 + 48 = 60.

(this post has been modified to plug error)


Oct 23, 2014

CAT preparation - Ratio and Proportion (Tough)

Question

John has chocolates of types A and B in the ratio 3 : 7, while Mike has chocolates of types B and C in the ratio 5 : 4, Ram has chocolates of types C and A in the ratio 3 : 5. If there are more chocolates of type C than of type B, and more of type B than of type A, what is the minimum possible number of chocolates overall?

Explanation

Again, big thanks to Mukund Sukumar for excellent solution.

Let john have 3x chocolates of type A and 7x of type B
Let Mike have 5y chocolates of type B and 4y of type C
Let john have 3z chocolates of type C and 5z of type A

So in total A=3x+5z ; B=7x+5y ; C=4y+3z

Since C>B we get solving y<3z-7x --->(1)
Since B>A we get solving 5y>5z-4x ---> (2)

What gets inferred from above 2 statements is z>=3. so when x=1,z=3, we get only y=1 as choice, for which second condition doesnt satisfy.

So, when x=1,z=4, we get y<5 from first condition and when y > 3.2 from second condition. so which gives choice the only y=4.

Hence x=1,y=4 and z=4 works and is the best possible answer.

For these values, we get A=23,B=27,C=28.


Minimum possible number of chocolates overall is 76. 

CAT Preparation Online - Tough one from Permutation and Combination

Question

A wonderful, but very tough question from Permutation and Combinations.

In how many ways, can we rearrange the word MONSOON such that no two adjacent positions are taken by the same letter? (Tough one. Tougher than what we will see in CAT)

Explanation

First up, lets get the facts out of the way – The three O’s need to be kept apart, then the 2 N’s. 
Let us focus on the three O’s.

We can place the three O’s in some blanks around the other letters. Or, three O’s can be placed in 3 slots out of the 5 in __M__N__S__N__ . This can be done in 5C3, or 10 ways.

Or, the O’s can be in slots {1, 3, 5} or {1, 3, 6} or {1, 3, 7} or {1, 4, 6} or {1, 4, 7} or {1, 5, 7} or {2, 4, 6} or {2, 4, 7} or {2, 5, 7} or {3, 5, 7}  - Whew.

Now, for each of these arrangements, there are 4!/2! = 12 arrangements for the other 4 letters. But the one thing we need to keep in mind now is the fact that 2 N’s could be adjacent in these arrangements. We will need to eliminate these.

O’s in slots {1, 3, 5} or O__O__O__ __ - Ns could be in the last two slots. There are 2! = 2 words like this. So, number of words that we need to count = 12 – 2 = 10

O’s in slots {1, 3, 6} or O__O__ __O__ - Ns could be two slots 4 and 5. There are 2! = 2 
words like this. So, number of words that we need to count = 12 – 2 = 10

O’s in slots {1, 3, 7} or O__O__ __ __O - Ns could be in the slots {4, 5} or {5, 6}. There are totally 4 words that we need to subtract. So, number of words that we need to count = 12 –  4 = 8

O’s in slots {1, 4, 6} or O__ __O__O__  - Ns could be in the slots {2, 3}. There are 2! = 2 words like this. So, number of words that we need to count = 12 – 2 = 10

O’s in slots {1, 4, 7} or O__ __O__ __O - Ns could be in slots {2, 3} or {5, 6}. There are totally 4 words that we need to subtract. So, number of words that we need to count = 12 –  4 = 8

O’s in slots {1, 5, 7} or O__ __ __O__ O - Ns could be in the slots {2, 3} or {3, 4}. There are totally 4 words that we need to subtract. So, number of words that we need to count = 12 –  4 = 8

O’s in slots {2, 4, 6} or __O__O__O__  - Tehre are no possible slots for N. So, we count all 12 words on this list.

O’s in slots {2, 4, 7} or __O__O__ __ O - Ns could be in slots {5, 6}. There are 2! = 2 words like this. So, number of words that we need to count = 12 – 2 = 10

O’s in slots {2, 5, 7} or __O__ __O__ O - Ns could be in slots {3, 4}. There are 2! = 2 words like this. So, number of words that we need to count = 12 – 2 = 10.

O’s in slots {3, 5, 7} or __ __ O__O__O - Ns could be in the first two slots. There are 2! = 2 words like this. So, number of words that we need to count = 12 – 2 = 10

Total number of words = 10 + 10 + 8 + 10 + 8 + 8 + 12 + 10 + 10 + 10 = 96.
Phew!.

There is a far more elegant method for accounting for the words where the 2 N’s appear together. This one came from Mukund Sukumar.

We need to account for the number of possibilities of N,N being together. So to subtract that part, consider 'NN' being together as one letter and place O's. In 3 out of the 4 slots in _M_NN_S_

The O’s can be selected in 4C3 ways. The MNNS can be rearranged in 3! Ways if the N’s have to appear together.

Or, we get 4C3 * 3! = 24 ways. So, we have 120-24 = 96 ways totally.