Demystifying Permutation & Combination - Rajesh Balasubramanian - CAT 100th Percentile - CAT 2011, 2012 and 2014
Permutation and Combination is a wonderful topic to learn. This topic is all about counting. In all other topics, we need to get to an answer, be it average, or speed, or angle, or LCM. In this topic, we will mostly concern ourselves with the idea of counting the number of ways of doing something. In most scenarios we will be enumerating possibilities rather than solving to get an answer.
Before we go further, let us define a few ground rules.
- This topic is based on the simple idea of counting. So, from now on, we will avoid the terms ‘permutation’ and ‘combination’.
- We will build the theory for this topic mostly with examples.
- Wherever possible, we will list and count. Especially, if the answer is less than 10 we will shoot to list out all possibilities.
- nCr, nPr, n! will be resorted to only if absolutely necessary. Counting errors happen when we look to force–fit an idea on to a question. We will use nPr, nCr etc, when we hit the framework. We will not use these as starting points.
Now let us move to first set of questions.
Ram wants to travel from Chennai to Kolkatta (to join IIM Kolkatta). He wants to take only 1 piece of baggage with him. He has 3 types of suitcases and 4 types of back packs. In how many ways can he select his luggage?
This is straightforward. Out of the seven pieces available, he has to select exactly one. If he has suitcases S1, S2, S3 and bags B1, B2, B3 and B4, he can pick one of these 7. So, there are 7 options.
After trying to fit in his luggage, Ram realizes that he needs to carry two pieces of baggage. He plans to carry one suitcase and one backpack. In how many ways can he select his baggage now?
He can select S1 or S2 or S3 and B1, B2, B3 or B4. Totally he has 12 options now.
S1B1, S1B2, S1B3, S1B4
S2B1, S2B2, S2B3, S2B4
S3B1, S3B2, S3B3, S3B4
Fundamental Rule of Counting
If there are ‘m’ ways of doing a task and ‘n’ ways of doing another task, then there are m × n ways of doing both.
If a process can be broken into multiple steps and you have to do each of the many steps, then the total number of ways of doing the process = product of number of ways of doing each step.
AND => ×
Rule of Sum
If there are m ways of doing a task and n ways of doing another task, then the number of ways of doing either of these two (but not both) = m + n. In other words, if we have to do one thing OR another thing, the number of ways = sum of the number of ways of doing each step
OR => +
Number of ways Ram can choose 1 suitcase = 3
Number of ways Ram can choose 1 bag = 4
Number of ways he can choose 1 suitcase OR 1 bag = 3 + 4 = 7
Number of ways he can choose 1 suitcase AND 1 bag = 3 × 4 = 12
Let us take one more example and build counting ideas.
John, who is in charge of creating number plates for cars, has three colors at his disposal – black, white and yellow. He has to paint the number plate with one color and the letters and numbers in another color. In how many ways can he create a number plate?
Again, let us list and count.
- Black plate, white letters
- Black plate, yellow letters
- White plate, yellow letters
- White plate, black letters
- Yellow plate, white letters
- Yellow plate, black letters
There are totally six ways.
Mike has three types of flowers with him – roses, lilies and violets. Mike decides he has to create a bouquet that has two distinct flowers. In how many ways can he create this?
- Rose and Lily
- Lily and Violet
- Rose and Violet
What is the difference?
In the number plate example, we select 2 colors out of 3, in the bouquet example we select 2 flowers out of 3. There are 6 ways of doing the former, but only 3 ways for the latter. What is the difference?
The Idea of Order
The difference is characterised by this term called ‘order’. In the number plate example, ‘black plate–white letters’ is different from ‘white plate–black letters’; whereas in the bouquet example, ‘rose–lily is the same as lily–rose’.
If in a type of selection ‘AB’ is different from ‘BA’, then order is important. If ‘AB’ is same as ‘BA’ then order is not important. Essentially, if the reason for which the selections are made is the same, then order does not matter. In the bouquet example, the flowers are chosen for the ‘same’ bouquet. But in the number plate example, one color is for the background and the other color is for the letters and numbers. Here the reasons are different.
Mike has three types of flowers with him – roses, lilies and violets. Mike decides he has to create a bouquet that has two flowers. In how many ways can he create this?
RL, LV, RV, RR, LL, VV
What is the difference between selecting two distinct flowers and two flowers?
The Idea of Repetition
This difference is based on the idea of repetition. If the same element can be selected again, then we allow ‘repetition’. If we are selecting two flowers, then we can select rose and rose. However, if we are looking for two distinct flowers, then rose–rose is not to be counted.
If in a type of selection ‘AA’ is permitted and should be counted, then repetition is allowed. If ‘AA’ cannot be a legitimate selection, repetition is not allowed.
Understanding the idea of Repetition
A teacher has a chocolate, a biscuit and a cold–drink with her. She says that whoever gets a question correct would get one of the three as award.
Ram gets the first question right. How many options does he have of choosing his award? 3
Krish gets the second question right. How many options does he have of choosing his award? 2
John gets the third question right. He has only one option for choosing the award.
Next day, the teacher follows a new awards scheme. She gives Star rating, Circle rating and Square rating to students who get questions right.
Ram gets the first question right. How many options does he have of choosing his award? 3
Krish gets the second question right. How many options does he have of choosing his award? 3
John gets the third question right. How many options does he have of choosing his award? 3
In the first instance, selection is made without repetition. In the second instance, repetition is allowed. If repetition is not allowed, the choice–set shrinks with every selection that is made. If repetition is allowed, then the choice–set remains the same. At every stage, there are the same n objects to choose from.
Rearrangements
Ram, Krishna and John decide to take part in a race. If there is to be no tie, in how many ways can the three positions on the race be determined?
1st Position | Ram | John | John | Krishna | Krishna |
---|---|---|---|---|---|
2nd Position | John | Ram | Krishna | John | Ram |
3rd Position | Krishna | Krishna | Ram | Ram | John |
For the first slot, there are 3 options, for the second one there are two options, for the third there is only one option. Totally, there are 3 × 2 × 1 = 6 = 3! options.
The number of ways of rearranging r objects is given by r!
A school plans to paint the three floors of its building. The painter can choose from the colour red, blue, yellow, and orange for each floor in the building. In how many ways can he choose the colours to paint the building?
The painter can choose from four colors for the first floor.
The painter can choose from four colors for the second floor.
The painter can choose from four colors for the third floor.
Total number of options = 4 × 4 × 4 = 64
A school plans to paint the three floors in its building. The painter can choose from red, blue, yellow, and orange for each floor in the building. Further he decides that each floor should have a different colour. In how many ways can he choose the colours to paint the building?
The painter can choose from four colors for the first floor.
The painter can choose from three colors for the second floor.
Total number of options = 4 × 3 × 2 = 24
The principal of a school, who is an eccentric person, decides that all three floors should have a color that is a mixture of three colours that the painter has selected. In how many ways can the school be painted?
Now, this is different from the previous question in one key aspect. In the previous question, we select a color for the first floor, one for the second floor and one for the third floor. Here we are going to select 3 colours out of 4 and mix them. Here, a selection of red, blue and green results in an identical outcome as that of a selection of blue, green and red. In other words, order does not matter. The number of ways would be red–blue–yellow, red–blue–orange, red–yellow–orange, and blue–yellow–orange. There are only 4 options totally.
Now, let us see if there is a method to arrive at this answer. Let us look at this by enumerating some options. Look at the following six sequences. These are options that one could have chosen if one were painting each floor with a different colour (as outlined in the previous question).
First | Red | Red | Blue | Blue | Yellow | Yellow |
---|---|---|---|---|---|---|
Second | Blue | Yellow | Red | Yellow | Red | Blue |
Third | Yellow | Blue | Yellow | Red | Blue | Red |
In the case of selecting some set of three colours to get an overall blend, all the 6 options outlined above result in only one end outcome. So, the 4 × 3 × 2 options of the previous question result in (4 x 3 x 2)/6 options for this one. In other words, the number of ways of selecting 3 paints for a blend is (4 x 3 x 2) / ( 3 x 2 x 1) . Why is it 3 × 2 × 1 in the denominator? For every 3 × 2 ×1 outcomes for Question 2, there is only one end outcome when we consider the scenario outlined in Question 3.
What matters in this question is the combination of the colors and not the order. Hence considering the different possible arrangements of a selection is redundant here. And, we know that 3 distinct things can be rearranged in 3! ways; so we need to divide (4 × 3 × 2) by 3! to get the correct answer.
We are going to redefine the questions differently and create a general framework.
A school has to paint the ‘r’ floors in its building. The painter can choose from n different colours for each floor in the building. In how many ways can he choose the colours to paint the building?
From n colours, select one for each floor, ‘r’ number of times. This can be done in
From n options, select ‘r’ such that order is important and repetition is allowed. This can be done in
A school has to paint the ‘r’ floors in its building. The painter can choose from ‘n’ different colours for each floor in the building. Further he decides that each floor should have a different colour. In how many ways can he choose the colours to paint the building?
From n colours, select one distinct one for each of ‘r’ different floors.
From n options, select ‘r’ three such that order is important and repetition is not allowed. This can be done in n (n – 1) (n – 2) n – 3)….up to r terms. This can be re–written as n! / (n - r)! This term is called nPr.
The principal of the school, who is an eccentric, decides that all ‘r’ floors should have the same colour and that colour should be a mixture of some ‘r’ of the ‘n’ colours available. In how many ways can the school be painted?
From n colours, select r and then mix them together to get one blend to be used across the entire school
From n options, select ‘r’ such that order is not important and repetition is not allowed. This can be done in n (n – 1) (n – 2) (n – 3)….up to r terms / (1 × 2 × 3 × …r). This can be re–written as
Also, the number of permutations can be seen as the number of combinations multiplied by the different arrangements possible for each combination. That is, nPr = nCr × r!
Selecting in order = Selecting without order AND Rearranging them
A football team plays a 5–a–side tournament. In all these tournaments, there should be 1 forward, 1 defender, 2–midfielders, and 1 goal keeper. 1 of the 5 should also be the captain of the team. Ram is the coach of team ‘Samba’ which has a squad of only 5 people. Let us say the 5 people are A, B, C, D and E.
In how many ways can Ram select a forward and a defender from this five?
Number of ways of selecting forward = 5.
Number of ways of selecting defender = 4.
Total number of outcomes = 5 × 4 = 20
The selections are as follows:
BA | CA | DA | EA | |
---|---|---|---|---|
AB | CB | DB | EB | |
AC | BC | DC | EC | |
AD | BD | CD | ED | |
AE | BE | CE | DE |
In how many ways can Ram select a goal keeper and captain from this 5?
Number of ways of selecting goal keeper = 5.
Number of ways of selecting captain = 5.
Total number of outcomes = 5 × 5 = 25
The sections are as follows:
AA | BA | CA | DA | EA |
---|---|---|---|---|
AB | BB | CB | DB | EB |
AC | BC | CC | DC | EC |
AD | BD | CD | DD | ED |
AE | BE | CE | DE | EE |
In how many ways can Ram select 2 midfielders from this 5?
Number of ways of selecting two players out of
5 = 5C2 = (5 x 4)/2 = 10.
The selections are as follows
AB | ||||
---|---|---|---|---|
AC | BC | |||
AD | BD | CD | ||
AE | BE | CE | DE |
Technically speaking, the three answers are 5P2, 5^2 and 5C2 respectively. The key difference between selecting forward and defender vis–a–vis two midfielders is that in the former order is important, in the latter order is not important.
PROBLEMS BASED ON DIGITS OF A NUMBER
How many three digit numbers exist? How many of these three–digit numbers comprise only even digits? In how many 3–digit numbers is the hundreds digit greater than the ten’s place digit, which is greater than the units’ place digit?
Three digit numbers range from 100 to 999. There are totally 900 such numbers. There is a simple framework for handling digits questions.
Let three digit number be ‘abc’.
‘a’ can take values 1 to 9 {as the leading digit cannot be zero}.
‘b’ can take values 0 to 9.
‘c’ can take values 0 to 9.
Totally, there are 9 × 10 × 10= 900 possibilities.
Now, three digit number with even digits
Let the three–digit number be ‘abc’.
‘a’ can take values 2, 4, 6 or 8 {as the leading digit cannot be zero}.
‘b’ can take values 0, 2, 4, 6 or 8.
‘c’ can take values 0, 2, 4, 6 or 8.
4 × 5 × 5 = 100 numbers
In how many 3–digit numbers is the hundreds digit greater than the ten’s place digit, which is greater than the units’ place digit?
The digits have to be from 0 to 9. Of these some three distinct digits can be selected in 10C3 ways. For each such selection, exactly one order of the digits will have the digits arranged in the descending order.
So, number of possibilities = 10C3 = 120.
We do not have to worry about the leading digit not being zero, as that possibility is anyway ruled out as a > b > c.
How many 4–digit numbers exist where all the digits are distinct?
Let 4–digit number be ‘abcd’.
‘a’ can take values from 1 to 9. 9 possibilities
‘b’ can take values from 0 to 9 except ‘a’. 9 possibilities
‘c’ can take values from 0 to 9 except ‘a’ and ‘b’. 8 possibilities
‘d’ can take values from 0 to 9 except ‘a’, ‘b’ and ‘c’. 7 possibilities
Total number of outcomes = 9 × 9 × 8 × 7
PROBLEMS BASED ON REARRANGEMENT OF LETTERS OF A WORD
In how many ways can we rearrange the letters of the word ‘MALE’?
In how many ways can we rearrange the letters of the word ‘ALPHA’?
In how many ways can we rearrange the letters of the word ‘LETTERS’?
Number of ways of arranging letters of the word MALE = 4! = 24. (Think about the number of ways of arranging r distinct things).
Now, ‘ALPHA’ is tricky. If we had 5 distinct letters, the number of rearrangements would be 5!, but here we have two ‘A’s.
For a second, let us create new English alphabet with A1 and A2. Now the word A1LPHA2 can be rearranged in 5! ways. Now, in this 5! listings we would count A1LPHA2 and A2LPHA1, both of which are just ALPHA in regular English. Or, we are effectively double–counting when we count 5!. So, the total number of possibilities = 5!/2.
The formula is actually 5!/2!. . Whenever we have letters repeating we need to make this adjustment.
In how many ways can we rearrange the letters of the word ‘LETTERS’? – 7!/2!2!
In how many ways can we rearrange letters of the word ‘POTATO’ such that the two O’s appear together?
In how many ways can we rearrange letters of the word ‘POTATO’ such that the vowels appear together?
The two O’s appear together
Let us put these two O’s in a box and call it X.
Now, we are effectively rearranging the letters of the word PTATX. This can be done in 5!/2! ways.
Now, we need to count the ways when the vowels appear together.
Let us put the three vowels together into a box and call it Y.
We are effectively rearranging PTTY. This can be done in 4!/2! ways.
However, in these 4!/2! ways, Y itself can take many forms.
For instance, a word PTTY can be PTTAOO or PTTOAO or PTTOOA.
How many forms can Y take?
Y can take 3!/2! = 3 forms.
So, total number of ways = 4!/2! × 3!/2! = = 12 × 3 = 36 ways
PROBLEMS BASED ON DICE
Dice questions have a similar framework to digits question. When a die is thrown thrice, we can take the outcomes to be ‘a’, ‘b’, ‘c’. There are two simple differences vis-a-vis digits questions.
- a, b, c can take only values from 1 to 6. In digits we have to worry about 0, 7, 8 and 9 as well
- There are no constraints regarding the leading die. All throws have the same number of options.
So, in many ways, dice questions are simpler versions of digits questions.
In how many ways can we roll a die thrice such that all three throws show different numbers?
Let the throws be ‘a’, ‘b’, ‘c’.
‘a’ can take 6 options – 1 to 6
‘b’ can take 5 options – 1 to 6 except ‘a’
‘c’ can take 4 options – 1 to 6 except ‘a’ and ‘b’
Total number of outcomes = 6 × 5 × 4 = 120
In how many ways can we roll a die thrice such that at least two throws show the same number?
We can have either two throws same or all three same.
There are 6 ways in which all three can be same — (1, 1, 1), (2, 2, 2), (3, 3, 3), (4, 4, 4), (5, 5, 5), (6, 6, 6).
Now, two throws can be same in three different forms a = b, b = c or c = a
a = b –> Number of outcomes = 6 × 1 × 5. ‘a’ can take values from 1 to 6. b should be equal to ‘a’ and c can take 5 values – 1 to 6 except ‘a’
b = c there are 30 possibilities,
and c = a there are 30 possibilities
Total number of options = 6 + 30 + 30 + 30 = 96
In how many ways can we roll a die twice such that the sum of the numbers on the two throws is an even number less than 8?
Sum can be 2, 4 or 6
2 can happen in one way: 1 + 1
4 can happen in 3 ways: 1 + 3, 2 + 2, 3 + 1
6 can happen in 5 ways: 1 + 5, 2 + 4, 3 + 3, 4 + 2,5 + 1
Totally, there are 1 + 3 + 5 = 9 ways.
PROBLEMS BASED ON COIN TOSSES
When a coin is tossed three times, how many ways can exactly one head show up?
When a coin is tossed coin 5 times, in how many ways can exactly 3 heads show up?
When a coin is tossed 5 times, in how many ways can do utmost 3 heads show up?
Three coins are tossed, options with one head are HTT, THT and TTH. 3 ways
5 coins are tossed, three heads can be obtained as HHHTT, HTHTH, TTHHH, …etc. Obviously this
is far tougher to enumerate.
We can think of this differently. All the versions are nothing but rearrangements of HHHTT. This can be
done in 5!/3!2! ways.
Coins questions are common, so it helps to look at them from another framework also.
Let us assume the outcomes of the 5 coin tosses are written down in 5 slots.
Now, suppose, we select the slots that are heads and list them down.
So, a HHHTT would correspond to 123.
HTHTH would be 135.
TTHHH would be 345.
The list of all possible selections is nothing but the number of ways of selecting 3 slots out of 5. This
can be done in 5C3 ways, or, 10 ways.
Number of ways of getting exactly r heads when n coins are tossed = nCr
In how many ways can we toss a coin 5 times such that there are utmost 3 heads?
Utmost 3 heads => Maximum of three heads
Number of ways of having 3 heads = 5C3 = 10
Number of ways of having 2 heads = 5C2 = 10
Number of ways of having 1 head = 5C1 = 5
Number of ways of having 0 heads = 5C0 = 1
Utmost 3 heads = 10 + 10 + 5 + 1 = 26 ways.
When a coin is tossed 6 times, in how many ways do exactly 4 heads show up? Exactly 2 tails?
When a coin is tossed 6 times, what is the total number of outcomes possible?
Coin tossed 6 times, number of ways of getting 4 heads = 6C4 = 15
Exactly two tails = 6C2 = 15
Every outcome where there are 4 heads corresponds to an outcome where there are 2 tails. So, we are
effectively counting the same set of outcomes in both scenarios.
In other words nCr = nC(n–r)
Total number of outcomes = 6C0 + 6C1 + 6C2 + 6C3 + 6C4 + 6C5 + 6C6 = 1 + 6 + 15 + 20 + 15 + 6 + 1 = 64.
This 64 is also
When a coin is tossed once, there are 2 possible outcomes.
When it is tossed 6 times there will be 2 × 2 × 2 × 2 × 2 × 2 =
Therefore, nC0 + nC1 + nC2 + ……….. + nCn =
{This is also seen in the topic ‘Binomial Theorem’. But never hurts to reiterate!}
PROBLEMS BASED ON CARD PACKS
Questions based on card pack are very straightforward. We need to know exactly what lies inside a card pack. Once we know this, everything else falls in place.
A card pack has 52 cards - 26 in red and 26 in black.
There are 4 suits totally, 2 of each colour. Each suit comprises 13 cards - an Ace, numbers 2 to 10, and Jack, Queen and King.
The cards with numbers 2 to 10 are called numbered cards.
Cards with J, Q, K are called Face cards as there is a face printed on them.
In how many ways can we select 4 cards from a card pack such that all are face cards?
There are 12 face cards in a pack. Number of ways of selecting 4 out of these = 12C4
In how many ways can we select 3 cards from a card pack such that none are black numbered cards?
There are 18 black numbered cards. If we select 3 cards and none of these are black numbered cards, then all of these must be from the remaining 34. Number of ways of selecting 3 cards from 34 is 34C3
In how many ways can we select 5 cards from a card pack such that we select at least 1 card from each suit?
We should select 1 card each from 3 of the suits and 2 from the fourth.
The suit that contributes the additional card can be selected in 4C1 ways.
So, total number of outcomes = 4C1 × 13C1 × 13C1 × 13C1 × 13C2
CIRCULAR ARRANGEMENT
Let us say there are n people to be seated around a circular table. In how many ways can this happen? If we think about this as n slots, where n things are to fit in, the answer would be n!. But, what we miss out here is the fact that if every object moves one step to the right/left then this would not be a different arrangement. In fact any rotation of one arrangement is not giving us another arrangement. So, how do we think about this?
Let us fix one person’s position. Then, we have the remaining (n–1) persons who can be arranged in (n–1)! ways.
In how many ways can 6 people be arranged around a circle?
In how many ways can 6 people be arranged around a circle if A and B should never sit together?
Number of ways of arranging n people around a circle = (n –1)!.
So, the number of ways of arranging 6 people around a table = (6 –1)! = 5! = 120.
Now, A and B should never sit together. Let us calculate all the possibilities where A and B do sit together.
Now, A and B can be together called X.
Number of ways of arranging 5 around a circle = 4!.
Now, AB can be sitting such that A is to the left of B or B is to the left of A.
So, total number of options = 4! × 2.
Number of options where A and B do not sit adjacent to each other = 5! – 2 × 4! = 120 – 48 = 72.
SELECTING ONE OR MORE FROM A SET
If there are 4 books and 3 CDs on a table, in how many ways can we select at least one item from the table?
Each article has 2 options, either you can select it or you can skip it.
Total no of option =
Since we need to select at least least one item, we need to subtract this possibility.
Total number of ways =
If there are 4 identical copies of a book and 3 identical copies of a CD on a table, in how many ways can we select at least one item from the table?
We can select either 0, 1, 2, 3 or 4 books. Similarly, we can select 0, 1, 2 or 3 CDs.
So, total number of options = 5 × 4 = 20 ways.
Of these one will include the option of not selecting any of the things.
So, total number of possible outcomes = 4 × 5 – 1 = 19.
Note that here we do not worry about WHICH CD or book we are selecting. Since the CDs and books
are identical, only the number of CDs/books matters
DISTRIBUTION INTO GROUPS
In how many ways can we split 8 different objects into groups of 5 and 3?
In how many ways can we split this into groups of 4, 3 and 1?
In how many ways can we split this into groups of 4, 2, and 2?
Number of ways of splitting 8 different objects into groups of 5 and 3 = 8C5:
Select 5 objects, the remaining 3 form the second group automatically.
You should also note that it is same as selecting 3 objects from 8, 8C3 x 8C5 = 8C3.
8 different objects into groups of 4, 3 and 1:
First select 4 objects – this can be done in 8C4 ways.
Then select 3 out of the remaining 4 – this can be done in 4C3 ways.
Total number of ways = 8C4 × 4C3 = 8!/4!4! x 4!/3!1! = 8!/4!3!1!
So, it follows that p + q + r objects can be split into groups of p, q and r in (p+q+r)!/p!q!r! ways as long as p, q, r are distinct.
8 different objects into groups of 4, 2 and 2:
Now, we need to treat this differently. From 8 objects, number of ways of selecting 4 is 8C4.
Post this, number of ways of selecting 2 out of 4 would be 4C2.
But 8C4 × 4C2 would overstate the number. In the final 4C2, we calculate the number of ways of selecting 2 objects from 4, with the assumption that the remaining 2 would form the other group.
However, let us say we need to select two out of A, B, C, and D. For every selection of AB in the Group 1 and CD for Group 2, we could have an exact mirror selection CD in Group 1 and AB in Group 2. So, the correct answer should be (8C4 x 4C2)/2!.
Every time we split and allocate into groups of same size, we need to be careful.
DISTRIBUTION INTO GROUPS – VARIANTS
In how many ways can 6 identical toys be placed in 3 identical boxes such that no box is empty?
This is simple. Since the toys and boxes are identical, we just need to deal with a ways of splitting six into three natural numbers
1 + 2 + 3 = 6
1 + 1 + 4 = 6
2 + 2 + 2 = 6
These are the three ways in which it can be done.
In how many ways can 6 identical toys be placed in 3 distinct boxes such that no box is empty?
Again, we are looking to solve for a + b + c = 6. But in this case, a (1, 2, 3) will be counted as a separate from (3, 2, 1) and (2, 1, 3).
(1, 2, 3) can be rearranged in 3! = 6 ways
(1, 1, 4) can be rearranged in 3C1 ways = 3 ways.
We need to select which box has the set of 4 toys. The other two boxes will have 1 each. Alternatively, we are thinking about in how many ways we can rearrange 114. This can be done in 3!2! ways.
(2, 2, 2) can be done in only one way.
So, totally we have 6 + 3 + 1 = 10 ways.
Alternative Method
a + b + c = 6. Now, let us place six sticks in a row
| | | | |
This question now becomes the equivalent of placing two ‘+’ symbols somewhere between these sticks. For instance
| | + | | | + |, This would be the equivalent of 2 + 3 + 1. or, a = 2, b = 3, c = 1.
There are 5 slots between the sticks, out of which one has to select 2 for placing the ‘+’s.
The number of ways of doing this would be 5C2 = 10.
Bear in mind that this kind of calculation counts ordered triplets. (2, 3, 1) and (1, 2, 3) will both be counted as distinct possibilities. This is why we use this method for finding the number of ways of placing 6 identical objects in 3 distinct boxes. So, the above question can also be phrased like this: In how many ways can we have ordered triplets of natural numbers (a, b, c) such that a + b + c = 6. There is another version of this question with ordered triplets of whole numbers. Think about what adjustment needs to be done there.
In how many ways can 6 distinct toys be placed in 3 identical boxes such that no box is empty?
First let us think of the distributions.
The boxes can have
1, 2, 3: This can be done in 6C3 × 3C2 ways. First select 3 out of 6, and then 2 out of the remaining 3. This is nothing but distributing 6 as 3, 2, 1 which can be done in 6!/(2! × 3! ×1!)ways
1, 1, 4: This can be done in 6C4 ways. Once we select 4 out of 6, the other two go into one box each. Since the boxes are identical, we do not have to worry about selecting anything beyond the first set of 4 toys.
2, 2, 2: This looks like it could be 6C2 × 4C2 ways. But this will carry some multiple counts. The idea we are using here is simple – select 2 out of 6 and then select 2 out of 4.
When we do this, a selection of AB, and then CD will get counted. This will get accounted as AB, CD, EF. However, we will also be counting a selection of CD, AB, EF, and EF, AB, CD. Since the boxes are identical, all these selections are effectively the same. So, number of ways would be 6C2 x 4C2 / 3!
So, total number of ways of doing this would be 60 + 15 + 15 = 90 ways.
In how many ways can 6 distinct toys be placed in 3 distinct boxes such that no box is empty?
Again, let us start with the distributions.
Scenario I: (1, 2, 3): This can be done in 6C3 × 3C2 × 3! ways. First select 3 out of 6, and then 2 out of the remaining 3. After we have done this, the toys can go into the three distinct boxes in 3! ways. 360 ways
Scenario II: 1, 1, 4: This can be done in 6C4 × 3! ways. Once we select 4 out of 6, the other two go get broken up as 1 and 1. Now, we have something akin to ABCD, E and F to be allotted into 3 distinct boxed. This can be done in 3! ways. 90 ways
Scenario III: 2, 2, 2: This should be 6C2 × 4C2 ways. The idea we are using here is simple – select 2 out of 6 for the first box and then select 2 out of 4 for the second box. 90 ways.
Total number of ways = 360 +90 + 90 = 540 ways.
Now, this question can be rephrased wonderfully like this:
How many onto functions can be defined from {a, b, c, d, e, f} to {1, 2, 3}?
You can solve the above question by thinking of all functions from the first set to the second and subtracting the non–onto functions from that. Needless to say, we would get the same answer.
Factors of a Number
A divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A composite number is a positive integer that has at least one positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number.
Literally prime means ‘of first importance’ and composite means ‘made up of various parts or elements’. Now what a composite number made up of? Prime numbers! All composite numbers can be written as a product of prime factors. This is called as the standard form of a composite number. We can say thatprime numbers are the basic building blocks of all numbers.
For example, 42 can be written as 2 * 3 * 7 and 50 can be written as 2 * 5^{2}
Always keep in mind that 1 is neither prime nor composite. But why 1 is neither prime nor composite?
In number theory, the fundamental theorem of arithmetic states that every integer greater than 1 is either prime itself or can be uniquely written as a product of prime numbers. Take the case of 90. Theorem states that 90 is either a prime or a product of primes. By factorization, we get 90 as product of primes. 90 = 2 * 3* 3 * 5. It also says that the combination of primes will be unique (if we disregard the order of primes). Means 90 can be written as 5 * 3 * 3 * 2 or 3 * 2 * 3 * 5 or any combination we can form using the prime. But there will be always one 2, two 3s and one 5 in the expression, which is unique to 90. If we treat 1 as a prime, then we can bring in any number of ones. We can write 90 as 5 * 3 * 3 * 2 * 1 and 5 * 3 * 3 * 2 * 1 * 1 which are both valid expression for 90 and this violate the unique factorization requirement of fundamental theory. So one is not considered as a prime and as one cannot be represented as a product of primes and hence one is not composite too.
Zero is neither a prime number nor a composite number. It cannot be a prime because it has an infinite number of factors and cannot be composite because it cannot be expressed by multiplying prime numbers.
We can get lot of information related to a number from its standard form. Here we go
Number of factors of a number
If a number N can be represented as P_{1}^{a} * P_{2}^{b} * P_{3}^{c} where P_{1}, P_{2}, P_{3} are prime factors of N then number of factors of N can be found as (a + 1) * (b + 1) * (c + 1).
50 = 2 * 5^{2}, so number of factors of 50 = (1+1) * (2+1) =6. Which are 1, 2, 5, 10, 25and 50. These are various combinations of the prime factors 2, 5 and 5.
Similarly, 792 = 2^{3}* 3^{2}* 11, number of factors = (3+1) * (2+1) * (1+1) = 24
You can see how extensively we use divisibility rules here. For the above problem it won’t take much time to see the number 792 has a factor 2 (ending with even number), factor 4 (last 2 digits divisible by 4), factor 8 (last 3 digits divisible by 8 ), factor 3 (sum of digits divisible by 3), factor 9 (sum of digits divisible by 9) and factor 11 (difference between sum of digits at odd place and sum of digits at even place is zero or multiple of 11, here 0).
To find the standard form divide the number with its prime factors (take highest power of each prime) till we get unity. Then group the powers of all prime factors we used in each step to get the standard form. Confused? It is easy with examples J
Take 544; By using the divisibility rules we can easily see 2, 4, 8 are factors of 544. Take the highest power of each prime (here 8 ) for division.
544/8 = 68, divisible by 2, 4 and 17. Take the highest power of each prime
68/ (4 * 17) = 1.
544 = 8 * 4 * 17 = 2^{5 }* 17
Number of factors = 6 * 2 = 12
Need one more? Take 1080; Applying divisibility rules, we get 2, 3, 4, 5, 8, 9 divides the number. Take the highest power of each prime (here 8, 5, 9) for division.
1080 / (8 * 5 * 9) = 3 (can stop dividing here as we got a prime, no need to write an obvious step to get unity by dividing with the same prime!)
1080 = 8 * 5 * 9 * 3 = 2^{3}* 3^{3}* 5
Number of factors = (3 + 1) * (3 + 1) * (1 + 1) = 4 * 4 * 2 = 32
Sum of factors of a number
40 = 2^{3} * 5, number of factors = (3 + 1) * (1 + 1) = 4 * 2 = 8.
Sum of the factors = 1 + 2 + 4 + 8 + 5 + 10 + 20 + 40 = 90
This is same as (2^{0} + 2^{1} + 2^{2} + 2^{3}) (5^{0} + 5^{1}) = 15 * 6 = 90.
Find the sum of all the powers of each prime numbers, starting from 0 to the highest power contained in the standard form. Product of all such sums will give us the sum of the factors.
Here also it is easy to understand with examples, so here we go.
We have already seen that 1080 = 2^{3} * 3^{3 }* 5
In this case, sum of the factors will be (2^{0 }+ 2^{1} + 2^{2} + 2^{3}) * (3^{0 }+ 3^{1} + 3^{2} + 3^{3}) * (5^{0} + 5^{1})
= 15 * 40 * 6 = 3600
This also explains how we find the numbers of factors. It is the product of the number of factors in each bracket (here, 4 * 4 * 2 = 32).
Product of factors of a number
N = P_{1}^{a} * P_{2}^{b} * P_{3}^{c }
Then the product of all the factors of N = N ^{(a + 1) (b + 1) (c + 1)/2}
e.g. 50 = 2 * 5^{2}; Product of all factors of 50 = 50 ^{(6) / 2} = 50^{3}
Number of odd factors
To get the number of odd factors, ignore the powers of 2.
Take 1080, 1080 = 2^{3} * 3^{3} * 5
Number of odd factors of 1080 = (3 + 1) * (1 + 1) = 4 * 2 = 8, here we considered only the powers of 3 and 5 to get the number of odd factors.
Sum of odd factors of a number
Sum of factors of 1080 = (2^{0 }+ 2^{1}+ 2^{2}+ 2^{3}) * (3^{0}+ 3^{1}+ 3^{2}+ 3^{3}) * (5^{0}+ 5^{1}), where each term in the expansion represents a factor of 1080.
We need at least one 2 to get an even factor. Remove all terms that has a 2 in it and we will remove all even factors. Even factors in 1080 are 2^{1}, 2^{2}and 2^{3}. The only power of 2 remaining is 2^{0 }(=1), which can be removed as it will not make any impact. Means, you ignore all powers of 2 to get the sum of all odd factors.
Now we need to remove even factors from the expression so that the result will be the sum of all odd factors.
Sum of odd factors of 1080 = (3^{0}+ 3^{1}+ 3^{2}+ 3^{3}) * (5^{0}+ 5^{1}) = 240
Number of even factors of a number
Let a number is of the form, N = 2^{a} * P_{2}^{b} * P_{3}^{c}…
Then Number of even factors of N = a * (b + 1) * (c + 1) …
For e.g. 1080 = 2^{3 } * 3^{3} * 5
Number of even factors of 1080 = 3 * (3 + 1) * (1 + 1) = 24
Sum of even factors of a number
To get the sum of the even factors we need to ensure that all the terms in the expression for the sum of factors are even. All members in the 2’s bracket except 2^{0}will give an even number. Remove 2^{0 }from the group and that’s all it takes!
For e.g. 1080 = 2^{3 } * 3^{3} * 5
Sum of even factors of 1080 = (2^{1} + 2^{2 }+ 2^{3}) * (3^{0 }+ 3^{1} + 3^{2 }+ 3^{3}) * (5^{0 }+ 5^{1}) = 3360
Other conditions
What if we are asked to find the sum and number of factors of 1080 which are divisible by 15?
We don’t have to use anything else other than the logic we used for odd and even factors. We know number of terms in the expression is the number of factors. So when a condition is given, number of factors is the number of terms in the expression satisfying the given condition and considers only those factors to get the sum.
1080 = (2^{0 }+ 2^{1}+ 2^{2}+ 2^{3}) * (3^{0}+ 3^{1}+ 3^{2}+ 3^{3}) * (5^{0}+ 5^{1})
Now 15 = 3 * 5, so we need to ensure that every term in the expression has a 3 and 5 in it. Now look at the bracket of 3 and find the terms that don’t yield a 3 in the expression. Also check for bracket of 5 for the terms that don’t give us a 5. 3^{0}and 5^{0}are the culprits. Remove those entries and we get the expression we need.
Sum of factors of 1080 which are divisible by 15
= (2^{0 }+ 2^{1}+ 2^{2}+ 2^{3}) * (3^{1}+ 3^{2}+ 3^{3}) * (5^{1})
= 15 * 39 * 5 = 2730
Find the sum of factors of 544 which are perfect squares
544 = 8 * 4 * 17 = 2^{5 }* 17
Our expression, (2^{0}+ 2^{1}+ 2^{2}+ 2^{3}+2^{4 }+2^{5}) (17^{0}+17^{1})
Ensure all terms in the expression satisfy the condition, perfect squares. So each term in the expression should be of even power. We have to remove all odd powers in the expression
Required sum is (2^{0}+ 2^{2 }+2^{4}) (17^{0}) = 21.
Number of factors = 3 * 1 (number of terms in each bracket) = 3.
For the number 1000 find the below values
The number of divisors = (3 + 1) * (3 + 1) = 16 (as 1000 = 2^{3}* 5^{3})
The product of divisors = 1000^{16/2 }= 1000^{8}
The sum of divisors= (2^{0}+ 2^{1}+ 2^{2}+ 2^{3}) (5^{0 }+ 5^{1}+ 5^{2}+ 5^{3}) = 2340
The sum and number of odd divisors
we need to remove all factors that can yield a 2 from the two’s bracket.
Sum of odd factors = ( 2^{0}) * (5^{0}+ 5^{1}+ 5^{2}+ 5^{3}) = 156
Number of odd factors = 1 * 4 = 4
The sum and number of even divisors
We need to remove all factors that cannot yield a 2 from the two’s bracket (which is 2^{0})
Sum of even factors = (2^{1}+ 2^{2}+ 2^{3}) (5^{0}+ 5^{1}+ 5^{2}+ 5^{3}) = 2184
Number of even factors = 3 * 4 = 12
The sum and number of divisors which are perfect squares
We need to remove all the factors which are not perfect squares
Sum of factors which are perfect squares = (2^{0}+ 2^{2 }) (5^{0}+ 5^{2}) = 130
Number of factors which are perfect squares = 2 * 2 = 4
The sum and number of divisors which are not perfect squares
Total sum – sum of divisors which are perfect squares = 2340 – 130 = 2210
Total factors – number of divisors which are perfect squares = 16 – 4 = 12
The sum and number of divisors which are divisible by 125
We need to remove all the factors that cannot yield 125 (125 = 5^{3})
Sum of factors which are divisible by 125 = (2^{0}+ 2^{1}+ 2^{2}+ 2^{3}) (5^{3}) = 1875
Number of factors which are divisible by 125 = 4 * 1 = 4
The sum and number of divisors which are divisible by 100
100 = 2^{2 }* 5^{2 }
We need to remove all factors that cannot yield a 2^{2 }from two’s bracket and also remove all factors that cannot yield a 5^{2 }from five’s bracket.
Sum of factors which are divisible by 100 = (2^{2}+ 2^{3}) (5^{2}+ 5^{3}) = 1800
Number of factors which are divisible by 125 = 2 * 2 = 4
Co Primes
We will end this chapter with a very useful concept, co primes. A co prime is a number which has no common prime numbers in their standard form. 20 = 2^{2 }* 5 and 21 = 7 * 3, no common primes hence 20 and 21 are co primes. (Two consecutive integers will always be co prime)
The number of integers co prime to a positive integer n, within the range [1, n-1], is given by Euler's phi function (phi)
If a number N = P_{1}^{a} * P_{2}^{b }* P_{3}^{c} then phi(N) = N ( 1 - 1/ P_{1}) ( 1 - 1/ P_{2}) ( 1 - 1/ P_{3})
Consider 6, 6 = 2 * 3
Phi (6) = 6 (1 – 1/2) (1 – 1/3) = 6 *1/2 * 2/3 = 2, means there are 2 numbers between 1 and 6 which are co prime to 6. (1 and 5). The numbers 1 and -1 are coprime to every integer, and they are the only integers to be co prime with 0.
Take another example, 24; 24 = 2^{3} * 3
phi(24) = 24 ( 1 – 1/2) (1 – 1/3) = 24 * 1/2 * 2/3 = 8. There are 8 numbers between 1 and 24 which are co prime to 24. (1, 5, 7, 11, 13, 17, 19, 23)
One more example, 36; 36 = 2^{2 }* 3^{2}
phi(36) = 36 ( 1 – 1/2) (1 – 1/3) = 36 * 1/2 * 2/3 = 12 . There are 12 numbers less than 36 and co prime to 36. (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35)
If a and b are relatively prime, then
- 2^{a} -1 and 2^{b} -1 are also relatively prime.
- There exist integers x and y such that ax + by = 1 (Bézout’s identity)
- Any powers a^{j} and b^{k} are also co prime.
Happy Learning :-)
HCF & LCM fundas
HCF and LCM are among the initial ‘complicated’ stuffs we dealt with as a student. Someone taught me once that HCF is a postman who can go and meet all of the given numbers to deliver their letters. And LCM is like a postmaster to whom all the given numbers can go in case of any issue. Highest common factor (HCF), also known as GCD (Greatest common divisor) of a group of numbers is the greatest number that can exactly divide all the numbers in the group. Least Common Multiple (LCM) of a group of numbers is the smallest number which can be divided by all the numbers in the group.
Finding HCF of given numbers
Factorization Method
Find the HCF of 100, 225 and 900
Represent each number in their standard form.
100 = 2^{2 }* 5^{2}
225 = 3^{2} * 5^{2}
900 = 2^{2} * 3^{2} * 5^{2}
what is common in all of them, 5^{2}. HCF (100, 225, 900) = 25.
So 25 is the largest integer that can completely divide 100, 225 and 900.
Division Method:
To find the HCF of two given numbers, divide the largest by the smallest number, and then divide the dividend by the remainder. Repeat this until remainder is zero. The last dividend is the HCF of the two numbers.
Find HCF of 27 & 36
Step1: Divide 36/27, remainder = 9
Step2: Divide dividend by remainder
27/9, remainder = 0
So the HCF or GCD (greatest common Divisor) of 27 and 36 is 9
To find the HCF of three given numbers
Calculate the HCF of 2 numbers, then HCF of the result with 3rd number.
Find the GCD of 100, 225, & 900 by Successive Division Method
Phase1: Find GCD of two numbers (here 900 and 100)
Step 1: Divide the largest number 900 by the smallest number 100. And this division gives us a remainder 0 and the divisor is the GCD of 100 and 900 = 100.
Phase2: Find the GCD of 100(GCD of 900 & 100) & 225(given number)
Step 1: Divide the remaining given number 225 by the GCD of 100 & 900 i.e.100.
Step 2: Division in Step 1 gives us remainder 25. Divide the dividend (100) again by remainder (25), which gives us a remainder 0 and the divisor (25) is our GCD.
GCD of 100, 225 and 900 = 25
Finding LCM of given numbers
Factorization method
Find the LCM of 100, 225 and 900
100 = 2^{2 }* 5^{2}
225 = 3^{2 }*5^{2}
900 = 2^{2 }* 3^{2 }* 5^{2}
Write down all the prime factors that appear at least once in any of the number and then raise it to their highest available power. Product of them will give you the LCM. Using this logic in our above problem, LCM = 2^{2 }* 3^{2 }* 5^{2} = 900. Which means 900 is the smallest number which can be completely divided by the numbers 100, 225 and 900.
Division method
Write the given numbers as shown below and divide them with the prime numbers that can exactly divide one or more of the given numbers. On division, write the quotient in each case below the number. If any number is not divisible by its respective divisor, it is to be written as such in the next line. Keep on dividing the quotient until you get 1(as quotient of all). Multiply all the divisors to get LCM of given numbers.
Find LCM of 100, 225 and 900
5 | 100 225 900
5 | 20 45 180
2 | 4 9 36
3 | 2 3 6
2 | 1 3 3
3 | 1 1 1
LCM (100, 225, 900) = 3 * 2 * 3 * 2 * 5 * 5 = 900.
We can extend division method to find GCD or LCM of any given numbers. It is much easier and time saving to use the prime factorization method as once we write the numbers in their standard form we can get the answer just by visual inspection. Only thing we need is the speed and accuracy to write the standard form of the number, which comes through practice. In case of division method for LCM a closer look will show you that we are just using standard form method in another way.
LCM for comparing fractions
Find the L.C.M. of the denominators of the given fractions. Convert each of the fractions into an equivalent fraction with L.C.M. as the denominator, by multiplying both the numerator and denominator by the same number. The resultant fraction with the greatest numerator is the greatest.
Which one is greater 10/9 or 7/6?
LCM of denominator = 18.
Make denominator same as the LCM for the both the fractions
20/18, 21/18 second one has the highest numerator hence the highest fraction is 7/6.
HCF and LCM of decimal numbers
In given numbers, make the same number of decimal places by annexing zeros in some numbers, if necessary. Considering these numbers without decimal point, find H.C.F. or L.C.M. as the case may be. Now, in the result, mark off as many decimal places as are there in each of the given numbers.
Find the HCF and LCM of 0.12 and 0.3
Add one zero to 0.3 so that we have same number of decimal places, 0.12 and 0.30, consider these numbers without decimals i.e. 12 and 30 and find HCF (6) and LCM (60). Mark as many decimals we removed (here 2). So the answer is HCF = 0.06 and LCM = 0.6
Useful concepts
HCF (n_{1,} n_{2}) * LCM (n_{1,} n_{2}) = n_{1 }* n_{2 }(works only for TWO numbers)
LCM of fractions = LCM of numerators/HCF of denominators.
HCF of fractions = HCF of numerators/LCM of denominators.
Two numbers are co primes if their HCF is 1.
LCM is always greater than or equal to the biggest among the given numbers.
HCF is always less than or equal to the smallest among the given numbers.
Some regular scenarios asked from HCF / LCM
Find the GREATEST NUMBER that will exactly divide x, y, z.
Required number = H.C.F. of x, y and z.
Find the GREATEST NUMBER that will divide x, y & z leaving remainders a, b and c respectively.
Required number = H.C.F. of (x – a), (y – b) and (z – c).
Find the LEAST NUMBER which is exactly divisible by x, y and z.
Required number = L.C.M. of x, y and z
Find the LEAST NUMBER which when divided by x, y and z leaves the remainders a, b and c respectively. It is always observed that (x – a) = (z – b) = (z – c) = K (say).
Required number = (L.C.M. of x, y and z) – K.
Find the LEAST NUMBER which when divided by x, y and z leaves the same remainder ‘r’ each case.
Required number = (L.C.M. of x, y and z) + r.
Find the GREATEST NUMBER that will divide x, y and z leaving the same remainder in each case.
Required number = H.C.F of (x – y), (y – z) and (z – x).
Try out the above formulae by taking some arbitrary numbers and also try to understand why it works. And most importantly share them too.In our exams, we may not find a problem directly asking to find the HCF and LCM. But questions where we need to apply the concept of HCF and LCM are very common.
The front wheels of a toy truck are 4 inches in circumference. The back wheels are 7 inches in circumference. If the truck travels in a straight line without slippage, how many inches will the truck have traveled when the front wheels have made 12 more rotations than the back wheels?
(A) 112 (B) 64 (C) 48 (D) 36 (E) 28
Front wheel covers 4 inches in one rotation and back wheel covers 7 inches for one rotation. Distance travelled by the truck will be an integral multiple of the LCM of 4 and 7 (distance covered by front wheel and back wheel for each of their rotation). LCM of 4 and 7 is 28 (4 and 7 are co primes hence HCF is 1. We can get LCM by multiplying the given numbers as HCF * LCM = Number1 * Number2) Only options that can be written as 28n are 112 and 28.
If 28, front wheel will make 7 rotations and back wheel will make 4 rotations.
Difference is 3. Not our answer.
If 112, front wheel will make 28 rotations and back wheel will make 16 rotations.
Difference is 12… our answer :)
If options are not available, then we can see that for each 28 inch (LCM) covered by the truck the difference between the number of rotations made by the front wheel and back wheel will be 3 more than the previous value, which is nothing but the difference of the given numbers divided by their HCF (here HCF = 1). Means for the first revolution, front wheel will make 7 rotations and backwheel will make 4 rotations. Difference is 3… for the second revolution difference will be 6 and so on… going with this trend after the truck covers 28 inches for fourth time the difference will be 4 * 3 = 12. So the required distance is 4 * 28 = 112.
Happy Learning :-)
Factorials
Factorial is an important topic in quantitative aptitude preparation not just because of its importance as an independent concept, but also because of its application in many topics like permutation & Combination, Probability etc… The factorial of a non negative integer n is denoted as n! The notation was introduced by Christian Kramp in 1808.
n! is calculated as the product of all positive integers less than or equal to n.
i.e 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720
n! = 1 when n = 0, and n! = (n-1)! * n if n > 0
What is the significance of n!
n! is the number of ways we can arrange n distinct objects into a sequence.
2! = 2 means numbers 1, 2 can be arranged in 2 sequences (1, 2) and (2, 1).
We can arrange 0 in one way. So 0! = 1, not zero. Now we know why, and no need to say “its like that” if someone asks ;-)
Find the highest power of a prime number in a given factorial
The highest power of prime number p in n! = [n/p^{1}] + [n/p^{2}] + [n/p^{3}] + [n/p^{4}] + …
[x] denotes the greatest integer less than or equal to x.
[1.2] =1
[4] = 4
[-3.4] = -4 (why? Because -4 is less than -3.2)
Find the highest power of 3 in 100!
= [100/3] + [100/3^{2}] + [100/3^{3}] + [100/3^{4}] + [100/3^{5}] + …
= 33 + 11 + 3 + 1 + 0 (from here on greatest integer function evaluates to zero)
= 48.
What is the greatest power of 5 which can divide 80! exactly (Another way of asking what is the highest power of 5 in 80!)
= [80/5] + [80/5^{2}] + [80/5^{3}] + …
= 16 + 3 + 0 + … = 19.
Find the highest power of a non prime number in a given factorial
We learnt before that any non prime number can be expressed as a product of its prime factors. We will use this concept to solve this type of questions.
What is the greatest power of 30 in 50!
30 = 2 * 3 * 5.
Find what the highest power of each prime is in the given factorial
We have 25 + 12 + 6 + 3 + 1 = 47 2s in 50!
16 + 5 + 1 = 22 3s in 50!
10 + 2 = 12 5s in 50!
We need a combination of one 2, one 3 and one 5 to get 30. In the given factorial we have only 12 5s. Hence only twelve 30s are possible. So the greatest power of 30 in 50! is 12.
Note: We don’t have to find the power of all prime factors of a given number. It is enough to find the greatest power of the highest prime factor in the factorial (here 5).
What is the greatest power of 8 in 50!
8 =2^{3}
50! has 47 twos. We need 3 two to get an 8.
We can have a maximum of [47/3] = 15 8s in 50!
Note: The highest power of the number p^{a} in n! = [Highest power of p in n!]/a
n! in its standard form
Find the highest power of all prime numbers, less than n, in n!
What are the number of factors of 15!
2, 3, 5, 7, 11 and 13 are the prime numbers less than 15.
Highest power of 2 in 15! = 11
Highest power of 3 in 15! = 6
Highest power of 5 in 15! = 3
Highest power of 7 in 15! = 2
Highest power of 11 in 15! = 1
Highest power of 13 in 15! = 1
15! = 2^{11 }* 3^{6 }* 5^{3 }* 7^{2}* 11^{1 }* 13^{1}
Thus we can find the number of divisors, sum of divisors and other values for 15!
number of factors of 15! = (11 +1) (6 + 1) (3 + 1) ( 2 + 1) ( 1 + 1) (1 + 1) = 4032
Find the number of zeros at the end of a factorial value
This is just another way of asking what highest power of 10 is in a given factorial.
10 = 2*5, we need a combination of one 2 and one 5 to get a zero at the end. Just find the number of 5s in the given factorial as number of 2s will be always more than number of 5s.
Find the number of zeros at the end of 100!
[100/5] + [100/25] + … = 20 + 4 + 0 + … = 24.
Find the number of zeros at athe end of 100! in base 7
Concept is same as before. in base 10 we need a 2 and 5 to get a zero but in base 7 we need a 7 to get a zero. so we have to find the highest power of 7 in 100!
[100/7] + [100/49] + ... = 14 + 2 = 16. There will be 16 zeros at the end of 100! in base 7
Note: To find the number of zeros of a factorial in a base b, calculate the highest power of b in that factorial. b need not be prime, we already know how to find the highest power of a composite number in a factorial expression.
So how many trailing zeros are there in 500! in base 9 ?
Wilson's theorem
For every prime number p, (p-1)! + 1 is divisible by p
take p =7, then as per Wilson's theorem 7 is prime only if (6!) + 1 is divisible by 7 and it is :-)
some useful results derived from Wilson's theorem
Remainder [ (p-1)!/p] = p - 1 ( where p is a prime number )
Remainder [ 6!/7 ] = 7; Remainder [100!/101] = 100 and so on...
Remainder [ (p-2)!/p] = 1 ( where p is a prime number )
Remainder [ 5!/7 ] = 1; Remainder [99!/101] = 1 and so on...
Some extra concepts
Product of n consecutive natural numbers is divisible by n!
11 * 12 * 13 * 14 is completely divisible by 4!
This can be extended to obtain other interesting results.
consider 1 * 2 * 3 * 4 * 5 * 6 . as per above result 1 * 2 * 3 * 4 * 5 * 6 is divisible by 6!.
now take ( 1 * 2 * 3 ) * ( 4 * 5 * 6 ) . each of this is divisible by 3!
so 1 * 2 * 3 * 4 * 5 * 6 is completely divisible by (3!)^{2 }
similarly 1 * 2 * 3 * 4 * 5 * 6 is completely divisible by (2!)^{3}also.
Note: To generalise (a*n)! is completely divisible by (n!)^{a}, where a and n are integers.
The product of all odd (even) integers up to an odd (even) positive integer n is called the double factorial of n. (though it has only about half the factors of the original factorial!). It is denoted as n!!
9!! = 1 * 3 * 5 * 7 * 9 = 945
8!! = 2 * 4 * 6 * 8 = 384
Product of first n! is called the super factorial of n, denoted as sf(n)
sf(4) = 1! * 2! * 3! * 4!
A factorion is a natural number that equals the sum of the factorials of its decimal digits.
For example, 145 is a factorion because 1! + 4! + 5! = 1 + 24 + 120 = 145.
Note: There are just four factorions (in base 10) and they are 1, 2, 145 and 40585.
A factorial prime is a prime number that is one less or one more than a factorial
2 = 1! + 1, 3 = 2! + 1, 5 = 3! -1, 7 = 3! + 1 etc…
In the chapter Know your Numbers, we saw Triangular numbers where instead of multiplying the numbers, we added n consecutive numbers... Remember why it is called as Triangular numbers ?
The first triangular number is 1.
The second one is 1 + 2 = 3.
The third triangular number is 1 + 2 + 3 = 6 and so on.
We can calculate the nth triangular number using the formula [(n) (n+1)]/2
Happy Learning :-)
Remainder Theorem
Remainder theorem is a very important topic in number system and can be learnt easily. We will try to learn some interesting concepts regarding remainders with examples. Here we go!
Definition of remainder
If a and d are natural numbers, with d # 0, it can be proved that there exist unique integers q and r, such that a = qd + r and 0 ≤ r < d. The number q is called the quotient, while r is called the remainder. Dividend = Divisor × Quotient + Remainder. |
if r = 0 then we say that a is perfectly divisible by d or d is a factor of a. For example, we say 8 is a factor of 40 because 40 leaves a remainder 0 with 8.
By definition remainder cannot be negative. |
Now just to give an example, 17 = 3 * 5 + 2, which means 17 when divided by 5 will give 2 as remainder. Well that was simple!
Find Remainder[ (12 * 13 * 14) / 5 ]
Remainder [ (12 * 13 * 14) / 5 ]
= Remainder [2184/5] = 4. But this method is not the right one for us :)
In order to find the remainder of an expression find the individual remainder and replace each term with the respective remainders. Eg: Remainder[(100 + 30 * 4 - 8 ) / 7] = Remainder[(Remainder[100/7] + Remainder[30/7] * Remainder[4/7] - Remainder[8/7] ) / 7 ] = Remainder[(2 + 2 * 4 - 1)/7] = Remainder[9/7] = 2 |
In the above case 12, 13 and 14 will give remainders 2, 3 and 4 respectively when divided by 5. So replace them with the respective remainders in the expression and find the remainder again.
Remainder [ (12 * 13 * 14) / 5 ] = Remainder[(2 * 3 * 4) / 5] = Remainder[ 24 / 5 ] = 4.
Note:
One common mistake while dealing with remainders is when we have common factors in both dividend and divisor. Example, what is the remainder when 15 is divided by 9
15 / 9 is same as 5 / 3, remainder 2. Correct? No 15/9 will give a remainder of 6.
Where we slipped?
Always remember that if we find remainder after cancelling common terms make sure we multiply the remainder obtained with the common factors we removed.
In previous case we will get correct answer (6) when we multiply the remainder obtained (2) with the common factor we removed (3).
What is the remainder of 1421 * 1423 * 1425 when divided by 12 ? ( CAT 2000 )
1421, 1423 and 1425 gives 5, 7 and 9 as remainders respectively when divided by 12.
Remainder [ (1421 * 1423 * 1425 ) / 12 ] = Remainder [ (5 * 7 * 9) ] / 12, gives a remainder of 3.
Find the reminder when 1! + 2! + 3! + . . . . .. . .. 99! + 100! is divided by the product of first 7 natural numbers
From 7! the remainder will be zero. Why ? because 7! is nothing but product of first 7 natural numbers and all factorial after that will have 7! as one of the factor. so we are concerned only factorials till 7!, i.e, 1! + 2! + 3! + 4! + 5! + 6!
1! + 2! + 3! + 4! + 5! + 6! = 873 and as 7! > 873 our remainder will be 873
What is the remainder when 64^{999 }is divided by 7? (GMAT Type Question)
Many of us get intimidated with such numbers, always remember that the key to crack quant is a strong hold of basic concepts.
Remainder [64^{999 }/ 7 ] = Remainder[ 64 * 64 * …. 64 (999 times) / 7 ]
Remainder[64/7] = 1, hence Remainder [64^{999 }/ 7 ] = Remainder [ 1 ^{999 }/ 7 ] = 1
What is the remainder when 444^{444}^{ ^ 444} is divided by 7 ? (GMAT Type Question)
Remainder[444/7] = 3
Remainder[ 444 ^{444 ^ 444 }/ 7 ] = Remainder [ 3 ^{444 ^ 444 }/ 7 ]
= Remainder [ ( 3^{2 }) ^{222 ^ 444 }/ 7 ] = Remainder [ 2^{222 ^ 444 }/ 7 ] ( As Remainder [ 3^{2 }/ 7 ] = 2 )
= Remainder [ ( 2^{3} ) ^{74 ^ 444 }/ 7] = Remainder [ 1 ^{74 ^ 444 }/ 7 ] = 1 ( As Remainder [ 2^{3 }/ 7 ] = 1 )
Concept of negative remainder
We saw earlier that by definition remainder cannot be negative. But considering negative remainder is a very useful exam trick.
For example,
What is the remainder when 2^{11} divided by 3?
The easiest method for this one will be using the concept of negative remainders.
Here 2 when divided by 3 gives a remainder of -1. (Say)
2 = 3 * 1 + (-1), remainder is -1, which is theoretically incorrect but let’s cheat!
So we are asked to find (-1) * (-1) * … 11 times divided by 3.
Which is Remainder[-1/3] = -1.
Whenever you are getting negative number as a remainder, make it positive by adding the divisor to the negative remainder. |
Here required answer is 3 + (-1) = 2.
Remainder when (41 * 42) is divided by 43
Use negative remainder concept,
Remainder [ 41 * 42 / 13 ] = Remainder[(-2) * (-1) / 43 ]( as 41 = 43 * 1 – 2 and 42 = 43 * 1 – 1)
= Remainder [ 2 /43 ] = 2 (here we got a positive remainder itself, so no need of correction)
Some useful concepts while dealing with remainder are given below.
Remainder[(ax + 1)^{n }/ a] = 1 for all values of n. |
Find the remainder when 100^{99 }is divided by 11
Remainder[100^{99 }/ 11 ] = Remainder[(11* 9 + 1)^{99 }/ 11] = 1.
Remainder[(ax - 1)^{n }/ a ] = 1 when n is even Remainder[(ax - 1)^{n }/ a ] = (a-1) when n is odd. |
Find the remainder when 21^{875 }is divided by 17.
Remainder[21 / 17] = 4, so we need to find Remainder[4^{875}/ 17]
4^{2 }= 16 = (17 – 1), we can write the expression as Remainder[(4^{2})^{437 }* 4 / 17]
= Remainder[(17 – 1)^{437 }* 4 / 17] = Remainder[(17-1) * 4 / 17] = Remainder[64 / 17] = 13.
Remainder[(a^{n }+ b^{n}) / (a + b) ] = 0 when n is odd. |
Remainder[(2^{101 }+ 3^{101}) / 5 ] = 0
What is the remainder when 15^{23 }+ 23^{23 }is divided by 19 ? ( CAT 2004 )
15^{23 }+ 23^{23 }is divisible by 15 + 23 = 38 ( as 23 is odd).
So Rem[(15^{23 }+ 23^{23})/19] = 0
Remainder[(a^{n }+ b^{n} + c^{n} + ...) / (a + b + c + ...) ] = 0 if ( a + b + c + ... are in Arithmetic progression and n is odd |
What is the remainder when 16^{3 }+ 17^{3 }+ 18^{3 }+ 19^{3} is divided by 70 ? ( CAT 2005 )
Apply the above funda. Here n =3 ( odd ), 16 + 17 + 18 + 19 = 70 and 16,17,18 and 19 are in AP. Remainder is 0
Remainder[(a^{n }- b^{n}) / (a + b) ] = 0 when n is even. |
Remainder[(5^{100 }– 2^{100}) / 7] = 0
Remainder [(a^{n }- b^{n}) / (a - b) ] = 0 |
Now we can say Remainder[(101^{75 }– 76^{75}) / 25] = 0 in no time..!
The remainder when f(x) = a + bx + cx^{2}+ dx^{3}+ … is divided by (x-a) is f(a) |
Rem [(3x^{2 }+ 4x + 1) / (x-2)] = f(2) = 3 * 2^{2 }+ 4 * 2 + 1 = 21
Cyclic property of remainders
Sometimes it is easy to find the remainder by using the cyclic property of remainders, remainders forming a pattern.
As a thumb rule if we divide p^{n }with q, the remainder will follow a pattern. |
For example,
Remainder [ 2^{1 }/ 3 ] = 2, Remainder [ 2^{2} / 3 ] = 1, Remainder [ 2^{3 }/ 3 ] = 2, Remainder [ 2^{4 }/ 3 ] = 1 and so on.
Pattern repeats in cycles of 2. Remainder [ 2^{n }/ 3 ] = 2 when n is odd and 1 when n is even.
With this information, we can find Remainder [ 2^{3276 }/ 3 ] = 1 very quickly.
One more, Remainder [ 9^{1} / 11 ] = 9, Remainder [ 9^{2} / 11 ] = 4, Remainder [ 9^{3} / 11 ] = 3 , Remainder [ 9^{4} / 11 ] = 5
Remainder [ 9^{5} / 11 ] = 1, Remainder [ 9^{6} / 11 ] = 9, Remainder [ 9^{7} / 11 ] = 4, Remainder [ 9^{8} / 11 ] = 3
Pattern repeats in cycles of 5. So if we are asked to find Remainder [ 9^{100 }/ 11 ]， we know it is 1. (100 is in the form 5n and we know remainder for 5 is 1.. cool right ?)
Note:
Remainder [9^{3}/11] = Remainder [Remainder [9^{2}/11] * Remainder [9^{2}/11] ) / 11] = Remainder [ 4 * 9 / 11] = 3.
This funda comes very handy in scenarios like this. Like we dont have to solve Rem [9^{8 }/11] because we already know Rem[9^{4 }/11] as 5..
Rem [9^{8 }/11] = Remainder [ 9^{4 }* 9^{4 }/11 ] = Remainder [ (5 * 5) / 11 ] = 3
Also, Remainder [9^{7 }/11] = Remainder [9^{3 }* 9^{4 }/ 11 ] = Remainder [ ( 3 * 5 ) / 11 ] = 4 ( as Rem [9^{3 }/11] = 3 and Rem [9^{4 }/11] = 5 )
What is the remainder when 7^{100 }is divided by 4?
Remainder[ 7^{1 }/ 4 ] = 3, Remainder[ 7^{2 }/ 4 ] = 1, Remainder[ 7^{3 }/ 4 ] = 3, Remainder[ 7^{4 }/ 4 ] = 1 and so on...
Pattern repeats in cycles of 2. Remainder [ 7^{n }/ 4 ] is 3 when n is odd and is 1 when n is even.
7^{100 }when divided by 4 gives a remainder of 1.
(Same can be solved using other methods also)
Find the remainder when 3^{99^99} is divided by 7
Find the pattern of remainder when 3^{n }is divided by 7.
Remainder [ 3^{1 }/ 7 ] = 3, Remainder [ 3^{2 }/ 7 ] = 2
Remainder [ 3^{3 }/ 7 ] = 6 (Don’t calculate Rem[3^{3}/7] we already have Rem[3^{1}/7] & Rem[3^{2}/7])
Remainder [ 3^{4 }/ 7 ] = 4 (using Rem[3^{2}/7])
Remainder [ 3^{5 }/ 7 ] = 5 (using Rem[3^{3}/7] and Rem[3^{2}/7] )
Remainder [ 3^{6 }/ 7 ] = 1 (using Rem[3^{3}/7])
Remainder [ 3^{7 }/ 7 ] = 3 (using Rem[3^{3}/7] and Rem[3^{4}/7] )
Remainder [ 3^{8 }/ 7 ] = 2 (using Rem[3^{4}/7])
Pattern repeats in cycles of 6. (We can do this easily from Euler’s theorem, as φ(7) = 6, hence Remainder [3^{6}/7] = 1. Explained just to get the idea of patterns in remainders)
Now our task is to find Remainder [ 99^{99}/ 6 ]
Remainder [99^{99}/6] = Remainder [3^{99}/6]
Remainder [ 3^{1} / 6 ] = 3, Remainder [ 3^{2} /6 ] = 3, Remainder [ 3^{3} / 6 ] = 3 and so on..!
Hence 99^{99 }can be written as 6n + 3.
Remainder [ 3^{99^99 }/ 7 ] = Remainder [ 3^{(6n + 3)}/ 7 ]
we have found out the pattern of 3 divided by 7 repeats in cycles of 6. So we need to find the Remainder [ 3^{3} / 7 ] to get the answer which is equal to 6
Euler’s Remainder Theorem
We say two numbers ( say a and b ) are co-prime to each other when HCF(a,b) = 1, i.e, no divisor divide both of them completely at the same time.
Eg: 21 and 8 are co primes because they don't have any common factors except 1
In number theory, Euler's totient or phi function, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. |
Take n = 9, then 1, 2, 4, 5, 7 and 8, are relatively prime to 9. Therefore, φ(9) = 6.
How to find Euler’s totient?
Say n = P_{1}^{a }x P_{2}^{b }x P_{3}^{c }x ... ( where P_{1} P_{2}, P_{3} ... are prime factors of n ) φ(n) = n x (1 - 1/P_{1}) x (1 - 1/P_{2}) x (1 - 1/P_{3}) x .... If n is prime then φ(n) = n - 1 |
φ(100) = 100 x (1-1 / 2) x (1- 1 / 5) = 100 x 1 / 2 x 4 / 5 = 40
φ(9) = 9 x (1 – 1/3) = 6
Euler’s Remainder theorem states that for co prime numbers M and N, Remainder [M^{φ}^{(N) }/ N] = 1 Always check whether the numbers are co primes are not. Euler’s theorem is applicable only for co prime numbers |
What is the remainder when 21^{865 }is divided by 17
Remainder[21/17] = 4
Remainder [ 21^{865}/ 17 ] = Remainder [ 4^{865}/ 17 ]
4 and 17 are co prime numbers. ( A prime number is always coprime to any other number)
φ(17) = 17 x ( 1 – 1 / 17) = 16.
So Euler’s theorem says Remainder [ 4^{16}/ 17 ] = 1
To use this result in the given problem we need to write 865 in 16n + r form.
865 = 16 * 54 + 1, so 4^{865 }can be written as 4^{16 * 54 }x 4
Remainder[4^{865}/17] = Remainder[ 4^{16*54}/17] * Remainder[4/17] = 1 * 4 = 4
What is the remainder when 99^{999999 }is divided by 23
Remainder[99/23] = 7
Remainder[99^{999999}/23] = Remainder[7^{999999}/23]
7 and 23 are co prime numbers
Here 23 is prime, so φ(23) = 22
So by applying Euler's theorem we can say that Remainder[7^{22}/23] = 1
In order to use this result in our problem we need to write 999999 in 22n + r form. Before rushing into dividing 999999 by 22, just think whether we have any better way to do that. We know, 999999 = 22n + r , 0 ≤ r < 22. 999999 is divisible by 11 and so is 22. which means r is also a multiple of 11. Only numbers which are less than 22 and is a multiple of 11 is 11 and 0. But as 999999 is odd and 22n is even, r should be odd. so r = 11. Saved our time right ? ;)
999999 = 22n + 11
Remainder[7^{999999}/23] = Remainder[7^{22n}/23] * Remainder[7^{11}/23] = 1 * Remainder[7^{11}/23] = Remainder[7^{2 }* ^{5 }* 7/23]
= Remainder[ 3^{5} * 7/23] ( as Remainder[7^{2}/23] = 3 )
= Remainder[3^{3 }* 3^{2 }* 7/23] = Remainder[4 * 9 * 7/23] = Remainder[28 * 9/23] = Remainder[45/23] = 22
Find the remainder when 97 ^{97 ^ 97 }is divided by 11
Remainder [97/11] = 9
So, Remainder [97^{97^97}/11] = Remainder [9^{ 97^97}/11]
From Euler’s theorem, Remainder [9^{10}/11] = 1
97 and 10 are again co primes. So φ(10) = 10 (1-1/2) (1-1/5) = 4
Remainder [97^{4}/11] = 1
97 = 4n + 1, So Remainder [97^{97}/11] = Remainder [97/10] = 7
Means 97^{97 }can be written as 10n + 7
Now our original question,
Remainder [9^{97^97}/11] = Remainder [9^{10n+7}/11] = Remainder [9^{7}/11] = 4 :)
Fermat’s little theorem
Euler’s theorem says that if p is a prime numberand a and p are co-primes then a^{φ}^{(p) }/ p always gives a remainder of 1.
Now we know for any prime number p, φ(p) = p - 1
Remainder of a^{( p – 1 )}/ p is 1, which is Fermat’s little theorem |
We can derive other useful results like
- Remainder of a^{p }/ p is a.
- (a^{p }– a) is always divisible by a.
Wilson’s theorem
Remainder[(p-1)! / p ] = (p-1), if p is a prime number. |
We can also derive some useful results like
- Remainder of [(p-1)! + 1] / p is zero.
- Remainder of (p-2)! / p is 1.
Example:
Remainder of [22!/23] = 22
Remainder of [21!/23] = 1
I hope the explanations are clear are correct. Please let me know if any concepts regarding remainders are missed out or incase of any errors.. Happy learning :)
Set theory - Maxima / Minima Using Line Method
Set theory is a good friend for those who find it difficult to score in quant section. We need to arrange the given data based on the question and this can get complicated sometimes. There are some methods which will make our life easier while dealing with set based questions. We have shared two methods in the article, Line method and Sum of sets. If you know any thumb rule regarding when to use what or some other good methods to solve set based questions please share your thoughts.
Thanks Ankan Sengupta and Alok Moghe for your support in this article :)
Let's solve!
In a school of 100 students each of them play at least one sport among cricket, football, volleyball, basketball, hockey and tennis.It is known that exactly 90 play cricket, 80 play football, 70 play hockey, 60 play basketball , 40 play volleyball and 10 play tennis.
What is the maximum number of students who play exactly four of the six games?
Don't rush to venn diagrams. We will represent the given data as simple lines.
Now we are asked to find the max number of students who play EXACTLY 4 games. All what we need is to draw boxes which will contain EXACTLY 4 lines using the given 6 lines. Just ensure that all lines in the box has the same length and as the question is asked for maximum we need to arrange the lines so that the length of the box ( basically overlapping part of the lines within the box) should be maximum.
We can draw 3 boxes as above. one has 4 lines of length 60 each and other 2 boxes having 5 lines of length 10 in each of them. Answer is 60 + 10 + 10 = 80. Easy right ?
What is the maximum number of students who play exactly five of the six games?
Again we will try to draw boxes which will contain EXACTLY 5 lines using the given 6 lines.
We can draw 2 boxes. one with 5 lines of length 40 each and other one with 5 lines of length 10 each. Our answser is 40 + 10 = 50.
What is the minimum number of students who play cricket, football and hockey?
Here we are asked for the minimum. So we need to arrange the lines so that we can have the box which has all 3 lines with MINIMUM length of lines. Remember we have 100 students in the class. Diagram will look like below
The length of the lines in the box is 100 - ( 20 + 30 + 10 ) = 40, our answer :)
PS: you can also solve this one using below trick
Find the difference from total for each item and add all of them together.
For cricket, 100 - 90 = 10
For football, 100 - 80 = 20
For hockey, 100 - 70 = 30
Sum = 10 + 20 + 30 = 60
Again find the difference from the total, 100 - 60 = 40 :)
We will solve another set now.
The following table gives the number of students who secured more than 90% marks in each of the five subjects from class 6th to 10th at a school in year 2006
class/subject | english | physics | chemistry | maths | biology |
6th | 12 | 16 | 15 | 22 | 18 |
7th | 15 | 22 | 22 | 21 | 15 |
8th | 7 | 18 | 16 | 23 | 17 |
9th | 10 | 19 | 15 | 22 | 18 |
10th | 15 | 25 | 21 | 29 | 16 |
The number of students in the different classes in the year were as below
Class | No. of students |
6th | 30 |
7th | 35 |
8th | 28 |
9th | 36 |
10th | 40 |
In the class 7th the number of students who scored more than 90% in at least two of the five subjects is at least
Sum of set method: Let a, b, c, d and e represents students who got more than 90% in exactly 1, 2, 3, 4 and 5 subjects respectively.
a + 2b + 3c + 4d + 5c = sum of all those who got above 90
= 15 + 22 + 22 + 21 + 15
= 95
Now we need to minimize b, c, d and e ( atleast 2 subject cases ). We can do this by putting b = c = d = 0 and putting max value to e ( as we multiply e with 5 )
so a + 5e = 95
As atleast 15 students got 90% in a subject (check the table) e can have the minimum value of 15.
so e = 15 and a = 20 is the case.
and minimum atleast 2 case will be 15.
This will satisfy total number of students too, 20 + 15 = 35.
For the curious ones line method given below
Line method : We need to find the minimum value of atleast 2. now atleast 2 consist of ( students with 90% in 2 subjects ) + ( students with 90% in 3 subjects ) + ( students with 90% in 3 subjects ) + ( students with 90% in 4 subjects ) + ( students with 90% in 5 subjects ). So to minimize "atleast 2" scenario we have to maximize atleast 1.
Diagram given below
We can see with atleast 1 case maximum ( means boxes which can have only one line ) we get min atleast 2 cases as 15.
Happy learning. Cheers!
CAT Preparation : Worried About Quant ? Lets Tame Some Monster Numbers
So one fine day you had this epiphany that a management degree from a premium B school would solve your current problems (ranging from impressing your crush to improving your salary) and will change your life for good. You decided to give CAT and thought what a funny name that is for an exam. You googled for the syllabus and found the most comforting sentences you ever read in your life – High school Math and English. You are happy as you always scored well in Math and you loved reading Harry potter series. You joined some forums where you met your fellow aspirants - Clark Kent, Bruce Wayne, Peter Parker and Pandit Gangadhar Vidyadhar Mayadhar Omkarnath Shastri. Everything was peaceful until one day you saw some weird numbers like 123456…. 1000 digits or 9999^55555. You were bemused thinking why on earth these kind of questions appearing in a forum that should be focusing on high school math. To add up to your pain, all your above said mortal friends turned in to Superman, Batman, Spiderman, Shaktiman and solved them in a blink of an eye. Some even complained why such super easy questions are being posted.
When I started seeing all such numbers, my expression was almost like this and the case would be similar for most of the mortal newbies.
Don’t worry, it is just a very common initial crisis most of the CAT aspirants face (even for people from math background) and with very minimal effort, you can also put a cape and come up with some fancy names for yourself.
In this article we will learn some simple and interesting concepts to solve 10 such "Monster" number waala questions. If you know how to solve all the given questions without taking more than a minute per question, you need not spend time on this page and can explore other interesting articles we have in MBAtious. For others, let’s have some fun!
- What is the remainder when 88888….. 300 digits is divided by 111.
- What is the remainder when 123123123123… 600 digits divided by 1001.
- What is the remainder when 5555…. 900 digits is divided by 7.
- What is the remainder when 123123… 300 digits is divided by 999
- What is the remainder when 1111… 111 digits is divided by 625
- What is the remainder when 3^1 + 33^2 + 333^3 + 3333^4 + … 33 terms is divided by 6
- What is the remainder when 123456789^2 – 987654321^2 divided by 8
- What is the remainder when 123456…. 9899100 is divided by 16
- Which is greater, 49^51 or 51^49
- What is the number of digits in 3^40
Soltuions:
- Concept 1: Any digit written 3 times will be divisible by 3 and 37
Given question, 111 = 37 * 3. As the given number is divisible by both 3 and 37, remainder is 0.
- Concept 2: Any number of the form abcabc is divisible by 7, 11 and 13.
Given question, 1001 = 7 * 11 * 13 and the given number is divisible by 7, 11 and 13. So the remainder when divided by 1001 is 0
- Concept 3: Any digit repeated P times is divisible by P, where P is a prime > 5
here, P = 7 and hence 555555 (repeated 6 times) is completely divisible by 7
900 is divisible by 6, so 555555… repeated 900 times is completely divisible by 7. Remainder is 0
- Concept 4: A number is divisible by 99.. n digits if the sum of the digits taken n at a time from right is divisible by 99.. n digits.
Here, sum of digits taken 3 at a time for 123123… 300 digits = (123) * 100 = 12300
12300/99 gives a remainder of 312
- Concept 5: A number is divisible by 5^{n }if the last n digits are divisible by 5^{n }
so to check for the divisibility with 625 ( 5^4) we need to check the last 4 digits, 1111
1111/625 will give a remainder of 486
- Concept 6: Any power of a number formed by the digit 3 repeated any times will give a remainder of 3 when divided by 6
[ ( 33… n terms ) ^ any power ] / 6 gives a remainder of 3
so 3/6, 33^2/6, 333^3/6.. will give a remainder of 3
so we are looking at 3 + 3 + 3 … 33 terms / 6 = 99/6 gives a remainder of 3
- Concept 7: (Any odd number)^2 / 8 gives a remainder of 1
here both terms are odd and hence will give a remainder of 1 each with 8
so net remainder is 1 – 1 = 0
- Concept 8: A number is divisible by 2^{n }if the last n digits are divisible by 2^{n }
Here as we need to check with the divisibility by 16 (= 2^4) we are worried only about last 4 digits, which are 9100
9100 will give a remainder of 12 when divided by 16, so 12 is our answer
- Concept 9: To compare a^b and b^a, closer the base (a or b) is to e, higher the value will be.
here 49 is closer to e (= 2.71) so 49^51 > 51^49
- Concept 10: To find the number of digits of an expression, take the integer part of the log of the number and add one.
Here, log (3^40) = 40 log 3 = 40 x 0.477 = 19.xx
Integral part = 19, number of digits = 19 + 1 = 20
Learn the basic log values like log2, log3 etc.
Please let me know in case of errors or better methods :)
Happy learning!
Three Concepts In Percentage To Tackle Quant
While preparing for exams like CAT, it is very important to budget your time and effort in the right topics and in the right order. It is very common for aspirants to blindly accept a pre-defined order of chapters starting from Types of numbers to Factors to HCF/LCM to Divisibility and so on. This might also be the reason why our preparation forums are getting flooded with number system questions than other topics. These are definitely important areas but considering you folks are preparing for being the next management think tanks, a much better strategy would be to arrange topics in order of their range of application and ROI. This way, concepts like Approximation, Solving using options, Equations, Percentages and Ratio/Average concepts would enjoy much higher ranks than the one allocated them in our default order. In this article we will see some very important concepts from the topic Percentages which will help you immensely in both Quant and DI.
Percentage is not new to us. We deal with it every day; while giving tips, while calculating discounts etc. In CAT and other exams, application of percentage can be seen in various topics like TSD, Profit/Loss, Ratio/Proportion, Number theory etc. and not to forget DI.
Concept 1: X% of Y = Y% of X
What is 27% of 90?
Our thought process mostly would be 10% of 90 is 9, 5% is 4.5 and 2% is 1.8
hence 27 % of 90 = 18 + 4.5 + 1.8 = 24.3 (5 seconds max)
There would be faster methods but we are not going to any math Olympiad. Practice this method religiously and you will be quick enough for CAT and similar exams. :)
Now what is 90% of 27?
No need to calculate again, we already did it and got the answer as 24.3!
27% of 90 = 27 x 90 / 100 = 90 x 27 / 100 = 90% of 27
That means when we solve one percentage sum we are actually solving two. And this comes very handy if one problem is much easier to solve than the other one.
For example, what is 36% of 25?
We know 36% of 25 = 25% of 36
as second one is much easier to calculate we can say 36% of 25 = 9 in no time.
Let’s recap how to convert percentage to fractions and vice versa.
60% = 60/100 = 3/5
so to calculate 65% of 60, we can easily calculate as 65% of 60 = 60% of 65 = 3 x 65 / 5 = 39
Now to convert 3/5 to percentage, (3/5) x 100 = 60%
Before going further, make sure you know values like 1/3 = 0.33, 1/7 = 0.1428, 1/9 = 0.111, 1/11 = 0.0909 etc. If we get a question like a 140 is increased by 28.56% we can immediately know it has increase 2/7 times which is 140 (1 + 2/7) = 140 x 9/7 = 180. Saved time, isn’t it? Mug up!
Concept 2: Successive Percentage Increase/decrease
Let’s start with a simple problem, what would be the final value if 60 is increased by 30%
Final value = 60 x (1 + 30/100) = 78
(Else we know 10% of 60 = 6, so 30% increase should add 18 yielding 78 )
Now what would be the final value if 60 is increased by 30% and then by 50%
Final Value = 60 x (1 + 30/100) (1 + 50/100) = 117
Let the successive increase in percentages be a% and b%. In that case, the total increase will be (a + b + ab/100) % (for decrease use a negative sign)
Here an increase of 30% and 50% can be considered as a net increase of 95%
Final value = 60 (1 + 95/100) = 60 x 195/100 = 117
(Smart way would be 95% increase means 5% ( = 3 ) less than double the original value, so 60 x 2 – 3 = 117)
Now what would be the final value if 60 is increased by 30% first and then decreased by 50%?
Net change = (30 – 50 – 15) = -35% => 35% decrease
Final value = 60 – 21 = 39 (because 35% of 60 is 6 x 3 + 3 = 21)
What if a 50% off + 50% off is given on a brand? Will we get it for free? :)
Net change = (-50) + (-50) + (-50) x (-50)/100 = -100 + 25 = -75% = 75% discount
Now an interesting one, what if 60 is increased by 50% first and then decreased by 50%
Net change = 50 – 50 – 25 = -25 => 25% discount.
What if 60 is decreased by 50% and then increased by 50%?
Net change = -50 + 50 – 25 = -25% discount
Got the idea right, cool!
Concept 3: Product Constancy
Petrol/Diesel price again hiked today. But we are not affected as we always fill for 100 Rupees. ;)
Formula:
If Z = XY and if there is p% increase in X (or Y). Then Y (or X ) should decrease by P/ (100+P) x 100 to keep Z constant.
Also, and if there is p% decrease in X (or Y). Then Y (or X ) should increase by P/ (100 - P) x 100 to keep Z constant.
If Milk price is hiked by 25%, how much % should we reduce the consumption to keep the expenditure constant (say at 100)?
Expenditure = Price x Consumption
Price went up by 5%
so Consumption should come down by 25/ (100+25) x 100 = 2500/125 = 20%
Also, if price is decreased by 10%, then consumption should increase by 10/ (90) x 100 = 11.11% (we knew 1/9 = 0.1111)
A man spends Rs.54 on apples every month. Price of Apple is decreased by 20% and this man can buy 10 apples more. What is the reduced price per dozen?
If price is 20% decreased => consumption should increase by 25% (as seen in previous case)
25% increase = 10 apples => He used to buy 40 apples before.
54 Rupees for 40 Apples.
Now price is reduced by 20% (Multiplying factor = 1-20/100 = 80/100 = 0.8 )
so new price per dozen = 0.8 x 54/40 x 12 = 13 (approx)
Ramesh takes 90 minutes to reach his office from home. If his speed becomes 5/4 of original speed. How much less time will he take to reach his office?
Here distance is same and we can see Speed increased by 25%. So Time should reduce by 20% = 18 minutes.
Once you master this concept, many problems in TSD, Profit/Loss, and Geometry will be a cake walk.
Some extra gyan:
If A’s income is 16.66% than B. Does that mean B’s income is 16.66% less than that of A. Of course not.
If A is X% higher than B then B is 100 * X/ (100+X) % lower than A
So In the given question, B’s income is 100 x 16.66 / (100 + 16.66) = 14.28% lesser than A
We don’t need this formula here if you have mastered the fractional values. We know 1/6 = 0.1666
So A = (1 + (1/6) B ) = 7/6 B
=> B = (6/7) A => (1 – 1/7) A => 14.28% less.
Also, If A is X% lower than B then B is 100 * X/ (100-X) % higher than APercentage change (increase/decrease) = (Change/original) x 100
A was earning 60 rupees and he got a hike and started earning 70. What is the percentage change?
Percentage change = [(70 – 10)/60] x 100 = 16.66% increase (we know 1/6 = 0.1666).
Now, how much percentage decrease should happen for A to earn 60 rupees again?
= [(60 – 70)/70] x 100 = 14.28% (we know 1/7 = 0.1428 )If current value, P increases at a rate of R% per annum then
Value after n years = P*(1 + R/100)^n
Value n years ago = P/(1 + R/100)^n
If value decreases at a rate of R%, use –R instead of R in the above formula.
Number theory demystified - Ankan Sengupta, FMS Delhi
Number theory has always been a chapter which is fascinating if can be learnt properly, otherwise it might become nightmarish and can well prove to be the bane in a competitive exam like CAT, where you’ll find a chunk of question on this topic every year. In this article I’ll discuss a few topics along with some tricks to make others help grapple this superlative topic with some ease at least.
Number theory problems are of 3 types mainly. Basic concepts based, Remainder problems and LCM-HCF based problems. I’ll discuss all 3 of them.
Basic Concept based problems: Now a days most of the questions come from this area only cause there is no fixed set of formulae to solve problems of this area. So what you need is to have a clear understanding of the basics. Take for example:
For how many natural numbers n (n+36) is a perfect square ?
a) 0
b) 1
c) 2
d) None of the above
Ans: Case 1:both n and n+36 are perfect squares. Only 1 possible case,that is n = 64.
Case 2: n+36=kn, where k is a perfect square.so k=1+36/n.Factors of 36 are 1,2,3,4,6,9,12,18 and 36. Only when n=12,k is a perfect square. So combining these 2 cases we can say option C is correct.
A clarity of basics is the imperative tool to be able to decipher all the cases. If you miss even a single case,that might lead to a -1 instead of a clear-cut +3. People who are prone to silly mistakes watch out for keywords like,natural numbers/real numbers/integers while solving this type of questions.
Now I want to discuss one of favourite questions in this topic.
In how many ways can you express 72 as product of 3 natural numbers( unordered pairs)
If there is a triplet (a,b,c), then an ordered triplet means (a,b,c) and (b,a,c) are different and an unordered triplet means (a,b,c),(b,a,c),(c,a,b) etc all are same.
72 = 2^3 * 3^2
let, x = 2^a1 * 3^b1
y= 2^a2 * 3^b2
z = 3^a3 * 3^b3
a1+a2+a3=3..solutions=3+3-1C3-1= 10
b1+b2+b3=2 solutions=3+2-1C3-1= 6
total solutions=10*6= 60( these are ordered pairs)
Some of the solutions will be 1*1*72, 2*2*18 ..there will 4 such numbers since 4 factors of 72 are perfect squares...these numbers can be arranged in 3!/2! =3 ways...
60-3*4=48..these 48 is ordered pairs with all numbers different..so divide by 3!..48/6=8. add the remaining 4 we removed 8+4=12.
Now what we did in the step before the last one is to remove repetitive elements.A simple way to do that is to check how many perfect squares are there in the number given.
Like in 72=2^3*3^2,there 2*2=4 perfect squares(Every even power including 0 of a prime factor gives rise to a perfect square,so contributions of 2’s power=2,contribution of 3’s power=2).
Now since 72 is not a perfect cube so all the 3 numbers cannot be equal,atmost 2 can be equal.When 2 of the numbers are equal,total number of arrangements is 3!/2!=3.so these 3*4=12 elements are repetitive.So primarily just subtract these 12 elements from total 60 and divide the residue by 3!(since there are 3 number so divide the ordered unequal numbers by 3! To get the unordered one).So total unordered unequal solutions=48/6=8.Now add back those 4 repititive elements here.so total 8+4=12 solutions.
This is the most complex problem of this portion.Will end this part with another problem with slightly different flavour.
A * B = 9C + 1 where A, B and C are natural numbers and A lies between 100 and 200 both inclusive. How many different values can A take.
a) 101
b) 50
c) 11
d) none of the above
A=100+x,where x is a whole number and < =100.
so (100+x)B-1/9=C to have an integral value of C, (1+x)B-1=9k, k=positive integer.
now if (1+x)=3m form,then 3m-1 cannot be equal to 9k.
so except for 3m form,3m+1 and 3m+2 both forms are permissible.
so 1+x=3m,x=3m-1=3n+2.
so all the whole numbers between 0 and 100,which are of the form 3n+2 need to be excluded.
so 101-33=68 should be the answer.
Incorporated this question just to show how clarity in basics is a prerequisite in this topic.
Remainder problems:
Now a days CAT doesn’t emphasize on this portion much cause by cramming a few formulae you can tackle all the questions. Still would like to discuss 2 topics here: Chinese remainder theorem(CRT) and modified Euler function/modified cyclicity/charmichael’s function.
a) CRT:
Find the last 3 digits of 126^130.
Ans:there are many ways to solve this question.but easiest way is to use CRT.
See in CRT what we do is to express the divisor as a product of 2 co-prime integers. Now we’ve to find last 3 digits,that means we’ve to divide the number given by 1000.1000=125*8 (125 and 8 are co-primes).
Now divide the number given by 125.remainder is 1.
And again divide the number given by 8. Remainder is 0.
Now this is the most important part.By the help of CRt we can say that the ultimate remainder that we require is of the form 125k+1=8m,where k,m are non-negative integers..376 is the first number of this form. So 376 is our answer.This is how CRT works.
b) Cyclicity:
Now I’ll discuss a trick that reduces our effort in problems where we generally employ Euler’s theorem.
The use will be just like Euler.Just instead of calculating Euler’s totient function, we’ll compute cyclicity.
C(P^n)=P^n(1-1/P)[P=prime,not for 2]
C(2^n)=2^(n-1)[n
C(2^n)=2^(n-2)[n>=3]
C (any composite number say P^n*Q^k*R^m) = LCM{C(P^n),C(Q^k),C(r^m)}[P,Q,R are prime factors of that composite number]
Say for example
25^19mod36-find remainder.
In this problem E(36)=12.When you divide the exponent with 12 remainder is 7,so you still have to do some calculation. Now C(36)=LCM{C(3^2),C(2^2)}=6.when you divide the power by 6,it becomes 1.So simply the remainder becomes 1.
By Euler you’ll get the same answer,but it reduces your effort significantly.
c) LCM-HCF/factor based problems:
Here I’ll discuss 2 of my favourite type of problems.
First question incorporates both the concept of LCM and remainder.
I thought of a number that when divided by 20 leaves a remainder 18,when divided by 19 remainder is 17 and so on .So what is the remainder when smallest such number is divided by 50?
Ans: This question checks our basics very nicely.
We can say if the number is N,N+2 is divisible by 2,3,4,5,6…,20.so LCM of all these numbers=2^4*3^2*5*7*11*13*17*19.
So N=the number mentioned-2.
Now last 2 digits of the number mentioned above=10 (we can get that by simple remainder theorem).
So last 2 digits of N=08.So if we divide a number by 50 whose last 2 digits=08, remainder will always be 08.So this is the ans.
Second problem involves your thinking regarding multiplication along with factorisation.
N=2^3*3^4*5^9.Fins the number of zeroes in the product of all the factors of this number that are not divisible by 12.
Ans: No of factors of this number=4*5*10=200
Number of factors divisible by 12=2*4*10=80
Product of all factors=N^no of factors/2=N^100
Product of all factors divisible by 12=(12N)^40
Product of factors not divisible by 12=N^100/(12N)^40=N^60/12^40=2^100*3^80*5^540
So number of zeroes=min(100,540)=100.
This example sums up all the queries regarding questions on factorisation.
These are the main topics that you’ve to cover in number theory and trust me if your basics are clear Number Theory is the most interesting topic that you’ll come across in mathematics.
One more topic I’d like to mention here in a short way.
Perfect number is defined as a positive integer which is the sum of its proper positive divisors, that is, the sum of the positive divisors excluding the number itself.First four perfect numbers can be generated by 2^{n}^{−1}(2^{n} − 1).[Where 2^{n} − 1 is a prime number].
This are all even perfect numbers.All even perfect numbers (except 6) digital root 1.6,28,496,8128 are perfect numbers. The reciprocals of the divisors of a perfect number N must add up to 2.If you can remember these properties you’ll surely be benefited on the long run.For more enthusiastic readers,some suggested topics are:Charmichael’s function,Chicken Mcnugget’s theorem,Number of Ordered and unordered pairs in a given LCM of 3 or more numbers,Concepts regarding Armstrong number,Factorian etc.
Happy learning.
Through The Eyes Of An Aspirant - Probability Theory Decoded - Ankan Sengupta, FMS Delhi
Probability itself doesn’t pose much of a threat to aspirants. But a probability question, clubbed with Number theory or permutation-combination, when is dished out to aspirants, sometimes it can really break a havoc. Geometrical probability is another portion to cause discomfort too. So I’d be segregating this chapter in mainly three parts - General probability theory (including conditional probability), Binomial probability and Geometrical probability.
Probability in general is defined as the extent to which an event is likely to occur, measured by the ratio of the favourable cases to the whole number of cases possible. So mathematically we can write it as P(A) = s(A)/n, where P(A)=probability of occurrence of the event A,s(A)=No. of events in favour of A,n=total no. of events=sample space.This is called the Classical Definition of Probability.
But if trials are to be repeated a great number of times under essentially the same condition then the limit of the ratio of the number of times that an event happens to the total number of trials, as the number of trials increases indefinitely is called the probability of the happening of the event. It is assumed that the limit exists and finite uniquely. Symbolically p (A) = p = lim (n -> infinity) m/n, provided it is finite and unique.This definition is more general in nature and is called Statistical Defnition of Probability.
The two definitions are apparently different but both of them can be reconciled the same sense.
1) General Probability- General probability theory includes questions of probability that are clubbed with other topics from Number theory, Algebra or PnC and questions on conditional probability. So I’d be discussing a few questions regarding these topics in this space. The first question is a simplistic probability question which only incorporates general probability concept. I’ve solved it in an unconventional way in method 1 and with a self-developed shortcut in method 2.
Find the probability that 3 random points selected from circumference of circle lie on the same semi-circle
Approach 1:
Since we're here concerned with circumference,so just consider a clock.suppose there are marks at 3,6,9 and 12 positions..now for choice of first 2 points there is no restriction.So choose 2 points at 12 and 3 positions..Now there are 4 gaps in between those marked positions.Check only between 6 and 9 there cannot be the 3rd point to satisfy our criteriaSsince I considered those 2 points randomly,so we can randomise it throughout the domain.Answer is 1-1/4=3/4 only.
Approach 2:
n/2^(n-1)..put n=3..it is the general formula for this question,n=no. of points under consideration.This is an empirical formula without any proof.
Now a problem which deals with number theory.
Let N be a set of all 4 digit perfect squares. Find the probability if a number whose sum of tens digit and units digit is equal to 7 is selected from the set
a) 12/68
b) 18/68
c) 13/68
d) None of the above
4 digit square roots will range from 32 to 99, so total 68 numbers
now, check for those number from 1 to 30, which give last two digits sum as 7, so found it as 4, 5,15,19,25, (one should know that any 5 square would end up in 25.
so favourable numbers are 35,45,.....,95,(7 such numbers)
(50-4)^2,(50+4)^2,(100-4)^2(3 such numbers)
(50+19)^2,(100-19)^2( 2 such numbers)
total,7 + 3 + 2 = 12.
P=12/68.
A question now which clubs probability with algebra.
Each coefficient of ax^2+bx+c=0 is determined by throwing a dice. Find probability of its roots being real.
For real roots,b²-4ac>=0,where 1< =a,b,c< =6.
this cannot happen for b=1
b=2 gives a=c=1--- 1 soln.
b=3 gives a=c=1, a=2,c=1, a=1,c=2---3 soln
b=4 gives 8 soln
b=5 gives 14 soln.
b=6 gives 17 cases
Total=43 cases
total cases =no. of ways of a*no. of ways of b*no. of ways of c=6*6*6=216
Ans=43/216
Now I’d discuss one of my most favourite problems here. This is mainly a question of PnC.I’m modifying it in terms of probability.
A dice can be coloured with at most 2 different colours. Find the probability that it is coloured with exactly 2 colours.
This problem can be solved by making cases.In that you’ve to consider symmetry of the figure which incorporates a complex calculation.
So I’d be approaching it differently with a technique derived from graph theory mainly,Polya’s enumeration theorem.
How many ways are there to color the sides of a 3-dimensional cube with upto t colors, up to rotation of the cube?
Answer is,
So,In our problem denominator has t=2 and numerator is t=1 subtracted from t=2.
When t=2,total cases=10 and when t=1 total cases=1.
So answer is (10-1)/10=9/10.
A problem on conditional probability will conclude the theory of general probability aptly.
Your neighbor has 2 children. He picks one of them at random and comes by your house; he brings a boy named Joe (his son). What is the probability that Joe’s sibling is a brother ?
Consider the experiment of selecting a random family having two children and recording whether they are boys or girls. Then, the sample space is S = {BB,BG,GB,GG}, where, e.g., outcome “BG” means that the first-born child is a boy and the second-born is a girl. Assuming boys and girls are equally likely to be born, the 4 elements of S are equally likelythat the The event, F, that the neighbor has two boys (i.e., Joe has a brother) is the set F = {BB}.Now we are given the event E′ that “your neighbor randomly chose one of his 2 children, and that chosen child is a son”
We want to compute P(F|E ′ ) = P(F ∩ E′ ) P(E′) = P({BB}) P(E′ |{BB})P({BB}) + P(E′ |{BG})P({BG}) + P(E′ |{GB})P({GB}) + P(E′ |{GG})P({GG})
= 1/4 /[1(1/4) + (1/2)(1/4) + (1/2)(1/4) + 0(1/4)] = 1/4 /1/2 = 1/ 2 .
2) Binomial Proability:
We consider binomial probability when we’re dealing with finite number of caes and only 2 outcomes are possible.Say,X=the variable,total no. of trials=n.p=probability of having a favourable case,q=1-p=probability of having an unfavourable event. Then,if we’re to calculate probability that r events happened ,then P ( X = r ) = nCr * p^{r }* q ^{(n-r}^{)}
Now we’d consider an example.
out of 5 students like Maths.Say total 5^9 professors took data on 10 students to check those students like Maths or not,find how many of them would report only 2 like Maths.
A.So,here r=2.n=10.p=2/5,q=1-2/5=3/5.
P(X=r=2)=10C2*(2/5)^2*(3/5)^8=45*2^2*3^8/5^10.
Therefore out of 5^9 professors only P*5^9=2^2*3^10 would report the given.
3) Geometrical Probability:
This is the third variant of probability. I’ll be providing a few examples regarding how to deal with problems of this kind.
Ankan and Rajanya agreed to meet at Shiva temple between 10.00 to 11.00.Each one of them arrives there and stays for exactly 6 minutes.What’s the probability that they’ll meet?
A. The probability that they do not meet is represented by the total of the areas of the 2 outer triangles in the figure given below,which is 0.81.So probability that they’ll meet=1-0.81=0.19.
A driver goes out of the city to a place which is 100 Km away from the city and comes back in the same day. With a full tank he can drive upto 250Km.Today he forgot to fuel up his car.What is the probability that he’ll run out of fuel?
I’d be concluding my article now.
Keep practising and happy learning.