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 1.6.1.
The Ramsey number $R(i)$ is the smallest integer $n$ such that when the edges of $K_n$ are colored with two colors, there is a monochromatic complete graph on $i$ vertices, $K_i$, contained within $K_n$. The example shows that $R(3)=6$.
More generally, $R(i,j)$ is the smallest integer $n$ such that when the edges of $K_n$ are colored with two colors, say $C_1$ and $C_2$, either there is a $K_i$ contained within $K_n$ all of whose edges are color $C_1$, or there is a $K_j$ contained within $K_n$ all of whose edges are color $C_2$. Using this notion, $R(k)=R(k,k)$. More generally still, $R(i_1,i_2,\ldots,i_m)$ is the smallest integer $n$ such that when the edges of $K_n$ are colored with $m$ colors, $C_1,…,C_m$, then for some $j$ there is a $K_{i_j}$ contained in $K_n$ all of whose edges are color $C_j$.
Ramsey proved that in all of these cases, there actually is such a number $n$. Generalizations of this problem have led to the subject called Ramsey Theory.
Computing any particular value $R(i,j)$ turns out to be quite difficult; Ramsey numbers are known only for a few small values of $i$ and $j$, and in some other cases the Ramsey number is bounded by known numbers. Typically in these cases someone has exhibited a $K_m$ and a coloring of the edges without the existence of a monochromatic $K_i$ or $K_j$ of the desired color, showing that $R(i,j)>m$; and someone has shown that whenever the edges of $K_n$ have been colored, there is a $K_i$ or $K_j$ of the correct color, showing that $R(i,j)\le n$.
Exercises 1.6
Ex 1.6.1 Assume that the relation "friend'' is symmetric. Show that if $n\ge2$, then in any group of $n$ people there are two with the same number of friends in the group.
Ex 1.6.2 Suppose that 501 distinct integers are selected from $1\ldots1000$. Show that there are distinct selected integers $a$ and $b$ such that $a\divides b$. Show that this is not always true if 500 integers are selected. (hint)
Ex 1.6.3 Each of 15 red balls and 15 green balls is marked with an integer between 1 and 100 inclusive; no integer appears on more than one ball. The value of a pair of balls is the sum of the numbers on the balls. Show there are at least two pairs, consisting of one red and one green ball, with the same value. Show that this is not necessarily true if there are 13 balls of each color.
Ex 1.6.4 Suppose we have 14 red balls and 14 green balls as in the previous exercise. Show that at least two pairs, consisting of one red and one green ball, have the same value. What about 13 red balls and 14 green balls?
Ex 1.6.5 Suppose $(a_1,a_2,\ldots,a_{52})$ are integers, not necessarily distinct. Show that there are two, $a_i$ and $a_j$ with $i\ne j$, such that either $a_i+a_j$ or $a_i-a_j$ is divisible by 100. Show that this is not necessarily true for integers $(a_1,a_2,\ldots,a_{51})$.
Ex 1.6.6 Suppose five points are chosen from a square whose sides are length $s$. (The points may be either in the interior of the square or on the boundary.) Show that two of the points are at most $s\sqrt2/2$ apart. Find five points so that no two are less than $s\sqrt2/2$ apart.
Ex 1.6.7 Show that if the edges of $K_6$ are colored with two colors, there are at least two monochromatic triangles. (Two triangles are different if each contains at least one vertex not in the other. For example, two red triangles that share an edge count as two triangles.) Color the edges of $K_6$ so that there are exactly two monochromatic triangles.
Ex 1.6.8 Suppose the edges of a $K_5$ are colored with two colors, say red and blue, so that there are no monochromatic triangles. Show that the red edges form a cycle, and the blue edges form a cycle, each with five edges. (A cycle is a sequence of edges $\{v_1,v_2\},\{v_2,v_3\},\ldots,\{v_k,v_1\}$, where all of the $v_i$ are distinct. Note that this is true in figure 1.6.1.)
Ex 1.6.9 Show that $8< R(3,4)\le 10$.
Ex 1.6.10 Show that $R(3,4)=9$.