This principle sounds so obvious:

If we put N + 1 or more pigeons into N pigeon holes, then at least one pigeon hole will contain two or more pigeons.

Using this principle, however, one can solve a whole variety of problems.

1. One million trees grow in a forest. It is known that no tree has more than 600,000 leaves. Show that at any moment there are two trees in the forest that have exactly the same number of leaves.
2. Thirteen integer numbers are given. Show that there are two numbers among them whose difference is a multiple of 12.
3. 1. Show that in any group of five people, there are two who have the same number of friends within the group.
   2. Show that in any group of people, there are two who have the same number of friends within the group.
      If A is a friend of B, then B is a friend of A.
4. A plane is colored blue and red. Is it always possible to find two points of the same color exactly 1 inch apart? Is it always possible to find two points of different colors exactly 1 inch apart?

   In solving the following problem, use a more general principle, which can be called “General Pigeon Hole Principle:” If we put Nk + 1 or more pigeons into N pigeon holes, then at least one pigeon hole will contain k + 1 or more pigeons.

5. There are twenty-five students in a class. Each got an A, a B, or a C for a test. Show that there are at least nine students who received the same grade.

Hint to problems 1 -- 5. In each problem, identify “pigeons” and corresponding “pigeon holes.”

See solutions.

1. Trees are pigeons and numbers of their leaves are pigeon holes. As there are more pigeons than pigeon holes, there will be a pigeon hole with more than one pigeon in it.
2. There are only twelve possible remainders when a number is divided by 12: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and 11. These 12 different remainders are pigeon holes, while thirteen numbers are pigeons.
3. 1. In a group of five people, one can have no friend, or one friend, or two friends, or three friends, or four friends (be friends with everyone in the group). It looks like there are five pigeon holes (possible numbers of friends) but actually, if someone in a group has four friends, there cannot be anyone with no friends in that group. So there are only four pigeon holes: either zero through three friends, or one through four friends. Pigeons are five people of the group.
   2. Similar to 3(a), numbers of friends are pigeon holes, and people are pigeons. There are n pigeons and only n - 1 pigeon holes, as in the same group there cannot be a person without friends and a person who is friends with everyone.
4. Think of an equilateral triangle with each side exactly 1 inch long. At least two of its vertices have to be of the same color (colors are pigeon holes, and vertices of the triangle are pigeons). This proves that there have to be two points of the same color exactly 1 inch apart.
   Of course, if all points of the plane are colored the same color (blue or red), it’s impossible to find two points of different color any distance apart. But suppose there is at least one red point and at least one blue point on the plane. Then it is possible to find two points of different colors exactly 1 inch apart on this plane, and this is how:
   1. Chose two points of different color. If they are exactly 1 inch apart, the problem is solved.
   2. If the distance between them is less than 1 inch, mark a point which is 1 inch away of each of these points. No matter whether it is blue or red, it will have a point of different color exactly 1 inch away.
   3. If the distance between originally chosen points of different color is greater than 1 inch, connect these points with a segment. Look at the point on this segment which is 1 inch away from the red point (and so one inch closer to the blue point than the original red point). If this new point is blue, the problem is solved. If it is red, replace the original red point by this one, and continue to use this algorithm. Eventually the distance between the red point and the blue point that you are considering has to become 1 inch or less.
5. There are 25 = 3 × 8 + 1 students (pigeons) and 3 possible grades (pigeon holes); therefore, by the General Pigeon Hole principle, there must be more than 8 students with the same grade.
   Another solution (by contradiction): suppose that there were not 9 students with the same grade. In this case, at most 8 students could get an A, at most 8 students could get a B, and at most 8 students could get a C. Therefore, there could not be more than 8 × 3 = 24 students in this class, but we know there were 25. The assumption was wrong.