Jump To Content
AIEEE Prep

Community

AIEEE Prep

Primary Navigation

Pigeon- Hole Principle

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.

monali tanna
  • Authority 0
Post Body
monali tanna said:

it was fabulous

  • Quote
  • Posted 2 months ago.
hassan_k
  • Authority 33
Post Body
hassan_k said in response to:
monali tanna
monali tanna’s post:
Citation Body

it was fabulous

This is just amazing. I should thank Sureshbala for his invaluable contribution.

  • Quote
  • Posted about 1 month ago.
muna
  • Authority 0
Post Body
muna said:

yes it was amazing

  • Quote
  • Posted about 1 month ago.
Blues
  • Authority 62
Post Body
Blues said:

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

  • Quote
  • Posted about 1 month ago.
oLahav
  • Authority 720
Post Body
oLahav said in response to:
Blues
Blues’ post:
Citation Body

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?

  • Quote
  • Posted about 1 month ago.
oLahav
  • Authority 720
Post Body
oLahav said:

By the way, great lesson Surresh!

  • Quote
  • Posted about 1 month ago.
phoenixrohan
  • Authority 21
Post Body
phoenixrohan said:

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

  • Quote
  • Posted about 1 month ago.
oLahav
  • Authority 720
Post Body
oLahav said:

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?

  • Quote
  • Posted about 1 month ago.
Avirup
  • Authority 0
Post Body
Avirup said:

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

  • Quote
  • Posted about 1 month ago.
nawneet
  • Authority 0
Post Body
nawneet said:

THANKS

  • Quote
  • Posted 24 days ago.
neeleshs1
  • Authority 55
Post Body
neeleshs1 said:

it was really mindblowing

  • Quote
  • Posted 24 days ago.
vikram431
  • Authority 20
Post Body
vikram431 said:

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

  • Quote
  • Posted 21 days ago.
kalpesh_sharma
  • Authority 17
Post Body
kalpesh_sharma said:

Good job bro… Thanks

  • Quote
  • Posted 14 days ago.
anildasari
  • Authority 5
Post Body
anildasari said:

simply superb.please write few more lessons.

  • Quote
  • Posted 11 days ago.
anildasari
  • Authority 5
Post Body
anildasari said:

simply superb.please write few more lessons.

  • Quote
  • Posted 11 days ago.
dhirajdj123
  • Authority 18
Post Body
dhirajdj123 said:

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

  • Quote
  • Posted 7 days ago.
dhirajdj123
  • Authority 18
Post Body
dhirajdj123 said:

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

  • Quote
  • Posted 7 days ago.
thayi_b4u2009
  • Authority 0
Post Body
thayi_b4u2009 said:

superb

  • Quote
  • Posted 4 days ago.
  • Your comment will be modifiable for 10 minutes after posted.

Page Author

Avatar
Sureshbala
Name
Sureshbala

From Here You Can…

Information

Most Recent Related Content

Published In…

This work is public domain.