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!
  1. (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.
  2. (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.
  3. (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.
  4. (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? Or the first 21 powers of two?
  5. (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.