Pigeonhole Principle : Simple Form
- "If we put n balls in m boxes, and m < n, then at least one box must have
more than n/m balls."
Examples
For any six people in a party, either three of them know each other or three of them do not know each other.
There are at least two people in Hong Kong who have the same number of hairs.
Pigeonhole Principle : Strong Form
- "If we put kn +1 balls in n boxes, then
at least one box must contain k + 1 or
more balls."
Question 1
Consider an equilateral triangular playground. Each side of the
playground is two meters long. Now there are five children in the
playground. If the distance between any of two is less than or equal
to one meter, then these two children will fight with each other.
Is it possible to put these five children in the playground so that
they would not fight with each other? In other words, is it possible
to put five points in the above triangle in such a way that the
distance between any two point is strictly greater than one?
Question 2
Suppose there are 100 students in a school and there are at least two students with the same number of friends.
Note that if A is a friend of B, then B must also be a friend of A.
Show that it is possible that a student does not have any friend.
|
