Theorem 4.2.1.1. Pigeonhole Principle.
If \(k\) is a positive integer, and \(k+1\) or more objects are placed into \(k\) boxes, then there is at least one box containing two or more objects.
Subsection 4.2.1 The Pigeonhole Principle
The basic idea is really simple. For example, if we have three boxes and want to put away four or more toys, there must be at least one box containing two or more toys. The technique can be used cleverly to prove statements that are not so trivial.
Example 4.2.1.2. Words starting with the same letter.
In any group of \(27\) English words, at least two must start with the same letter, since there are only \(26\) letters in the English alphabet.
Example 4.2.1.3. People with the same number of hairs.
Assume no human has more than \(200000\) hairs on his/her head. Since there are more than \(200000\) people in Greensboro, there are at least two people in Greensboro with exactly the same number of hairs on their head.
Theorem 4.2.1.4.
If \(A\) and \(B\) are nonempty sets with \(\size{B} = k\) and \(\size{A}
\geq k + 1\text{,}\) then there are no injective functions from \(A\) to \(B\text{.}\)
Proof.
We show that any function from \(A\) to \(B\) is not injective. Make a box for each \(b\) in \(B\text{.}\) For each \(a\) in \(A\text{,}\) place \(a\) in box labeled \(b\) if \(f(a) = b\text{.}\) By the Pigeonhole Principle, there is a box with at least two elements in it. Thus there is a \(b\) in \(B\) with at least two different preimages. Thus \(f\) is not injective.
Example 4.2.1.5. Multiples consisting only of zeros and ones.
We find that these integers \(n\text{,}\) there is a positive multiple of \(n\) that has only zeros and ones in its decimal expansion.
\begin{equation*}
\begin{array}{r|r}
n \amp \text{multiple of }n\;\;\\\hline
2 \amp 2\cdot 5 = \phantom{00}10\\
3 \amp 3\cdot 37 = \phantom{0}111\\
4 \amp 4\cdot 25 = \phantom{0}100\\
5 \amp 5\cdot 2 = \phantom{00}10\\
6 \amp 6\cdot 185 = 1110\\
7 \amp 7\cdot 143 = 1001\\
\end{array}
\end{equation*}
Prove that for any integer \(n\text{,}\) there is a positive multiple of \(n\) that has only zeros and ones in its decimal expansion.
Solution.
There are \(n\) congruence classes modulo \(n\text{.}\) Use these as labels on a box. Consider the \(n+1\) integers
\begin{equation*}
1, 11, 111, \dots, \underbrace{111\cdots1}_{n+1\text{ times}}.
\end{equation*}
By the Pigeonhole Principle, there must be a congruence class with at least two of these integers in it. The difference of these two integers is \(0\) modulo \(n\text{,}\) hence divisible by \(n\text{.}\) Additionally, the difference only has \(0\) s and \(1\) s in its decimal expansion.
