In this lesson, 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 1: if 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 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 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 . (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.
I would like to thank Mr. David Santos, as I have used his book on number system to make this lesson, but I have tried to add my own flavor to it.
Hello, I have a doubt on the 2nd problem. I think the question should have been " what is the maximum no.of balls". Because, if the guy is damn lucky, he could draw 10 balls of same colour in the 1st attempt, ie he have to draw only 10 balls. Of course, this is a possible case and i think it will be the answer for the question " what is the minimum no.of ball". Pls correct me if am wrong.
gud lesson sir…. really ….. I know You are different….
To the question by Tanni_chats:
a pupil can go for swimming on 2,3,4 or 5 days.
No. of ways of going for 5 days - 1
No. of ways of going for 4 days - 5
No. of ways of going for 3 days - 10
No. of ways of going for 2 days - 10
Total - 26
The 27th pupil will have to select any one of these combinations and hence will end up going on the same days as another pupil.
superb prob sir……. theorem will definatly help us
i hve a problm..thr are 27 students who go for swimming on sum days from monday to friday in a certain week…if each pupil goes for swimming atleast twice show that there must be 2 pupils who go swimming exactly the same days///…. please help
Problem Analysis-
--------
This is a problem of Combination.
Let us try to understand the concept related to the problem.
Let us consider the days from Mon-Friday as pigeon holes and label respective pigeon holes as A to E.
Now from the concept of Combination, following is valid(starting
from min of 2 days):
→ A single student opting for 2 days can opt for any one out of (10
C 1) combinations.
AB, AC, AD, AE, BC, BD, BE, CD, CE, DE
→ A single student opting for 3 days can opt for any one out of (10
C 1) combinations.
ABC, ABD,
ABE, BCD,
BCE, CDE,
ACD, ACE,
ADE and BDE
→ A single student opting for 4 days can opt for any one out of (4
C 1) combinations.
ABD, ABDE,
BCDE, ACDE
→ A single student opting for 5 days can opt for only one
combinations.
Now let us consider the cases:
Case 1- One student(Student No. 1) opting for 5 days swimming.
In such a case the remaining 27-1=26, if opting for 2 days swimming
would have any one out of (10 C 1) combinations. So there would be
overlapping for remaining 26.
or
In such a case the remaining 27-1=26, if opting for 3 days swimming
would have any one out of (10 C 1) combinations. So there would
overlapping for remaining 26.
or
In such a case the remaining 27-1=26, if opting for 4 days swimming
would have any one out of (4 C 1) combinations. So there would be
overlapping for remaining 26.
or
In such a case the remaining 27-1=26, if opting for 5 days swimming
would have one. So there would be overlapping for remaining 26.
Note: For Case 1 there would surely be 2 students swimming on the
same day.
Case 2- One student(Student No. 1) opting for 4 days
swimming.
In such a case the remaining 27-1=26, if opting for 2 days swimming
would have any one out of (10 C 1) that includes (4 C 1 comb with
one left out) cominations which overlap with Student No. 1. So
there would be overlapping for remaining 26.
or
In such a case the remaining 27-1=26, if opting for 3 days swimming
would have any one out of (10 C 1) that includes (6 C 1 comb with
one left out) cominations which overlap with Student No. 1. So
there would be overlapping for remaining 26.
or
In such a case the remaining 27-1=26, if opting for 4 days swimming
would have any one out of (4 C 1) that includes (3 C 1 comb with
one left out) cominations which overlap with Student No. 1. So
there would be overlapping for remaining 26.
or
In such a case the remaining 27-1=26, if opting for 5 days swimming
would have one that overlap with Student No. 1. So there would be
overlapping for remaining 26.
Note: For Case 2 there would surely be 2 students swimming on the
same day.
Case 3- One student(Student No. 1) opting for 3 days
swimming.
In such a case out of the remaining 27-1=26 there will be one
student, who if opting for 2 days swimming would not overlap with
Student No. 1. So there is one case of no-overlapping one out of
remaining 26. Remaining 25 would be overlapping.
or
In such a case the remaining 27-1=26, if opting for 3 days swimming
would have any one out of (10 C 1) that includes (3 C 1 comb with
two left out) cominations which overlap with Student No. 1. So
there would be overlapping for remaining 26.
or
In such a case the remaining 27-1=26, if opting for 4 days swimming
would have any one out of (4 C 1) that includes (3 C 1 comb with
one left out) cominations which overlap with Student No. 1. So
there would be overlapping for remaining 26.
or
In such a case the remaining 27-1=26, if opting for 5 days swimming
would have one that overlap with Student No. 1. So there would be
overlapping for remaining 26.
Note: Incase Case 3 there would be one case where there would not
be 2 students swimming on the same day.
Case 4- One student(Student No. 1) opting for 2 days
swimming.
In such a case out of the remaining 27-1=26 there will be one
student, who if opting for 2 days swimming would not overlap with
Student No. 1. So there is one case of no-overlapping one out of
remaining 26. Remaining 25 would be overlapping.
or
In such a case out of the remaining 27-1=26 there will be one
student, who if opting for 2 days swimming would not overlap with
Student No. 1. So there is one case of no-overlapping one out of
remaining 26. Remaining 25 would be overlapping.
or
In such a case the remaining 27-1=26, if opting for 4 days swimming
would have any one out of (4 C 1) that includes (2 C 1 comb with
one left out) cominations which overlap with Student No. 1. So
there would be overlapping for remaining 26.
or
In such a case the remaining 27-1=26, if opting for 5 days swimming
would have one that overlap with Student No. 1. So there would be
overlapping for remaining 26.
Note: Incase Case 3 there would be one case where there would not
be 2 students swimming on the same day.
Conclusion-
-----
For Case 1 and Case 2, there will be overlapping, which means there
would surely be 2 students swimming on the same day.
For Case 3 and Case 4, there will be no overlapping, which means
there would be one case where there would not be 2 students
swimming on the same day.
gr8 lesson… atleast now i noe something abt combinatorix… thanks a lot…:)
u r special sir comes in a different angle
awesome man..ppl like u make our cat easier
Question-â€"-you have 3 kinds of balls(S,B,L)small,big,large. u paint them (one ball can be painted with 1
colour only ) randomly with 4 colours (R,G,Y,W)red,green,yellow,white. suppose u put â€â€Nâ€â€ balls into 5
boxes B1,B2,B3,B4,B5. now what should be the least value of N be so that u pickup atleast 3 same balls?
Answer-â€"suppose u put 3 balls in each box in the beginning without colour in mind (N=15). now if u put
another ball in any of the boxes u are sure 2 have atleast 2 balls of the same size in some box. now u put4
more balls in each box(N=60),if now u put another ball in any ox u are sure 2 have atleast 2 same balls in a
box. now double this(N=120) and u are sure 2 have atleast 2 same balls in some container and now if u
put another ball in any container u will be sure of having atleast 3 same balls in some box. so the answer to
the above question is (N=121)……….i.e((53)4)*2+1=121
simply superb.please write few more lessons.
good problem buddy……..thanks for ur sincere efforts
Ok, we have the set of integers 1, 4, 7, … , 97, 100. The form of these integers is 1+3k where k is between 0 to 33, so we have a total of 34 of these integers. Now, we want to break these set into pairs that sum up to 104, and if we have less than 18 groups, then choosing 19 elements mean that we have at least 1 full group in our set, so we have at least one pair that sums of up 104.
As demonstrated above, we have the pairs (4, 100), (97, 7), … (we have 16 of these) and 2 single integers, 1 and 52, which don't add with with anything to 104. Now, if we choose 19 elements trying to avoid the pairs so that we don't have a sum of 104, we first choose the 2 singles, then 1 element from each pair. Now we have 18 elements that have no sums of 104 in them. But we need one more element, so we must choose it from one of the pairs. Thus in our 19-element set, we must have at least one pair of integers summing up to 104.
Does this make sense?
I didn't get the answer to the 1st problem clearly. Can some1 explain it to me?
where did you get confused? which step?
Sorry Suresh Bala Iam not able to understand can u be more clearer…in last example it gets messed up
The second example is actually pretty simple when you think about it. What's the maximum number of balls you can take out without getting 10 balls with the same colour? Then if you add one ball, you must 10 balls of the same colour.
So first of all, for colours 1 to 9, we don't even have 10 balls, so let's take those out. There are 1+2+…9 = 45 balls of these. Now, we don't want 10 balls of any of the 41 remaining colours, so the greatest number of these we can take out is 9 per colour. That's 41 * 9. In total we have at most 41 * 9 + 45 as the maximum number with no 10 balls of the same colours. If we take out 1 more ball now, we must have 10 balls of the same colour, so the answer is 41(9)45+1 = 415 balls.
Does that make sense?
I read Shakespeare and the Bible, and I can shoot dice. That's what I call a liberal education.
© 2008 - 2013 Learnhub Marketing View Our Service Agreement and Privacy Policy
Are you an indian student planning on attending college? Our expert counselling can help.
How does counselling work?
Colleges
Study Abroad
Post Comments
i dont think it will be maximum because maximum can go any number beyond 415 and between the total number of balls available
the question said "guarantee"!!!