Example 14.1. Suppose there are $n$ candidates running for office at a debate and after the debate, the candidates all try to awkwardly elbow-bump (or "collide"). Then there will be at least two people who collided with the same number of people. To see this, we first note that each person can collide with anywhere between 0 and $n-1$ other people, which gives us $n$ possibilities, and so we consider the set $A_i$ of people involved in $i$ collisions, with $0 \leq i \leq n-1$. However, observe that it can't be the case that someone was involved in no collision and someone else collided with everyone, so at least one of $A_0$ or $A_{n-1}$ must be empty. This leaves $n-1$ possibilities for $n$ people, so our result follows.
Example 14.2. Suppose I'm a charlatan and I claim that I have a perfect lossless compression algorithm that I'd like to scam some sweet VC funding for. Recall that all data is really just a binary string. So, what I'm essentially claiming is that for every string $x \in \{0,1\}^*$, I can compress it into some other string $x'$ that's shorter and I can decompress it to recover $x$. Let's consider all the binary strings of length $n$. From our previous discussions, we know there are exactly $2^n$ such binary strings. How many strings of length $\lt n$ are there? There are $2^0 + 2^1 + \cdots 2^{n-1} = 2^n - 1$ such strings. But $2^n-1 \lt 2^n$, so there is at least one string of length $\lt n$ that corresponds to two strings of length $n$ after compression.
We can make the pigeonhole principle even more general.
Theorem 14.3. Let $A_1, A_2, \dots, A_k$ be disjoint sets such that $\left| \bigcup_{i=1}^k A_i \right| = n$. Then there exists a set $A_i$ such that $|A_i| \geq \left\lceil \frac n k \right\rceil$.
Proof. Suppose that $\left| \bigcup_{i=1}^k A_i \right| = n$. Let us assume that $|A_i| \lt \left\lceil \frac n k \right\rceil$ for all $1 \leq i \leq k$. Then we have $$\left| \bigcup_{i=1}^k A_i \right| = \sum_{i=1}^k |A_i| \lt \sum_{i=1}^k \frac n k = k \cdot \frac n k = n.$$ Here, we make use of the fact that if $|a_i| \lt \left\lceil \frac n k \right\rceil$, then $|a_i| \lt \frac n k$. Otherwise, since $|a_i|$ is an integer, we would contradict the definition of the ceiling function. In the end, the above argument shows that we contradict our initial hypothesis that $\left| \bigcup_{i=1}^k A_i \right| = n$. $\tag*{$\Box$}$
Example 14.4. Suppose you have large numbers of three colours of socks in a drawer and you're pulling socks out without looking. How many socks do you need to pull out before you're guaranteed to have a pair of the same colour? The answer is four: if we view each colour as a set, all we need is at least one more sock than there are sets.
Now, suppose you are a crab. Crabs have two claws and eight legs so they obviously need eight socks (this is different from octopuses, who have eight limbs, but it is not immediately clear if these should be considered arms or legs). How many socks do you need to pull out before you're guaranteed eight socks of the same colour? The pigeonhole principle says we need $n$ with $\left\lceil \frac n 3 \right\rceil = 8$, which suggests that $n \gt 21$. Approaching it from another perspective, in the worst case, our crab ends up with 7 socks of each colour, so it has 21 socks in total.
We can, of course, ask the same question of spiders, caterpillars, centipedes, and so on.
Theorem 14.5. Let $a_1, a_2, \dots, a_{n+1}$ be integers where each $a_i \leq 2n$. Then there exist $j \neq k$ such that $a_j \mid a_k$.
Proof. For each $a_i$, we have $a_i = 2^{b_i} \cdot m_i$, where $m_i$ is odd by prime factorization. Since $a_i \leq 2n$ and there are only $n$ odd numbers less than $2n$, there are two numbers $m_j$ and $m_k$ such that $m_j = m_k$. Without loss of generality, assume $b_j \gt b_k$ and therefore, we have $a_k \mid a_j$. $\tag*{$\Box$}$
The following is a result from Ramsey Theory. Ramsey Theory is concerned with combinatorial questions that concern how large certain structures have to be before they are guaranteed to have some property. Ramsey was a British mathematician from the early 20th century who passed away very young, at the age of 26 in 1930.
Example 14.6. Given any group of six people at a party, either three are mutual friends or three are mutual strangers. Consider Alice. Either Alice does or does not know each of the five others, which must mean that she knows at least three of the others or she doesn't know at least three of the others. We'll consider the case where she knows three other people, since the case where she doesn't know three other people is similar. So she knows Bob, Charlie, and Eve. We can consider two possbilities.
All of this can be stated more formally using graphs and cliques and colourings, but the party setting allows us to defer defining all of these things until we actually get to graph theory. But note that this argument hinges on the fact that there are at least five other people connected to Alice in order for us to apply the Pigeonhole principle. If we had fewer (i.e. if we took groups of five or less), we wouldn't be able to guarantee either mutual friend/stranger triplet.
We denote by $R(m,n)$ the Ramsey number, which is the minimum number of guests we need to be at our party such that at least $m$ people all know each other or at least $n$ people don't know each other.
Theorem 14.7. $R(3,3) \leq 6$.
Definition 14.8. A permutation of a set $A$ is an ordered list of the elements of $A$. (It is possible to see this as a bijection from $A \to A$ but this generally won't be convenient for our purposes.)
Example 14.9. Consider a set $A = \{1,2,3\}$. One possible permutation is $(1,2,3)$, another is $(3,1,2)$.
A natural question is how many such permutations must exist. For something of this size, we can easily enumerate all of the possibilities: \begin{matrix} (1,2,3) & (1,3,2) & (2,1,3) & (2,3,1) & (3,1,2) & (3,2,1) \end{matrix} This suggests that we can apply some of the counting rules we've already seen.
Theorem 14.10. If $A$ is a set containing $n$ elements, then the number of permutations of $A$ is $n!$.
Why? Because we have $n$ ways of choosing the first element, then $n-1$ ways of choosing the second element (because an element has been removed from the set), $n-2$ ways of choosing the third, and so forth.
Example 14.11. How many different ways are there to rank the presidents of the United States? There were $45$ presidents (Grover Cleveland is annoyingly considered the 22nd and 24th president), so I have 45 different choices for first place. I then have $44$ options for number 2, $43$ for number three, and so forth, until I'm left left with one choice for last. This gives me a total of $45!$ possibilities, which is an astronomical number. On the other hand, if I only want to rate the top $5$ presidents, I get $45 \cdot 44 \cdot 43 \cdot 42 \cdot 41$ which is less than a billion. We'll talk about these partial permutation after the midterm.