Exercises - The Pigeonhole Principle

Standard Level

1. The Pigeon-Hole Principle: Prove that if $kn+1$ pigeons are placed into $n$ pigeon-holes, then some pigeon-hole must contain at least $k+1$ pigeons.

2. Pick $5$ integers from $1$ to $8$, inclusive. Show the two of them sum to $9$.

3. Show that among $n+1$ arbitrarily chosen integers, there must exist two whose difference is divisible by $n$.

4. Consider the first $2n$ integers, $1, 2, 3, \ldots, 2n$. If more than $n$ of these integers are selected, show that two of the selected integers must be relatively prime.

5. Rearrange the first $n$ integers $1, 2, 3, \ldots, n$, listing them as $a_1, a_2, \ldots a_n$. Prove that if $n$ is odd, then $(a_1 - 1)(a_2 - 2) \cdots (a_n - n)$ must be even, regardless of how the integers were initially rearranged.

6. If each point of the plane is colored red or blue, prove there are two points of the same color at distance one inch from each other.

7. Prove that among any five points selected inside a square with side length 2 units, there always exists a pair of these points that are within $\sqrt{2}$ units of each other.

8. Prove that among any five points selected inside an equilateral triangle with side equal to one inch, there always exists a pair at the distance not greater than one half an inch.

9. Is it possible to cover a chessboard with dominoes that each cover exactly two squares? What if the squares in two diagonally opposite corners are removed? Explain.

◆ ◆ ◆