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

Apr 29, 2015

CAT Online Coaching - Permutation and Combination, Fixing the Errors III

This post had given a series of questions with incorrect solutions. Given below are the "debugged" solutions to questions 7, 8 and 9.

7. What is the probability of selecting 3 cards from a card pack such that all three are face cards? what is the probability that none of the three is a face card? 

Given solution
Number of cards in a card pack = 52
Numbert of face cards in a card pack = 12
Number of ways of selecting 3 cards from a card pack = 52C3
Number of ways of selecting 3 face cards from a card pack = 12C3

Probability of selecting three cards such that all three are face cards = 12C3/52C3
Probability of selecting three cards such that none of the three are face cards = 1 - 12C3/52C3

Bug in the solution:
Other possibilities exist. As in, if we select three cards from a card pack, all three could be face cards, all three could be non-face cards, one could be a face card with 2 non-face cards or we could have two face cards and one non-face card. This is why we cannot use the 1 minus idea.

As a rule we can say P(A) = 1 – P(B) – P(C) if A, B and C are mutually exclusive and collectively exhaustive events. As in among them they should account for all possible events. And there should be no overlap. Creating a group of MECE equiprobable events is the most fundamentally brilliant idea in all of probability. Go on, look it up.

Correct solution:
This is simple. Probability of selecting three cards such that none of the three are face cards = 40C3/52C3


8. A die is rolled thrice. In how many outcomes will two throws be same and the third one different?

Given solution
Let the three outcomes be ABC.

'A' can take all values from 1 to 6
'B' can also take all values from 1 to 6 
'C' can take all values except A - so it has 5 possibilities

Total number of outcomes = 6 * 6 * 5 = 180.

Bug in the solution:
The given solution is actually absurd. If two throws are to be same, then if A can take values from 1 to 6 and if B were equal to A, then b can take only one value. There can be no 6 * 6 * 5

Correct solution:
'A' can take all values from 1 to 6
'B' should be equal to A --- One possibility 
'C' can take all values except A - so it has 5 possibilities

6 * 1 * 5 = 30 outcomes.

There are 30 possible outcomes when A = B but not equal to C. Likewise, we could have A = C but not equal to B and B = C but not equal to A. So, there are totally 90 different possibilities.

9. How many 7 letter words can we have in English that have two distinct vowels and 5 distinct consonants.

Given solution
Now, we know there are 5 vowels and 21 onsonants. So, we need to select 2 from these 5 and 5 from the remaining 21. Since order is important, we need to select keeping order in mind.

So, we have 5P2 * 21P5.

Bug in the solution:
In this solution we do not account for intermingling of vowels and consonants. As in, we do not count words such as BACEDFG. We account for order within vowels and order within consonants, but we do not account for order across both categories.

Correct solution:
Select without accounting for order, then arrange everything put together

So, we have 5C2 * 21C5 * 7!.

Apr 28, 2015

CAT Online Coaching - Permutation and Combination, Fixing the Errors II


This post had given a series of questions with incorrect solutions. Given below are the "debugged" solutions to questions 4, 5 and 6. The questions and the incorrect solutions here

4. In how many ways can we select 2 cards from a card pack such that both belong to the same suit?

Given solution
The first card can be selected in 52 ways, as it can be any card in the pack. Now, there are 12 different ways of selecting the second card. Depending on the suit of the first card, the choice set we have for the second card gets limited. If the first card were a club, then the second card must be from among the 12 remaining clubs and so on.

So, total number of outcomes = 52 * 12.

Bug in the solution:
We are double-counting when we do this. If we select 2H as the first card and 5D as the second card; this is same as selecting 5D as the first card and 2H as the second card. However, in our current approach, we will end up counting both of these.

Correct solution:
The correct approach would be to select one of the four suits first and then select 2 cards from 13 in that suit. Or, the number of ways of doing this = 4 * 13C2 = 52 * 6.


5. When a coin is tossed 10 times, what is the probability of getting more heads than tails?

Given solution

When a coin is tossed 'n' times, the probability of getting more heads than tails = Probability of getting more tails than heads. So, we do not need to really compute this. Probability = 1/2.

Bug in the solution:
We are not counting the scenarios where there are an equal number of heads and tails. If we threw the coin an odd number of times, the probability of getting more heads than tails will be ½.

Correct solution:
Number of heads could be 6, 7, 8, 9, or 10. Probability = ( 10C6 + 10C7 + 10C8 + 10C9 + 10C10)/ 210

The other way of thinking about this would be ½ (1 – 10C5)/ 210. If we removed the scenario where the number of heads and tails are equal, the probability of more heads than tails should be equal to probability of more tails than heads.

6. In how many ways can we arrange 3 boys and 3 girls on a straight line such that no two boys stand next to each other

Given solution
We can arrange the 6 people as BGBGBG or GBGBGB. If we arranged them as BGBGBG, we would have 3! * 3! ways of arranging the 3 boys and the 3 girls. So, total number of possibilities = 2 * 3! * 3! = 72 ways.

Bug in the solution:
We are not accounting for arrangement such as BGBGGB and BGGBGB. Note that the question says that no two boys should stand next to each other. Two girls can stand next to each other.

Correct solution:

There are 4 possible outlines – BGBGBG, GBGBGB, BGBGGB or BGGBGB. So, total number of possibilities = 3! * 3! * 4 = 144. 

Apr 25, 2015

CAT Online Coaching - Permutation and Combination, Fixing the Errors

This post had given a series of questions with incorrect solutions. Given below are the "debugged" solutions to the first three questions.

1. Five boys need to be allotted to 4 different rooms such that each boy is allotted a room and no room is empty. In how many ways can this be done?

Given solution
Let the boys be A, B, C, D and E. Let the rooms be 101, 102, 103 and 104. Now, we know that exactly one room will have two occupants. First, let us try to send 4 boys to 4 rooms, we can worry about the fifth occupant later on. Let us select 4 out of the 5 boys first. This can be done in 5C4 ways. Now, these 4 can be allotted to 4 different rooms in 4! ways. So, 4 boys in 4 rooms can be done in 5C4 * 4! = 5 * 24 = 120 ways.

Now, the fifth boy has to go into one of the rooms. He can do this in 4 ways as there are 4 different rooms available. So, total number of outcomes = 120 * 4 = 480.

Bug in the solution:
We end up double-counting here.

A, B, C and D could be allotted rooms 101, 102, 103 and 104 in that order. Post this, E could “double-up” with A. So, we would have A and E in 101, B in 102, C in 103 and D in 104.

In another scenario, E, B, C, D could be allotted 101, 102, 103 and 104 in that order. Post this, A could “double-up” with E. So, we would have A and E in 101, B in 102, C in 103 and D in 104.

The two scenarios mentioned above are identical. However, we end up counting both. This is the reason for the double count.

Note that in our method, we end up having a ‘first’ occupant for a room and a ‘second’ occupant. We say, A goes into room number 101 and then E ‘joins’ him. The moment you do that, ‘order’ creeps in. We end up factoring in order when we shouldn’t.

Awesome, isn’t it.

Correct solution:
The boys should be allotted into rooms as 2 + 1 + 1 + 1. As in, exactly one room has 2 occupants. Some two guys have to be room-mates. Let us first select these two room-mates. This can be done in 5C2 ways. After we have selected these two room-mates, we practically need to just allot these 4 ‘groups’ into 4 rooms. This can be done in 4! Ways.

Total number of options = 5C2 * 4! = 10 * 24 = 240 ways.


2. How many 4-digit numbers with 4 distinct digits are possible?

Given solution
Let the 4-digit number be 'abcd'. Now,
'd' can take 10 possible values - 0 to 9. 
'c' can take 9 possible values - 0 to 9 except d
'b' can take 8 possible values - 0 to 9 except d and c
'a' can take 6 possible values - 1 to 9 except d, b and c

So, total number of possibilities = 6 * 8 * 9 * 10 = 4320.

Bug in the solution:
The simple way of stating the bug is as follows “But one of b, c, d might have been zero”.

When we say a can take 6 possible values. We eliminate 0, b, c, and d from the list 0 to 9. If b, c or d were zero, then that in that case, a will still have 7 possible options.

In this question, the leading digit has a constraint. So, start with that. No point factoring in the constraint in the last step. Get that out of the way first.

Correct solution:
Let the 4-digit number be 'abcd'. Now,
'a' can take 9 possible values - 1 to 9. 
'b' can take 9 possible values - 0 to 9 except a
'c' can take 8 possible values - 0 to 9 except a and b
'd' can take 7 possible values - 1 to 9 except a, b and c

Total number of options = 9 * 9 * 8 * 7.


3. In how many ways can we rearrange the letters of the word TWOIIM such that the vowels appear together?

Given solution
Let us take the three vowels together and call it as X. Now, we need to rearrange the letters of the word TWMX. This can be done in 4! ways. Or, there are 24 ways of rearranging the letters of the word TWOIIM with vowels appearing together.

Bug in the solution:
We do not account for the different variations that ‘X’ can come in. Now, the three vowels have been replaced with X. Or, X is nothing but OII in some order. The key point here is that X could be OIO, IOO or OOI. X can take three different forms. The solution has overlooked this.

Correct solution:
Let us take the three vowels together and call it as X. Now, we need to rearrange the letters of the word TWMX. This can be done in 4! ways.

Now, the three vowels have been replaced with X. Or, X is nothing but OII in some order. The key point here is that X could be OIO, IOO or OOI. X can take three different forms.

So total number of possibilities = 4! * 3 = 72 ways.

Apr 12, 2015

CAT Online Preparation - Permutation and Combination

Permutation and Combination is a classcic topic where getting something wrong is often more instructive than getting it right the first time, provided we have another look at what exatly went wrong with the incorrect solution.

To reinforce this idea of "debugging" a wrong solution in order to understand this topic better, I have given a bunch of questions with incorrect solutions that need to be fixed. So, have a go at this. Before you try, let me give a few ground rules.

1. You should try to figure out what exactly is wrong with this solution. It is not enough to say 240 is wrong as 120 is the correct answer. Try to articulate which step of the given solution is wrong. 

2. There might be 1-2 questions where the answer + solution are indeed correct. Otherwise, there is no thrill in this.

3. The best counter-solutions will get published on the blog with due credit to whoever contributed this. There might be some thrill in getting an admit to join IIM A or B or some such, but I am sure it will pale in comparison to getting a badge of honour from this blog. So, go for it.

Now, on to the questions and solutions.

1. Five boys need to be allotted to 4 different rooms such that each boy is allotted a room and no room is empty. In how many ways can this be done?

Solution: Let the boys be A, B, C, D and E. Let the rooms be 101, 102, 103 and 104. Now, we know that exactly one room will have two occupants. First, let us try to send 4 boys to 4 rooms, we can worry about the fifth occupant later on. Let us select 4 out of the 5 boys first. This can be done in 5C4 ways. Now, these 4 can be allotted to 4 different rooms in 4! ways. So, 4 boys in 4 rooms can be done in 5C4 * 4! = 5 * 24 = 120 ways.

Now, the fifth boy has to go into one of the rooms. He can do this in 4 ways as there are 4 different rooms available. So, total number of outcomes = 120 * 4 = 480.

This solution has been debugged here

2. How many 4-digit numbers with 4 distinct digits are possible?

Let the 4-digit number be 'abcd'. Now,
'd' can take 10 possible values - 0 to 9. 
'c' can take 9 possible values - 0 to 9 except d
'b' can take 8 possible values - 0 to 9 except d and c
'a' can take 6 possible values - 1 to 9 except d, b and c

So, total number of possibilities = 6 * 8 * 9 * 10 = 4320.

This solution has been debugged here

3. In how many ways can we rearrange the letters of the word TWOIIM such that the vowels appear together.

Let us take the three vowels together and call it as X. Now, we need to rearrange the letters of the word TWMX. This can be done in 4! ways. Or, there are 24 ways of rearranging the letters of the word TWOIIM with vowels appearing together.

This solution has been debugged here

4. In how many ways can we select 2 cards from a card pack such that both belong to the same suit?

The first card can be selected in 52 ways, as it can be any card in the pack. Now, there are 12 different ways of selecting the second card. Depending on the suit of the first card, the choice set we have for the second card gets limited. If the first card were a club, then the second card must be from among the 12 remaining clubs and so on.

So, total number of outcomes = 52 * 12.

This solution has been debugged here

5. When a coin is tossed 10 times, what is the probability of getting more heads than tails?

When a coin is tossed 'n' times, the probability of getting more heads than tails = Probability of getting more tails than heads. So, we do not need to really compute this. Probability = 1/2.

This solution has been debugged here

6. In how many ways can we arrange 3 boys and 3 girls on a straight line such that no two boys stand next to each other

We can arrange the 6 people as BGBGBG or GBGBGB. If we arranged them as BGBGBG, we would have 3! * 3! ways of arranging the 3 boys and the 3 girls. So, total number of possibilities = 2 * 3! * 3! = 72 ways.

This solution has been debugged here

7. What is the probability of selecting 3 cards from a card pack such that all three are face cards? what is the probability that none of the three is a face card? 

Number of cards in a card pack = 52
Numbert of face cards in a card pack = 12
Number of ways of selecting 3 cards from a card pack = 52C3
Number of ways of selecting 3 face cards from a card [ack = 12C3

Probability of selecting three cards such that all three are face cards = 12C3/52C3
Probability of selecting three cards such that none of the three are face cards = 1 - 12C3/52C3

This solution has been debugged here

8. A die is rolled thrice. In how many outcomes will two throws be same and the third one different?

Let the three outcomes be ABC.

'A' can take all values from 1 to 6
'B' can also take all values from 1 to 6 
'C' can take all values except A - so it has 5 possibilities

Total number of outcomes = 6 * 6 * 5 = 180.

This solution has been debugged here

9. How many 7 letter words can we have in English that have two distinct vowels and 5 distinct consonants.

Now, we know there are 5 vowels and 21 onsonants. So, we need to select 2 from these 5 and 5 from the remaining 21. Since order is important, we need to select keeping order in mind.

So, we have 5P2 * 21P5.

This solution has been debugged here

10. This is an interesting question - Of the 10 questions given here, how many answers are wrong? 

Solution: Can the 10th question have two possible answers?


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.