Pigeon hole principle is quite easy to understand. Now look in this pictures. Suppose 10 pigeons are about to fly into 9 holes. Then there must be at least one hole that contain more than 1 pigeon. As a real example you can see here.U may understand, it is impossible to have all the holes contain no more than 1 pigeon! (unless pigeon fly fly then disappear haha).
The problems here are all have solution. But i will post them in 2 week more time. I reason is, i want you guys to try to solve it together and get to know and learn from each other. For those who can solve please be sure to post yr solution in 2 week time. I would appreciate that. It require somehow my effort to post and write solution, So would you appreciate my effort by simply try to solve the problem and post yr good solution? I'm sure all mathematician like other to admire their solution including me.:D
As Smey has stated, The pigeon Hole principle is simple. Yet it application is so useful. He also posted some quite useful theorem, so you should take note it...
In my opinion, pigeon hole principle should be called dirichlet principle. Dirichlet was the one we owed for that theorem. There are two important theorem you should take note:
Theorem 1 : If k+1 or more objects are placed into the k boxes, the there is at least one box containing two or more of the objects.
Theorem 2: Generalizing: Let there be k1 boxes. If N or more objects are placed into the k boxes, then there is at least one box contaiing at least [N/k]+1 objects, where [a] denote the floor ceiling function of integer a. [4.5]=4 [-3.1]=-4.
As i have commited, this blog is for all level. I won't post problems that too hard nor too easy. Enjoy yr level!
Beginner Level:
1) A drawer contains 10 black socks and 10 white socks. You reach in and pull some out without looking at them. What is the least number of socks you must pull out to be sure to get 4 of the same color?
2) Show that in a group of 85 people at least 4 must have the same first initial of their names.
3) A bowl contains eight red balls, ten green balls and nine blue balls. A student selects balls at random without looking at them.
(a) What is the minimum number of balls the student must select to be sure of having at least two balls of the same color?
(b) What is the min number of balls the student must select to be sure of having at least three balls of the same color?
(c) What is the min number of balls the student must select to be sure of having at least three GREEN balls?
Intermediate level:
1) Let ABCD be a rectangle with AB=8, BC=9. Show that if select seven points in the interior of the rectangle, there are at lest two whose distance apart is less than or equal to 5.
2) There are 5 distinct points with integer coordinates in the {x,y} plane. Show that there must exist at least one pair of these points such that the midpoint of the line joining these two points also has integer coordinates.
3) Let S={2,5,8,11,14,...,71,74,77,80}. How many elements need to be selected from S to ensure that there will be at least two whose sum is 82.
Slightly Advance Level
1) Bill sent out at least one SMS message each minute during a period of exactly one hour. He sent a total of 70 messages over this duration. All these messages were sent to 16 friends and some of them received more than one message from him. Prove that there was a duration of a number of (consecutive) minute which bill sent out exactly 49 SMS messages.
2)Let S be a set of eight positive integers each of which is less than 30. Show that there must be two distinct subsets of S whose elements add up to the same sum. For instance, if the eight numbers are {2,4,5,8,12,15,18,24} , the two distinct subsets can be {2,4,12,15} and {4 , 5, 24}. The sum of both of these is 33.
3) Prove that in any permutation of the twenty_four members 1, 2, 3,..., 24 there must be at least an occurrence of four consecutive positions in the permutation containing numbers that are less than 20.
4) In a box there is a deck of personal identity cards. Each card contains a birthday information (d,m,y) where d, m, y are integer numbers referring to date, month and year respectively. Suppose you reach in the box and draw some cards without looking at them. What is the least number of cards you must draw so as to get two cards, whose birthdays (d1,m1,y1) and (d2,m2,y2) have an even sum. i.e (d1+m1+y1)+(d2+m2+y2) is even?
5) Jack picks 25 integers from 51, 52, 53, ... 97 and 98. Prove that among the 25 integers are three integers whose digits sum up to the same amount. Fore example, the sum of the digits of integer 52 is 7, which is the same as that of the integers 61, and 70.
Advance Level!
1) Given 27 distinct integers, prove that there must be 2 integers whose sum or difference is divisible by 50.
2) Prove that there exist integer x>3 such that 3^x has remainder 1 when divide by 10^10.
3) Given any 5 distinct real number a1, a2, a3,a4,a5. Prove that regardless of how the 5 number are chosen, we can always find two index i, j of number such that a[i]-a[j] is between in gap ]0, 1+a[i]a[j] [
