Ultimate Quant Marathon Blog For IIM CAT

For All Your Quant Queries

Concept 5 Pigeon- Hole Principle

with 6 comments


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.

Written by Implex

September 24, 2008 at 2:09 pm

6 Responses

Subscribe to comments with RSS.

  1. 5.1. 20[Every 3n-2 seat must have some one seated]
    5.2. n[Not very sure]

    Celebrating Life

    September 24, 2008 at 5:20 pm

  2. 5.1 is write
    5.2 is wrong try again

    outtimed

    September 24, 2008 at 5:57 pm

  3. sorry, n is right🙂

    outtimed

    September 24, 2008 at 7:01 pm

  4. can you please explain me the steps for answer of 5.2…

    CATastrophe08

    September 26, 2008 at 11:13 pm

  5. There are two ways to tackle this

    either we divide it in {1,3,5..,2n-1} and {2,4,6..,2n-2}
    the first set had n terms and no two can add to the third as sum will be even but the set is of odd numbers.hence max such set size is n

    other way is {n,n+1,…,2n-1}
    the sum of any two numbers will be more than the largest number
    if we include any more number, this condition will fail ..
    Hence this is a max such set
    of n elements

    outtimed

    September 27, 2008 at 12:48 am

  6. THnx outtimed

    CATastrophe08

    October 1, 2008 at 2:53 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: