Permutations and Combinations- Free Lecture Notes

Many of you have emailed about some easy reference for Permutations and Combinations, Number theory etc. I cannot say if it is an easy reference, but it is one concise one.. It is from one of our Professors at IIT Kanpur, Dr A K Lal, great chap, I must say. This is one gem of a compilation. Hope it helps you.. If the material is too tough, just ignore!

http://home.iitk.ac.in/~arlal/book/mth202.pdf

Enjoy!

Tips: Tournament Problems

Tournament Problems
There are 16 teams and they are divided into 2 pools of 8 each. Each team in a group plays against one another on a round-robin basis. Draws in the competition are not allowed. The top four teams from each group will qualify for the next round i.e round 2. In case of teams having the same number of wins, the team with better run-rate would be ranked ahead.

1. Minimum number of wins required to qualify for the next round _____?
2. Minimum number of wins required to guarantee qualification in the next round _____?

Now, i don't know how many of you are aware of the following method. But 1 thing I mention in advance that this should take only 30 seconds to solve
1.
1 group is consisting of 8 teams. So each team will play 7 match each. Suppose each of the 8 teams were seeded and we consider the case where a higher seeded team will always win.

So the number of wins for the 8 teams would be 7,6,5,4,3,2,1,0 with highest seeded team winning all and lowest seeded team losing all.

For minimum number of wins we allow 3 teams to win maximum number of matches. Of the remaining 5 teams just find out the mean of their number of wins.

In this case it would be (4+3+2+1+0)/5=2.

So 5 teams can end up with 2 wins each and a team with better run rate will qualify with 2 wins.

2.

In this case consider the mean of first 5 higher seeded teams (7+6+5+4+3)/5=5

So it may be the case that 5 teams can end up having 5 wins each. And hence 1 team will miss the second round birth. So minimum number of wins to guarantee a place would be 6.

The trick is to consider wording, qualify means best case scenario while guarantee qualify means worst case scenario.

Mini Concept: Multinomial Theorem

Some Trickery of Multinomial Theorem

x+y+z=n the number of non negative solutions of this equation will be
(n+3-1)C(3-1)=(n+2)C2

if we extend this to r variables then the formula becomes (n+r-1)C(r-1)

if we remove 0, means we need only positive integral solutions to the equation then we get formula as (n-1)C(r-1)

Lets take up one example.
On the occasion of Diwali, PAPA CHIPS is offering one of five prizes with every packet( the prize is inside the packet). the prizes include a pen, pencil, a CD, a movie ticket and a small game. Banta Singh is a fan of PAPA chips and he keeps buying the chips, what is the probability that Banta Singh gets all the five prizes by buying 12 packets of PAPA chips

Solution:
Chuck the story, the question is there are 5 variables and we need the solutions to the equation
a+b+c+d+e=12 ( non negative)
and a+b+c+d+e=12 ( positive integral)
The first case comes as every packet has a prize, and those 5 are the only kinds of prizes.
Second comes from that we need each kind of prize.

so the answer is 11C4/16C4=11!12!/(7!16!)=11.10.9.8/13.14.15.16= 33/182


Lets take another example
If the sum of 101 distinct terms in arithmetic progression is zero , in how many ways can three of these terms be selected such that their sum is zero?

Solution
it is obvious that the middle term is zero
so a(51)=0
so the terms are
-50D, -49D,....,-D, 0, D, ....49D, 50D

now the sum of 3 numbers to be zero
Case 1) if we pick 0, then we have to pick one positive and one negative, which must be equal except for the sign . so 50 ways

case 2) we leave 0 and pick two positive and one negative

then xD+yD-zD=0
x+y=z
z can vary from 1 to 50
we need positive solutions to the equation
which comes 0C1+1C1+2C1...+49C1
add this it will come to 50C2

case 3 it will be same as case 2
we get 50C2

hence total is 2.50C2+50=2500

Concept 6 Data Sufficiency

Concept 6: DATA SUFFICIENCY

"The ultimate goal of mathematics is to eliminate any need for intelligent thought."-A. N. Whitehead

Well, for starters try to think what's the meaning of the above quote, it has a nice and beautiful meaning. To make things so simple that an average mind is able to see it. So lets put this into practice, with another concept lesson.

Today, we will discuss DATA SUFFICIENCY, one of the very scoring problems in cat and other mba entrance exams. The good thing about DS is we get DS both in quant and DI, and it makes for 6-8 problems in almost every paper. As there are no theorems in DS, we will take things to note

Things To Note:

1) DS problems, we need to answer if it is sufficient information to answer, means, there should be one conclusive answer.  We do not need to find the answer, just if it can be found or not?

2) Some questions ask , is this true? So if we can find that the information available is enough to prove that it is not, we are still able to answer the question, that it is not true. Hence we are able to answer the question.

3) Check for all possibilties, that is using one statement, using second, then only combine the two.

Lets take up an example.

Instructions For DS Questions

Each question is followed by two statements, X and Y. Answer each question using the following instructions:
Mark (A) If the question can be answered by using the statement X alone but not by using the statement Y alone.
Mark (B) If the question can be answered by using the statement Y alone but not by using the statement X alone.
Mark (C) If the question can be answered by using either of the statements alone.
Mark (D) If the question can be answered by using both the statements together but not by either of the statements alone.
Mark (E) If the question cannot be answered on the basis of the two statements.


Example 6.1

In a triangle ABC, D is a point on the side BC and M, N are length of perpendicular dropped on line AD from the vertices B and C respectively. Is M > N?

(X) AB > AC

(Y) BD < DC

The problem is simple, but again see this, this question asks is M>N? The answer may be yes or no, but what we are concerned with is our ability to answer it and not the actual answer.

AB>AC gives us no idea, just imagine a few figures and you will know this.

Look at the other statement it says BD<DC, if BP and CQ are the perpendiculars then, BDP and CDQ are similar

so BD/DC=BP/CQ so we know the ratio and thus are able to answer and see this teh answer came NO.

so, we dont really want the answer, but the ability to give a unique answer.

So, answer is B)

This question was taken from QQAD practice test 4, here is the official solution.

Let D' be the midpoint of BC and let X' and Y' be the feet of the perpendicular from B and C to AD' respectively => X' = Y'. As D' shifts to right or left, we can know which of M or N is bigger. Thus, (Y) answers

(X) doesn't tell us anything

=> choice (B) is the right answer

Practice Problem 6.1

Is x=y?

X: (x+y)(1/x+1/y)=4?

Y: (x-50)^2=(y-50)^2

Practice Problem 6.2

What is the value of m and n?

X: n is an even number, m is an odd number, m>n

Y: mn=30

Note: Both the practice problems are old cat problems, enjoy!

Example 6.2

The distance of point P=(x,y,z) from the origin is sqrt(62) units, then find the coordinates of point P.

X: x+y+z=12

Y: x,y, and z are positive integers.

From original questions x^+y^2+z^2=62

From statement X

(x+y+z)^2=144

2(xy+yz+zx)=62

can't say for sure

From statement Y:

positive integers

but we can easily find two pairs (1,5,6), (2,3,7). can't find a unique solution

Option E

This question is taken from SIMCAT 9

Practice Problem 6.3

Rahim plans to draw a square JKLM with a point O on the side JK, but is not successful. Why is Rahim unable to draw the square?

X: The length of  OM is twice that of OL

Y: The length of OM is 4 cm

This problem is taken for CAT 07 paper.

Example 6.3Let p(x) = x^2 + 40. Then for any two positive integers i and j where i > j, is p(i) + p(j) a composite number?

(X) p(i) – p(j) is not a composite number

(Y) p(2i) + p(2j) is a composite number

One of my favourite problems !

p(i) – p(j) is not a composite number
=>i^2-j^2 is a prime as i ,j are positive integers and i >j, ( i^2-j^2) can't be 1
=>(i+j)(i-j)= prime
so i-j=1
let p be the prime so i=(p+1)/2
j=(p-1)/2
clearly p is not 2 hence all p is odd
p(i) + p(j)=80 +(p^2+1)/2

now p^2=6k+1 ( Refer my lession on prime numbers for this )
therefore
p(i) + p(j)=80 +(p^2+1)/2
becomes
80+(6k+2)/2=81+3k=3(27+k)
so not a prime => can be answered by using X

now, p(2i) + p(2j) is a composite number
4(i^2+j^2+20) is composite

now i and j can be anything
can't make any conclusions

=> choice (A) is the right answer

This is QQAD pratice test problem!

Thats all, do post your queries and suggestions !

Good Luck!

Concept 5 Pigeon- Hole Principle

I am delighted with the response, my concept lessons are being well received. Thank you.

Today, we will be taking something called "Combinatorics". It is generally the nemesis of many students, especially the ones who do not understand why do we need to arrange something, and that too in some weird way. Well I have sympathy for you, but no matter how chaotic our lives be, we still like to maintain some order, and therein comes the concept of ordering, arranging, partitioning and so on. And all of it come together to make a branch of mathematics called Combinatorics.

It will be injustice to combinatorics, if I write just once lesson, so I will try to write a few more, for the moment, I will pick up one of the darling principles of Combinatorics, known as Pigeon-Hole Principle.

Theorem 5.1if n+1 pigeons fly to n holes, there must be a pigeonhole containing at least two pigeons

Well this theorem, look apparently simple and trivial, but its extremely powerful. Lets take a test of it.

Example 5.1 Let A be any set of nineteen integers chosen from the arithmetic progression 1,4, . . . ,100. Prove that there must be two distinct integers in A whose sum is 104.

Now how do we go about this? remember n and n+1. The hint is to make n+1=19. Something clicked?

see we have 34 numbers of the form 3k+1, from 1 to 100. If we do not want a sum of 104 , we will break them in the sets of 2 integers whose sum is 104

{4,100},{7,97}..{49,55} and {1}, {52}. Clearly we have 16 two element sets and 2 one element set.

So if we make a set of 19 integers, we will have to pick both the integers from atleast one of the two element sets, which will give us a sum of 104.

We are done here.

If you still have doubts, let me explain again, suppose you are four friends ( boys) and there are three girls. And each one of you like a girl out of the three. So at least one of the girls will be liked by two boys. :)

Lets solved a more involved example, wherein we need not prove a thing, but find a thing. Some people may be feeling cat does not want us to prove but find. Here is how we do that.

Example 5.2 Let there be n balls with Ram. he decides to colour one ball with colour 1, two balls with colour 2 and so on upto, fifty balls with colour 50. At the end of it , all n balls are used, and no ball is coloured twice. Ram then draws balls from the lot at random, without replacement. What is is the minimum number of balls that he must draw in order to gurantee drawing 10 balls of the same color?

What the hell is his problem. Why coloring and then taking out. Stupid chap. Let us help him with the math now.

see if he picks all the balls with colors which are less than 10 it will come upto (1+2+3..+9)=45.

Now for the worst case he will pick 9 balls each from rest of the balls, which is 41*9

so total is 41*9+45=41*10+4=414. ( avoid multiplying, be watchful)

now if he picks one more ball, atleast one of the set will be of 10. so we are done

he needs to draw 414+1=415 balls.

Practice Problem 5.1 A circular table has exactly 60 chairs around it. There are N people seated at this table in such a way that the next person to be seated must sit next to someone. What is the smallest value of N?

Practice Problem 5.2 We call a set "Sum-free" if no two elements of the set add upto a third element of the set. What is the maximum size of the "sum-free" subset of {1,2,3...2n-1}?

Thats all in this lesson, this is more than enough, if you need more, look into the mock papers, you will find something.

I would like to thank Mr. David Santos, as I have used his book on number system extensively to make this lesson, but I have tried to add my own flavor to it.

Concept 4 Prime Numbers

I was recently reading a blog by one MIT student, wherein he quotes one of his professors, " Mathematicians are annoyingly Precise" and he further adds, " think deeply of simple things". So thats what we will do, be precise and rigorous in our deep thinking of simple things, that is exactly what CAT wants us to do. Lets roll!

Theorem 4.1 Prime numbers are odd, except for 2, and they have exactly two factors, the number and 1 itself.

You would be wondering, why I have started with this, but whole prime number theory is based on this only.

From here, I will formulate something, which I use excessively in problem solving !. But first lets solve an example. This question is taken from My quant problem set III, the link of which can be found," free material for cat".

Example 4.1 Let a,b,c,d be distinct prime numbers satisfying :

2a+3b+5c+7d=162

11a+7b+5c+4d=162

Given that abcd=k. Find the number of distinct values of k?

A)  0                   B) 1                  C)  2                   D) 3                 e) 4

How we go about this? We were told in school, that n variables need n equations, but we have n-2 here. A road-block? No, a call to think deeply. Just see how we can reduce variables or increase equations :) .

We subtract the two equations and get 9a+4b=3d => 4b=3(d-3a)

RHS is divisible by 3, so should be LHS and therefore b=3

put this in the initial equations, and we are sure the max value of a can be =7 ( i leave it to u to figure out how, a hint: all prime numbers are distinct, and we have used 3, we are left with the two smallest as 2 and 5 :) ).

Back again 3a=d-4=>d=3a+4 gives us (a,d)=(5,19),(11,37)..  but clealry the second set wont work, very large values. We found the set, just by using the constraint, all are distinct primes and 3 has been used.

so we have b=3,a=5 d=19, there is no further need to go as we need the no of values of k which will obviously be 1. But for the sake of completeness we can check c=2 :)

Seems like a marathon, but no its a 3-4 minute problem, once you start doing what I want you to !

Now, if you have understood this concept, you should be able to get the practice problem, which is taken from one of the simcats.

Practice Problem 4.1 A boy spends Rs. 81 in buying some pens and pencils. If a pen costs Rs.7 and a pencil Rs 3, What is the ratio of pens to pencils when the maximum number of pens are purchased such that no extra money is given to the shopkeeper?

A) 3:2    B) 2:1   C) 5:4   D) 7:2   E) none of these1

The next concept which I am going to take up is Prime squares:)

Theorem 4.2 : All prime squares ( p>3) are of the form 6k+1, i.e , p^2=6k+1, for all primes p>3.

Lets try to prove this,  any three numbers  (p-1)p(p+1) will be divisible by 6. but as p is a prime greater than 3, it would neither be divisible by 2 nor 3, hence p^2-1=6k so p^2=6k+1.

Some purists will say, that as p is a prime greater than 3, then, p^2-1=24k+1, yupp I agree, but 24k+1 becomes cumbersome to handle sometimes. The proof is simple again, p is odd so both will be divisible by 2 and one by 4. also one of them by 3. hence p^2-1=24k so p^2=24k+1

But, I have always used 6k+1, may be just used to it. You may pick the one that suites you.

Kindly note, this is a necessary condition not a sufficient one, means all prime square will be of form 6k+1, but all no of 6k+1 cant be prime square :)

Lets handle our next example based on this.

Example 4.2 : Find the number of primes p, such that p^2+3p-1 is also a prime?

A quick check will tell 2 does not satisfy and 3 does.

now we check for higher primes

p^2+3p-1=6k+1+3p-1=3(2k+p) hence divisible by 3, not  a prime

So, only one prime p=3 . We are done here !

More to follow, do tell us how you like this, press the rating button on the left :) !

Concept 3 Circle and Triangles ( Part 1)

Geometry as a section wa spretty popular in CAT till 2004, consiting of 1/3rd of the problems and people used to think if they could handle it well they are clear with quant cutoff. And really that used to be the case. Cat has changed the trend reducing geometry every year since and last year in CAT 2007, there was not a single problem from geometry.  But, we can for sure be ready for nice geometry problems, so that if they come, we are up and ready for it.

Geometry has some major theorems. One should be clear about them, the ones on similarity of triangles, congruency of triangles, pythagoras, area and volume formula. Kindly refer to a text book for revising such concepts, I would recommend Quantum Cat By Arihant Publishers. Lets roll then !

The major theorems which we always need are :

Theorem 3.1 Pythagoras Theorem : a^2+b^2=c^2 where a,b,c are sides of a right angled triangle.

Clearly, C is the largest side, we call it hypotenuse.

The triplets of real numbers (a,b,c) which satisfy the above theorem is called pythagorean triplets. They are of real interest in all kinds of work.

Example 3.1 The length of one of the legs of a right triangle exceeds the length of the other leg by 10 cm but is smaller than that of the hypotenuse by 10 cm. Find the hypotenuse.

The obvious solution is  (a-10)^2+a^2=(a+10)^2 ( I have jumped a step)

solving we have a^2-20a=20a =>a=40 ( a can't be zero, its side of a triangle)

hypo is a+10=50

P.s : we have avoided the cumbersome assumption of sides as a,a+10 and a+20

Tipster clue: See this , the smallest integer pythagorean triplet is (3,4,5) so all numbers of the form (3k,4k,5k) will be pythagorean!

Practice Problem 3.1 FInd the sum of the lengths of the sides of a right angled triangle if the Circumradius=15 and inradius=6

Theorem 3.2  Sin law

a/Sin A=b/SinB =c/SIn C=2R   where a,b,c are sides opposite <A , <B and <C respectively and R is circumradius of Triangle ABC.

Very useful theorem, though we have entered the domain of trigonometry, but trigonometry, plane geometry and coordinate geometry are very important for each other to co exist.

Theorem 3.3 Cosine law

a^2=b^2+c^2-2bcCos A ( the notations remain the same as Theorem 3.2). The theorem can be similarly used for other angles too.

Practice Problem 3.2 Find the angle between the diagonal of a rectangle with perimeter 2p and area (3/16)p^2

Example 3.2 Find the length of the base of an isosceles triangle with area S and vertical angle A.

How do we start with this, we can offcourse going to need some basic geometry knowledge. let me tell you all of it. First the vertical angle of an isosceles triangle is the angle between the two equal sides( unless otherwise mentioned). The Perpendicular dropped on the unequal side from the opposite vertex, bisects the vertical angle as well as bisects the side. It means if we have a triangle ABC with AC=AB and AD perpendicular to BC then BD=BC and <BAD=<CAD.

The last thing we need is that area of a triangle is (1/2)bcsinA or (1/2)b^2Sin A for an isosceles triangle as b=c

now given (1/2) b^2sin A=S.......(1)

Now as AD bisects the vertical angle and then use BD=bsin(A/2)

hence BC=2BD=2bSin(A/2)

we can put the value of b from (1) and we are done !

Practice Problem 3.3  Find the largest angle of a triangle in which the altitude and the median drawn from the same vertex divide the angle at the vertex into three equal parts

Lets do a more involved example. This came in IMS SimCat 9. Nice and easy problem, but it might scare you for a moment if you look at the figure they drew. So I am not giving it :)

Example 3.3 In Triangle ABC, AD,BE and CF are the medians which intersect at G. ABCH is trapezium with AH=5units , and BC=10units  and Area( Tr BHC)=35 Sq units. Find the ratio of Area( BDFG): Area( ABCH). ( note we have  H and C on same side of B :) )

Here we again need to know this. The three medians divide the triangle into three triangle of equal area . Also they divide it into three quadrilaterals of equal area. So Area( BDFG)= (1/3)Area(ABC)

Next comes, the traingles drawn on the same base and between same parallel lines have equal area. Hence Area(ABC)=Area(BHC)=35 as we know the base BC, we know the altitude D= 2Area/base=70/10=7

Area of trapezium =(1/2)altitude( sum of paralle sides)= (1/2)7(10+5)

so our ratio is (35/3)/(15.7/2)=2/9

We are done :)

Concept 2 Inequalities I

Concept 2 Inequalities

Lets move on to our next concept, i.e Inequalities. Inequalities are generally present in cat and similar MBA papers, the question can be direct or indirect.

Concept 2.1 AM-GM Inequality

It means that AM( arithemetic mean) of  a set of positive numbers is always greater than or equal to the GM( geometric mean). The equality holds when the numbers are equal

(a+b+c)/3 >=(a+b+c)^(1/3)..........( 2.1)

Example 2.1 If a,b,c are positive numbers prove that (a+b)(b+c)(c+a)>=8abc

what we will do is  use AM-GM multiple times

(a+b)/2 >=sqrt(ab)

=>(a+b)>=2sqrt(ab)

similarly for others

(b+c)>=2sqrt(bc)

(c+a)>=2sqrt(ac)

then multiplying these three inequalities we get the desired result!

Practice Problem 2.1show that (n^n)[(n+1)/2]^(2n)>(n!)^3

Practice Problem 2.2 if x,y,z be the lengths of the sides of a triangle then prove that (x+y+z)^3>=27(x+y-z)(y+z-x)(z+x-y)

Practice Problem 2.3 show that for any natural number n, (n+1)^n>2.4.6....2n

Example 2.2 Show that for any natural number n 2^n>=1 +n.2^[(n-1)/2]

Lets see how we do this

2^n>=1+n.2^[(n-1)/2]

2^n-1>=n.2^[(n-1)/2] ( can you recognise the form?)

its the sum of a GP

we need to use AM-GM on the sum of GP

[1+2+2^2...+2^(n-1)]/n>(1.2.2^2...2^(n-1))^(1/n)

(2^n-1)/n> ( 2^(1+2+3..+n-1))^(1/n)=(2^[n(n-1)/2])^(1/n)=2^((n-1)/2)

so

2^n-1>2^((n-1)/2)

so we are done !!

Concept 2.2 Cauchy- Schwartz Inequality

If a,b,c and x,y,z be real numbers ( positive, negative or zero) then

(ax+by+cz)^2<=(a^2+b^2+c^2)(x^2+y^2+z^2)

Equality holds iff  a:b:c::x:y:z

Example 2.3 if x^4+y^4+z^4 =27 find min value of x^6+y^6+z^6

use cauchy on x^3,y^3,z^3 and  x,y,z

then (x^6+y^6+z^6)(x^2+y^2+z^2)>=(x^4+y^4+z^4)^2....(1)

use cauchy on the numbers x^2,y^2,z^2 and 1,1,1

then (x^4+y^4+z^4)(1+1+1)>=(x^2+y^2+z^2)^2

3(x^4+y^4+z^4)>=(x^2+y^2+z^2)^2...(2)

squaring both sides of 1 and using 2 we get

(x^4+y^4+z^4)^4<=3[(x^6+y^6+z^6)^2](x^4+y^4+z^4)

putting x^4+y^4+z^4=27 and taking positive square root we get

x^6+y^6+z^6>=81

Practice Problem2.4  if a,b,c be positive numbers such that a+b+c=4 find minimum value of a^3+b^3+c^3

Practice Problem 2.5 Find the min value of 2x+y if xy=8 and x,y are positive numbers

For any queries, post your doubts here itself !

Concept 1 Perfect Squares

Concept I Perfect Squares

There has been a huge surge in the number of questions about perfect squares, in almost all mocks. The basic trick to any such question is assuming the number as a perfect square of an integer k and then using techniques of completion of square and then the formula of (a^2-b^2) and solving using divisibility theory

Example I Find all natural n such that n(n+16) is a perfect square

step 1 n(n+16)=k^2

step 2 (n^2+2.8.n+8^2)-8^2=k^2

step3 (n+8+k)(n+8-k)=64

see now lhs and rhs both are integers then both of (n+8-k) and (n+8+k) are divisors of 64. But note that we add the two equations we will get 2n+16, so teh sum of two divisors should be even hence both divisors even or both odd

so n+8+k=32,16,8,4,2 and n+8-k=2,4,8,16,32

but see this n is positive hence k is positive, thus n+8+k>n+8-k
so only two options

and solving we get 2n+16=34,20
so n=9,2

Note : The source of this problem is Pomona Wisconsin mathematics talent search exam!

Practice problem!!
Find the sum of all such positive integers m's such that m^2+25m+19 is a perfect square

Now we will extend the method to other kinds of problems
Basically what we used in the above problem is difference of square method

lets take an example
x^6=y^2+127, find the no of pairs of postive integers (x,y)

first step in this problem is recognising that 127 is a prime
then we move to
(x^3+y)(x^3-y)=127
so clearly 2x^3=128 x=4 and y=63

so one pair (4,63)