Pigeonhole Principle
The pigeonhole principle (PHP) states that if $n+1$ pigeons occupy $n$ pigeon holes, then at least one pigeonhole has more than one pigeon. This seemingly obvious statement is a type of counting argument that can be used to demonstrate unexpected results. Do you see how you can prove this principle? Hint: Think proof by contraction!
- (Candy Jar) At a party, 8 kids each took a piece of candy from a candy jar that contains 7 different types of candy. Show that at least 2 of the kids got candy of the same kind.
- Pigeons correspond to the kids
- Pigeonholes correspond to candy types
- There are 8 pigeons and 7 pigeonholes. By PHP there are at least 2 kids with candies of same type.
- (Birthdays) There 375 students in a class and we are planning to celebrate their birthdays. Show that two of the students have birthdays on the same day.
- Pigeons correspond to the students
- Pigeonholes correspond to birthdays (Jan 1, $\ldots$, Jan 31, Feb 1, $\ldots$, Feb 29, $\ldots$, Dec 31)
- There are 375 pigeons and 366 pigeonholes. By PHP there are at least 2 students with same birthday.
- (Friends Circle) There are 15 students are in a class - some (not all) are friends with each other. Show that at least two of the students have the same number of friends in the class.
- Pigeons correspond to the students
- Pigeonholes correspond to the number of friends (0, 1, 2, 3, $\ldots$, 14)
- Pigeonholes 0 and 14 cannot be simultanously non-empty!
- There are 15 pigeons and 14 pigeonholes. By PHP there are at least 2 students with same number of friends.
- (Powers of 2) Consider the first 101 powers of two $(2^1, 2^2, \ldots, 2^{101})$. Show that there is a pair of numbers whose difference is divisible by 100.
- How does a number divisible by 100 look like? What are the possible last two digits?
- If the difference of $x$ and $y$ is divisible by 100, then what the possibilities for the last two digits of $x$ and $y$?
- Is the claim true among the first 51 powers of two?
- What about the first 41 powers of two?
- (Kings on a Chessboard) Two kings on a chessboard that are in squares that touch each other (either the squares share an edge or a corner) attack each other. What is the maximum number of kings that can be placed on a $8 \times 8$ chessboard so that no pair of them attack each other.
- How about in a $9 \times 9$ chessboard?
- How about in a $m \times n$ chessboard? Here, $m$ and $n$ can be any two natural numbers.