341Pigeon Hole Principle
Let A be any set of 20 distinct integers chosen from the arithmetic progression 1,4,7,..............,100. Prove that there must be two distinct integers in A whoe sum is 104 .
-
UP 0 DOWN 0 0 4
4 Answers
1[12] there was this pigeon hole thing somewhere else in the forum as well even then prophet sir pointed that out ........
well are problems using this principle going to come in JEE 09 [7]
341Not likely -this is more competition math. If you have time just read up a bit on it. The principle is sheer common sense (though no used this till Dirichlet)
This one is a Putnam problem and is a standard example for PHP
What they do is to write the elements of the set as:
{1}, {52}, {4,100}, {7,97}, {10,94}, ..., {49,55}
So now if you choose 20 integers, you will end up choosing atleast one pair that adds up to 104.
62to add to Prophet's comment, I wud say that this is a must read for Olympiad preparations.
It is so easy that one can understand it even in class VIII.
The name is also childish I thought when I first read it ;)
But yeah i very important principle.. read it when you have free time from wiki or some other source.
It is used a lot in permutation problems of olympiad kind.
