Skip to main content
\(\renewcommand{\chaptermark}[1]{\markboth{\MakeUppercase{ #1}}{\thechapter~ #1}} \renewcommand{\sectionmark}[1]{} \newcommand{\abs}[1]{\left|#1\right|} \renewcommand{\theenumi}{5.\arabic{enumi}} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\norma}[1]{\left\|#1\right\|} \newcommand{\BM}[1]{\text{\boldmath$#1$}} \newcommand{\halmaz}[1]{\left\{\,#1\,\right\}} \newcommand{\halmazvonal}[2]{\left\{\,#1\mid #2\,\right\}} \newcommand{\halmazpont}[2]{\left\{\,#1:#2\,\right\}} \newcommand{\N}{\mathbb{N}} \newcommand{\len}{\norm} \newcommand{\var}[2][]{v_{#1}\left(#2\right)} \newcommand{\vari}[2]{v_{#1}\left(#2\right)} \newcommand{\size}[2][]{s_{#1}\left(#2\right)} \newcommand{\dep}[2][]{d_{#1}\left(#2\right)} \newcommand{\sizestar}[2][]{s_{#1}^*\left(#2\right)} \newcommand{\depstar}[2][]{d_{#1}^*\left(#2\right)} \renewcommand{\headrulewidth}{0pt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section3.4Pigeonhole principle

In this section we study the so-called pigeonhole principle which is a simple tool to prove several interesting results. First we prove the simplest form of the pigeonhole principle.

Assume that the statement is false. That is, each pigeonhole contains at most one pigeon. In this case the total number of pigeons is at most \(n\text{,}\) a contradiction.

One can easily generalize the above theorem. We have the following.

Again we prove the statement by contradiction. Assume that the statement is false, that is, each pigeonhole contains at most \(m\) pigeons. We obtain that the total number of pigeons is at most \(mn\text{,}\) a contradiction since there are \(mn+1\) pigeons.

Finally we prove a version where the pigeonholes may contain different number of pigeons.

Suppose that the first pigeonhole contains at most \(m_1-1\) pigeons, the second contains at most \(m_2-1\) pigeons etc., the \(n\)th pigeonhole contains at most \(m_n-1\) pigeons. The total number of pigeons contained in the \(n\) pigeonholes can be at most

\begin{equation*} (m_1-1)+(m_2-1)+\ldots+(m_n-1)=m_1+m_2+\ldots+m_n-n\text{,} \end{equation*}

a contradiction since there are \(m_1+m_2+\ldots+m_n-n+1\) pigeons.

To apply the pigeonhole principle one has to decide what the pigeons are. Then one has to identify the pigeonholes in such a way that if two pigeons are in the same pigeonhole, then they have some special property in common. It is important that we need more pigeons than pigeonholes. In what follows we solve several concrete problems by using the pigeonhole principle.

We apply the pigeonhole principle and the Division algorithm. Consider the integers \(a_n=\sum_{k=0}^n 10^k\) for \(n=0,1,2,3,4,5\text{.}\) We can write these numbers as \(q_n\cdot 6+r_n\text{,}\) where \(q_n\) is the quotient and \(r_n\) is the remainder, so \(0\leq r_n\lt 6\text{.}\) There are six possibilities for \(r_n\) and there are six integers \(a_0,a_1,\ldots,a_5\text{.}\) The numbers \(a_0,a_1,\ldots,a_5\) are odd integers while 6 is even, hence \(r_n\neq 0\) for all \(n\text{.}\) We have that \(r_n\in\halmaz{1,2,3,4,5}\) for all \(n\text{.}\) There are only 5 pigeonholes (possible remainders) and 6 pigeons (integers \(a_n\)). We obtain that there are at least two integers having the same remainder, say, \(a_{m_1}\) and \(a_{m_2}\text{,}\) where \(m_1\lt m_2\text{.}\) In this case \(a_{m_2}-a_{m_1}\) is divisible by 6 and all the digits are zeroes and ones.

\(n\) \(a_n\) \(q_n\cdot 6+r_n\)
0 1 \(0\cdot 6+1\)
1 11 \(1\cdot 6+5\)
2 111 \(18\cdot 6+3\)
3 1111 \(185\cdot 6+1\)
4 11111 \(1851\cdot 6+5\)
5 111111 \(18518\cdot 6+3\)

It is clear that \(r_0=r_3=1\text{,}\) therefore \(a_3-a_0=1111-1=1110\) is a multiple of 6 (\(1110=185\cdot 6\)) and this integer is in a right form.

We have a set containing \(n\) elements, let us say these are \(a_1,a_2,\ldots,a_n\text{.}\) We define \(n\) subsets as follows

\begin{equation*} S_k=\halmaz{a_1,\ldots,a_k}, k=1,2,\ldots,n\text{,} \end{equation*}

that is, \(S_1=\halmaz{a_1}, S_2=\halmaz{a_1,a_2},\ldots,S_n=A\text{.}\) Denote by \(s_k\) the sum of the elements of \(S_k\text{.}\) We apply the Division algorithm to write \(s_k=q_k\cdot n+r_k\text{,}\) where \(0\leq r_k\lt n\text{.}\) If for some \(k\) we have \(r_k=0\text{,}\) then

\begin{equation*} s_k=a_1+\ldots+a_k=q_k\cdot n\text{,} \end{equation*}

that is, the sum of the elements of \(S_k\) is a multiple of \(n\text{.}\) In this case the theorem is true. If no such \(k\) exists, then we have only \(n-1\) possible values for \(r_k\) and we have \(n\) subsets. The pigeonhole principle says that there are at least two subsets (say \(S_k\) and \(S_l, k\lt l\)) for which \(r_k=r_l\text{.}\) In this case we obtain that

\begin{equation*} s_l-s_k=(q_l-q_k)n=a_{k+1}+a_{k+2}+\ldots+a_l\text{.} \end{equation*}

Thus the sum of the elements of the subset \(\halmaz{a_{k+1},a_{k+2},\ldots,a_l}\) is a multiple of \(n\text{.}\)

Prove that among 367 people, at least two were born on the same day of the year.

Prove that among 1500 people, at least four were born on the same day of the year.

Prove that if seven distinct integers are selected from the set

\begin{equation*} \halmaz{1,2,3,4,5,6,7,8,9,10,11,12}\text{,} \end{equation*}

then two of these integers sum to 13.

We choose 11 integers from the set \(\halmaz{1,2,\ldots,20}\text{.}\) Prove that 2 of the chosen integers are consecutive.

Prove that if five points are selected from the interior of a unit square, then there are two points whose distance is less than \(\sqrt{2}/2\text{.}\)

Let \(A=\halmaz{1,2,\ldots,100}\text{.}\) Prove that if we choose 51 distinct integers from \(A\text{,}\) then there are at least two integers such that one of them is divisible by the other.

How many students in a class must there be to ensure that 4 students get the same grade (one of 1, 2, 3, 4, or 5)?

How many bishops can one place on an \(8\times 8\) chessboard such that no two bishops can hit each other?