Pigeonhole Principle: Counting, Collisions, and Applications

All flashcards

Basic pigeonhole principle

If more objects than containers are assigned to those containers, at least one container receives two or more objects.

Quantified pigeonhole principle

Among $n$ objects distributed among $m$ containers, some container holds at least $\left\lceil n/m \right\rceil$ objects.

Injective function

A function in which distinct domain elements have distinct images.

Surjective function

A function whose image includes every element of its codomain.

Strong pigeonhole principle

For positive thresholds $q_1,\ldots,q_m$, $\sum_{i=1}^m q_i-m+1$ objects force some box $i$ to contain at least $q_i$ objects.

Quiz questions

1. Seventeen objects are distributed among five containers. What minimum occupancy does the quantified pigeonhole principle guarantee for at least one container?Answer: At least four objects.
2. For positive integer thresholds $q_1,\ldots,q_m$, how many objects are sufficient to force some box $i$ to contain at least $q_i$ objects?Answer: $\sum_{i=1}^m q_i-m+1$ objects.
3. If finite sets $A$ and $B$ satisfy $|A|>|B|$, what must be true of every function from $A$ to $B$?Answer: It is not injective.
4. In a group of more than one person, each person's handshake count records how many other group members they shook hands with. What does the pigeonhole principle imply?Answer: At least two people have the same handshake count.
5. Each of $n$ objects is assigned independently and uniformly to one of $m$ categories, where $n\le m$. What is the probability of at least one collision?Answer: $1-\frac{(m)_n}{m^n}$