Pigeonhole Principle/Solutions

These are the solutions to the problems related to the pigeonhole principle.

Introductory

This page is in need of some relevant examples or practice problems. Help us out by adding some. Thanks.

Intermediate

M1

The maximum number of friends one person in the group can have is 4, and the minimum is 0.

M2

For the difference to be a multiple of 5, the two integers must have the same remainder when divided by 5. Since there are 5 possible remainders (0-4), by the pigeonhole principle, at least two of the integers must share the same remainder. Thus, the answer is 1 (E).

Olympiad

O1

By the Triangle Inequality Theorem, a side of a triangle can be less than the sum of the other two sides. Assume that the first two segments are as short as possible (1 inch). For a triangle to not exist, the next term must be 2, then 3, 5, 8, and 13 (this is the Fibonacci sequence). The 7th term is 13, which is greater than 10 inches.

O2

For the difference to be a multiple of 7, the integers must have equal modulo 7 residues. To avoid having 15 with the same residue, 14 numbers with different modulo 7 residues can be picked (). Thus, two numbers are left over and have to share a modulo 7 residue with the other numbers under the pigeonhole principle.

O3

See this article.

O4

The area of the circle is . For the ten points not to be within 2 units from each other, consider circles of 1 diameter each around each of the points. If any 2 of the circles intersect, then the respective centers are within 2 units of each other. , which is less than 10, which means that less than 10 circles can fit into the larger circle without intersecting (pigeonhole principle). Thus, not all 10 points can be within 2 units of each other and be inside the circle.

O7

The pigeonhole principle is used in these solutions (PDF).