Theorem 4.2.2.1. Extended Pigeonhole Principle.
Suppose \(n\) and \(k\) are positive integers. If \(n\) objects are placed into \(k\) boxes, then there is at least one box containing \(\ceiling{\frac{n}{k}}\) objects.
Subsection 4.2.2 The Extended Pigeonhole Principle
Example 4.2.2.2. People born in the same month.
In a group of \(100\) people, there are at least \(\ceiling{\frac{100}{12}} = 9\) born in the same month.
Example 4.2.2.3. Bowl of fruit.
Suppose a bowl contains apples, oranges, and bananas. How many random selections are required to ensure we have at least two of the same fruit?
Solution.
Label boxes by fruit types. Place fruit in the box identifying its type. Then there are \(3\) boxes, so if we select \(3 + 1 = 4\) fruit, the Pigeonhole Principle says we will have at least two of the same type.
If we wanted at least five of the same type, the Extended Pigeonhole Principle says we need \(\ceiling{\frac{n}{3}} \geq 5\text{.}\) That means we need \(\frac{n}{3} \gt 4\text{,}\) so \(n \gt 12\text{.}\) Thus if we select \(13\) fruit, we are guaranteed at least five of the same type.
Example 4.2.2.4. Natural numbers adding up to seven.
How many distinct random selections from \(\{1, 2, 3, 4, 5, 6\}\) are required to guarantee at least one pair that adds up to \(7\text{?}\)
Solution.
Note that \(1 + 6 = 2 + 5 = 3 + 4 = 7\) are the only ways to get a pair to add to \(7\text{.}\) Label 3 boxes: \(\{1,6\}\text{,}\) \(\{2,5\}\text{,}\) and \(\{3,4\}\text{.}\) By the Pigeonhole Principle, if we select \(3 + 1 = 4\) numbers, one box must contain two or more elements. Thus we will have a pair that sums to \(7\) if we select \(4\) numbers.
Example 4.2.2.5. Dealing cards.
Suppose we deal cards from a standard deck of cards (jokers removed). How many cards must be dealt to guarantee that at least \(3\) of the same suit are chosen?
Solution.
Imagine \(4\) boxes, labeled by the \(4\) suits: hearts (\(\heartsuit\)), diamonds (\(\diamondsuit\)), clubs (\(\clubsuit\)), spades (\(\spadesuit\)). By the Extended Pigeonhole Principle, if we deal \(n\) cards, we are guaranteed at least one suit has \(\ceiling{\frac{n}{4}}\) cards in it. We want \(\frac{n}{4} \gt 2\text{,}\) so we need \(n \gt 2 \cdot 4 = 8\text{.}\) Thus \(9\) cards will guarantee \(3\) of the same suit.
