Calculus

Set Theory

Set Theory Logo

Pigeonhole Principle

Solved Problems

Example 1.

Prove that any set of \(6\) distinct natural numbers contains two numbers whose difference is divisible by \(5.\)

Solution.

When a number is divided by \(5,\) it can have \(5\) different remainders: \(0,1,2,3,4.\) We have \(6\) distinct numbers. Therefore, by the pigeonhole principle, at least two of them have the same remainder. The difference of these two numbers has remainder \(0\) when divided by \(5,\) that is, it is divisible by \(5.\)

Example 2.

The cells of a \(3 \times 3\) array contain numbers \(-1, 0, 1.\) Prove that at least two of the eight sums on rows, columns and main diagonals are equal.

Solution.

Each of these \(8\) sums can take the following \(7\) values:

\[ - 3, - 2, - 1,0,1,2,3.\]

According to the pigeonhole principle, at least two sums must coincide.

Example 3.

Consider an equilateral triangle with side length \(a = 1.\) Prove that among any \(5\) points inside the equilateral triangle, there always exist two points that are within \(\frac{1}{2}\) units of each other.

Solution.

The midlines of the equilateral triangle divide it into four regular triangles with side \(q = \frac{1}{2}.\)

An equilateral triangle with 5 random points.
Figure 4.

By the pigeonhole principle, at least two of the five points will lie inside one of the four triangles.

It is known that the length of a line segment inside a triangle is less than the length of its longest side. Therefore the distance \(d\) between the two points inside the small triangle is less than \(q:\)

\[d \lt q = \frac{1}{2}.\]

Example 4.

A \(5 \times 6\) chessboard has 19 squares colored black. Prove that there exists a \(2 \times 2\) square in which at least three cells are colored black.

Solution.

We divide the rectangle into \(6\) equal parts, \(5\) cells each.

A 5x6 chessboard with 19 black squares.
Figure 5.

By the generalized pigeonhole principle, there is a part of the chessboard with \(4\) black cells since

\[\left\lceil\frac{n}{m}\right\rceil = \left\lceil\frac{{19}}{{6}}\right\rceil = \left\lceil3\frac{1}{6}\right\rceil = 4.\]

Then the \(2 \times 2\) square in this part has either \(3\) or \(4\) cells colored black.

Example 5.

Prove that if \(7\) natural numbers are chosen at random, then the sum of three of them is divisible by \(3.\)

Solution.

When divided by \(3,\) the remainders can be equal to \(0,1,2.\) So, using the generalized pigeonhole principle, we find that

\[\left\lceil\frac{n}{m}\right\rceil = \left\lceil\frac{{7}}{{3}}\right\rceil = \left\lceil2\frac{1}{3}\right\rceil = 3.\]

This means that there are \(3\) numbers of \(7\) that have the same remainders. Denote this remainder by \(r.\) The sum of the three numbers has the combined remainder \(3r,\) which is divisible by \(3.\) Hence, these numbers are also divisible by \(3.\)

Example 6.

Prove that if the integers \(m\) and \(n\) are coprime, then there is a natural number \(k\) such that \(m^k - 1\) is divisible by \(n.\)

Solution.

Consider \(n + 1\) numbers

\[{m^0} - 1,\;{m^1} - 1,\;{m^2} - 1,\; \ldots ,\;{m^n} - 1.\]

By the pigeonhole principle, there are \(2\) numbers that have the same remainder when divided by \(n.\) Let these numbers be

\[{m^a} - 1 \text{ and } {m^b} - 1,\]

where \(a \lt b.\)

Then their difference

\[\left( {{m^b} - 1} \right) - \left( {{m^a} - 1} \right) = {m^b} - {m^a} = {m^a}\left( {{m^{b - a}} - 1} \right)\]

is also divisible by \(n.\) The first factor \(m^a\) is not divisible by \(n\) because \(m\) and \(n\) are coprime. Hence, the number \(m^k - 1 = m^{b - a} - 1\) is divisible by \(n.\)

Page 1 Page 2