A key step in many proofs consists of showing that two possibly different values are in fact the same. The Pigeonhole principle can sometimes help with this.

Theorem 1.6.1 (Pigeonhole Principle) Suppose that $n+1$ (or more) objects are put into $n$ boxes. Then some box contains at least two objects.

Proof. Suppose each box contains at most one object. Then the total number of objects is at most $1+1+\cdots+1=n$, a contradiction. $\qed$

This seemingly simple fact can be used in surprising ways. The key typically is to put objects into boxes according to some rule, so that when two objects end up in the same box it is because they have some desired relationship.

Example 1.6.2 Among any 13 people, at least two share a birth month.

Label 12 boxes with the names of the months. Put each person in the box labeled with his or her birth month. Some box will contain at least two people, who share a birth month. $\square$

Example 1.6.3 Suppose 5 pairs of socks are in a drawer. Picking 6 socks guarantees that at least one pair is chosen.

Label the boxes by "the pairs'' (e.g., the red pair, the blue pair, the argyle pair,…). Put the 6 socks into the boxes according to description. $\square$

Some uses of the principle are not nearly so straightforward.

Example 1.6.4 Suppose $a_1,\ldots,a_n$ are integers. Then some "consecutive sum'' $a_k+a_{k+1}+a_{k+2}+\cdots+a_{k+m}$ is divisible by $n$.

Consider these $n$ sums: $$\eqalign{ s_1&=a_1\cr s_2&=a_1+a_2\cr s_3&=a_1+a_2+a_3\cr &\vdots\cr s_n&=a_1+a_2+\cdots+a_n\cr }$$ These are all consecutive sums, so if one of them is divisible by $n$ we are done. If not, dividing each by $n$ leaves a non-zero remainder, $r_1=s_1\bmod n$, $r_2=s_2\bmod n$, and so on. These remainders have values in $\{1,2,3,\ldots,n-1\}$. Label $n-1$ boxes with these $n-1$ values; put each of the $n$ sums into the box labeled with its remainder mod $n$. Two sums end up in the same box, meaning that $s_i\bmod n=s_j\bmod n$ for some $j>i$; hence $s_j-s_i$ is divisible by $n$, and $s_j-s_i=a_{i+1}+a_{i+2}+\cdots+a_j$, as desired. $\square$

A similar argument provides a proof of the Chinese Remainder Theorem.

Theorem 1.6.5 (Chinese Remainder Theorem) If $m$ and $n$ are relatively prime, and $0\le a< m$ and $0\le b< n$, then there is an integer $x$ such that $x\bmod m=a$ and $x\bmod n=b$.

Proof. Consider the integers $a,a+m,a+2m,\ldots a+(n-1)m$, each with remainder $a$ when divided by $m$. We wish to show that one of these integers has remainder $b$ when divided by $n$, in which case that number satisfies the desired property.

For a contradiction, suppose not. Let the remainders be $r_0=a\bmod n$, $r_1=a+m\bmod n$,…, $r_{n-1}=a+(n-1)m\bmod n$. Label $n-1$ boxes with the numbers $0,1,2,3,\ldots,b-1,b+1,\ldots n-1$. Put each $r_i$ into the box labeled with its value. Two remainders end up in the same box, say $r_i$ and $r_j$, with $j>i$, so $r_i=r_j=r$. This means that $$a+im=q_1n+r\quad\hbox{and}\quad a+jm=q_2n+r.$$ Hence $$\eqalign{ a+jm-(a+im)&=q_2n+r-(q_1n+r)\cr (j-i)m&=(q_2-q_1)n.\cr }$$ Since $n$ is relatively prime to $m$, this means that $n\divides(j-i)$. But since $i$ and $j$ are distinct and in $\{0,1,2,\ldots,n-1\}$, $0< j-i< n$, so $n\nmid(j-i)$. This contradiction finishes the proof. $\qed$

More general versions of the Pigeonhole Principle can be proved by essentially the same method. A natural generalization would be something like this: If $X$ objects are put into $n$ boxes, some box contains at least $m$ objects. For example:

Theorem 1.6.6 Suppose that $r_1,\ldots,r_n$ are positive integers. If $X\ge(\sum_{i=1}^n r_i) -n + 1$ objects are put into $n$ boxes labeled $1,2,3,\ldots,n$, then some box labeled $i$ contains at least $r_i$ objects.

Proof. Suppose not. Then the total number of objects in the boxes is at most $(r_1-1)+(r_2-1)+(r_3-1)+\cdots+(r_n-1)=(\sum_{i=1}^n r_i) -n < X$, a contradiction. $\qed$

This full generalization is only occasionally needed; often this simpler version is sufficient:

Corollary 1.6.7 Suppose $r>0$ and $X\ge n(r-1)+1$ objects are placed into $n$ boxes. Then some box contains at least $r$ objects.

Proof. Apply the previous theorem with $r_i=r$ for all $i$. $\qed$

$$\bullet\quad\bullet\quad\bullet$$

Here is a simple application of the Pigeonhole Principle that leads to many interesting questions.

Example 1.6.8 Suppose 6 people are gathered together; then either 3 of them are mutually acquainted, or 3 of them are mutually unacquainted.

We turn this into a graph theory question: Consider the graph consisting of 6 vertices, each connected to all the others by an edge, called the complete graph on $6$ vertices, and denoted $K_6$; the vertices represent the people. Color an edge red if the people represented by its endpoints are acquainted, and blue if they are not acquainted. Any choice of 3 vertices defines a triangle; we wish to show that either there is a red triangle or a blue triangle.

Consider the five edges incident at a single vertex $v$; by the Pigeonhole Principle (the version in corollary 1.6.7, with $r=3$, $X=2(3-1)+1=5$), at least three of them are the same color, call it color $C$; call the other color $D$. Let the vertices at the other ends of these three edges be $v_1$, $v_2$, $v_3$. If any of the edges between these vertices have color $C$, there is a triangle of color $C$: if the edge connects $v_i$ to $v_j$, the triangle is formed by $v$, $v_i$, and $v_j$. If this is not the case, then the three vertices $v_1$, $v_2$, $v_3$ are joined by edges of color $D$, and form a triangle of color $D$. $\square$

The number 6 in this example is special: with 5 or fewer vertices it is not true that there must be a monochromatic triangle, and with more than 6 vertices it is true. To see that it is not true for 5 vertices, we need only show an example, as in figure MISSING XREFN(fig:5 not ramsey).

\figure