CAT 2013 Exam

51365 Followers - 339 Articles - 1573 Questions and Answers

CAT 2010: Pigeon - Hole Principle

by Suresh


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 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.

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.

31 Comments
    Binoop
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    Binoop PulikkalTue, 24 Nov 2009 14:05:53 -0000

    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.

    Post Comments

    holly
    Rating
    1
    Rate Up
    hollyMon, 25 Jun 2012 09:40:10 -0000

    i dont think it will be maximum because maximum can go any number beyond 415 and between the total number of balls available

    Shuvajit
    Rating
    1
    Rate Up
    ShuvajitWed, 16 Jan 2013 21:33:26 -0000

    the question said "guarantee"!!!

    Reply to This
    venkivety
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    Venkateswara Reddy.MMon, 26 Oct 2009 06:14:13 -0000

    gud lesson sir…. really ….. I know You are different….

    Post Comments

    Reply to This
    meetnaren
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    NarenFri, 09 Oct 2009 16:49:35 -0000

    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.

    Post Comments

    Reply to This
    rachits21792
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    rachits21792Fri, 09 Oct 2009 10:48:53 -0000

    superb prob sir……. theorem will definatly help us

    Post Comments

    Reply to This
    sahitya_bits
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    sahityaFri, 21 Aug 2009 12:27:03 -0000

    how did we get 3k+1 in the first example?

    Post Comments

    Reply to This
    jha_avin
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    jha_avinTue, 11 Aug 2009 17:42:12 -0000

    cotent errased as it was replied by mistake.

    Post Comments

    Reply to This
    dieselboy
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    dieselboyTue, 04 Aug 2009 15:15:51 -0000

    Good Job ! Hope you continue really long with this great work !

    Post Comments

    Reply to This
    tanni_chats
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    taniya sahaMon, 22 Jun 2009 07:01:59 -0000

    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

    Post Comments

    jha_avin
    Rating
    1
    Rate Up
    jha_avinTue, 11 Aug 2009 17:43:26 -0000

    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.

    jha_avin
    Rating
    1
    Rate Up
    jha_avinTue, 11 Aug 2009 17:50:59 -0000

    I had alligned the content of this posting but it did not work.
    Please let me know incase this is not comprehensive.

    Thanks
    Avinash

    Reply to This
    surej
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    surej jayanSun, 31 May 2009 13:48:33 -0000

    it's great yar

    Post Comments

    Reply to This
    funduu
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    Ashwani Kumar DixitSat, 30 May 2009 17:46:55 -0000

    superb dude!!!!!!!

    Post Comments

    Reply to This
    bschool_23
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    PurviSat, 14 Mar 2009 14:24:18 -0000

    dis is awesome..thanx a ton to Suresh !

    Post Comments

    Sureshbala
    Rating
    1
    Rate Up
    SureshMon, 29 Jun 2009 08:55:35 -0000

    Thank You…Pleasure is mine

    Reply to This
    hazel_spark
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    Chandana ShekarSun, 08 Feb 2009 16:59:33 -0000

    gr8 lesson… atleast now i noe something abt combinatorix… thanks a lot…:)

    Post Comments

    Sureshbala
    Rating
    1
    Rate Up
    SureshMon, 29 Jun 2009 08:55:14 -0000

    Nice to hear that you liked this lesson…More lessons will follow

    Reply to This
    Sureshbala
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    SureshFri, 30 Jan 2009 13:11:23 -0000

    Thank you Santosh…Hope you are doing well….

    Post Comments

    singhsumitkrishnabihari
    Rating
    1
    Rate Up
    Thu, 09 Jul 2009 06:31:16 -0000

    hello sureshbala, i am sumit .i had not understood your lesson about pigeon hole.

    Sureshbala
    Rating
    1
    Rate Up
    SureshWed, 19 Aug 2009 21:22:38 -0000

    Hi,

    Could you please mention the area that is not clear to you? I will try to clarify your doubts.

    eaakbari
    Rating
    1
    Rate Up
    eaakbariSun, 14 Mar 2010 05:25:38 -0000

    Hello Mr Suresh. Its a hugely informative article you have here. But I am a GMAT aspirant. Will I need this

    Reply to This
    santosh gupta
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    santosh guptaTue, 20 Jan 2009 08:23:24 -0000

    u r special sir comes in a different angle

    Post Comments

    Reply to This
    Invincible Ishan
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    Ishan AggarwalThu, 15 Jan 2009 12:09:20 -0000

    thanx 4 this lesson!

    Post Comments

    Reply to This
    santhemaster
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    santhemasterTue, 13 Jan 2009 12:43:43 -0000

    Post Comments

    Reply to This
    dessai_saurabh
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    saurabh prabhu dessaiSat, 10 Jan 2009 17:55:00 -0000

    awesome man..ppl like u make our cat easier

    Post Comments

    Reply to This
    thayi_b4u2009
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    thayi_b4u2009Fri, 02 Jan 2009 17:31:24 -0000

    Post Comments

    Reply to This
    dhirajdj123
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    Dhiraj Kumar BediTue, 30 Dec 2008 07:12:29 -0000

    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

    Post Comments

    lamaster
    Rating
    0
    Rate Up
    master laFri, 13 Mar 2009 16:50:06 -0000

    ((53)4)*2+1=121
    r u sure there should be 53….
    i didnt get it.

    Reply to This
    anildasari
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    Anil DasariFri, 26 Dec 2008 12:47:10 -0000

    simply superb.please write few more lessons.

    Post Comments

    Reply to This
    kalpesh_sharma
    Vote
    Current Rating
    1
    Rate Up
    Rate Down
    Kalpesh SharmaTue, 23 Dec 2008 07:49:00 -0000

    Good job bro… Thanks

    Post Comments

    Reply to This
    vikram431
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    vikram reddy veeranagariTue, 16 Dec 2008 19:27:29 -0000

    good problem buddy……..thanks for ur sincere efforts

    Post Comments

    Reply to This
    neeleshs1
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    neeleshs1Sat, 13 Dec 2008 15:21:57 -0000

    it was really mindblowing

    Post Comments

    Reply to This
    nawneet
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    nawneetSat, 13 Dec 2008 13:05:31 -0000

    Post Comments

    Reply to This
    Avirup
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    AvirupSun, 07 Dec 2008 13:13:49 -0000

    Damn good explanation but I didn't get the second explanation.

    Post Comments

    Reply to This
    oLahav
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    Oren LahavThu, 04 Dec 2008 15:11:25 -0000

    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?

    Post Comments

    Reply to This
    phoenixrohan
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    phoenixrohanThu, 04 Dec 2008 12:42:17 -0000

    I didn't get the answer to the 1st problem clearly. Can some1 explain it to me?

    Post Comments

    chandra_avinash
    Rating
    1
    Rate Up
    Avinash ChandraFri, 26 Jun 2009 14:01:55 -0000

    where did you get confused? which step?

    Reply to This
    oLahav
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    Oren LahavThu, 20 Nov 2008 16:55:34 -0000

    By the way, great lesson Surresh!

    Post Comments

    Reply to This
    Blues
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    Wed, 19 Nov 2008 18:27:32 -0000

    Sorry Suresh Bala Iam not able to understand can u be more clearer…in last example it gets messed up

    Post Comments

    oLahav
    Rating
    0
    Rate Up
    Oren LahavThu, 20 Nov 2008 16:33:09 -0000

    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?

    Reply to This
    muna
    Vote
    Current Rating
    0
    Rate Up
    Rate Down
    munaMon, 17 Nov 2008 10:03:11 -0000

    yes it was amazing

    Post Comments

    Reply to This

Your Comment

Avatar
Vote
Current Rating
0
Rate Up
Rate Down
Have an account? Log In

Textile is Enabled. View Reference.
Lead_arrow_side

Think Beyond CAT Apply to Top MBA Colleges in the World

Fill out your information accurately in this form to learn more about the world's Best MBA programs.

About the Author

Sureshbala
Name:
About: Worked for more than 6 years in renowned corporate institutes as their core faculty/lead content developer for C.A.T,G.R.E, G.M.A.T and Campus Recruitment Training Programs.

Last Updated At Jan 16, 2013
8840 Views

31 Comments