The Pigeonhole Principle is a very natural idea. It says: If a collection of at least \(n+1\) objects is put into \(n\) boxes, then there is a box with at least two things in it. The Pigeonhole Principle has surprisingly deep applications. We will start with a few examples.
Back in Problem 2.11, we implicitly used the Pigeonhole Principle when we argued that if \(f:A\to B\) is a function for finite sets \(A\) and \(B\text{,}\) then
If \(f\) is an injection, then \(|A|\leq |B|\text{.}\)
A box has blue, green, yellow, red, orange, and white balls. How many must be drawn without looking to be sure of getting at least two of the same color?
We would like to generalize the Pigeonhole Principle, but first we need a useful function. The ceiling function of a real number \(x\text{,}\) written \({\lceil x \rceil}\text{,}\) is the smallest integer greater than or equal to \(x\text{.}\) That is, \(\lceil x \rceil\) is an integer, \(\lceil x \rceil \geq x\text{,}\) and there is no other integer between \(\lceil x \rceil\) and \(x\text{.}\) You can think of it as the “round-up to an integer” function.
Suppose \(n\in\mathbb{N}\) and let \(S=\{1,2,\ldots,2n\}\text{.}\) Argue that if we choose \(n+1\) distinct elements from the set \(S\text{,}\) then among those elements there must exist a pair of numbers such that one is a multiple of the other. Hint: Every number in \(S\) is of the form \(2^km\text{,}\) where \(k\) is a nonnegative integer and \(m\) is odd.
Explain why every collection of ten distinct integers \(x_1, x_2, \dots,
x_{10}\) must have at least one subset whose sum of the elements in the subset is divisible by 10.
