Simple Pigeonhole principle, but interesting result — Journey in Combinatorics
Use simple principle to derive beautiful results
Pigeonhole principle is one of the most easy yet fundamental theorem in the area of discrete math. Nonetheless, if pigeonhole principle is applied appropriately to some scenarios, some amazing results that seemed pretty difficult to prove can be deduced. In this article, you will learn or refresh the pigeonhole principle with some of the classical application. Then, some nice problems involving pigeonhole principle technique will be discussed. After reading this, you should be able to appreciate this simple yet subtle theorem.
Pigeonhole principle states that if there are n pigeons to be allocated, but only n-1 cages, then there must exists a cage with at least 2 pigeons. The proof is quite straightforward: Assume the opposite, then we have at most 1 pigeon at each cage. Summing over then n-1 cage, we have the number of pigeons ≤ (n-1)*1= n-1. However, we have n pigeons. There must be a contradiction.
Classical Application 1: Any group of 13 people will have two people born in the same month.
Proof: Here, the “pigeonholes” are the months where people were born, and “pigeons” are the 13 people. We only have 12 “pigeonholes”/cages, so there must be 2 pigeons in 1 cage, or 2 people born in the same month.
Classical Application 2: There is a number 8, 88, 888, 8888, 88888, …. that is divisible by 2021.
Proof: In fact, there must be such a number in the first 2021 that is divisible by 2021. Suppose not, then, every number will have a reminder after divided by 2021, and the reminders can only range from 1….2020. Since there are 2022 numbers, there must be some n_i, n_j that has the same reminders (after being divided by 2021). Then, you can check (without loss of generality, assume n_i > n_j), n_i-n_j is divisible by 2021. However, our numbers take certain form, and you will see that n_i-n_j=n_{i-j}*10^(j). Notice that 10 is relatively prime to 2021, and n_i-n_j must be divisible by 2021, then we now know that n_{i-j} must be divisible by 2021.
Classical Application 3 (Generalized Pigeonhole principle): Let n, a, b be numbers such that n > a*b. Suppose there are n pigeons, and there are a slots. Then, there must exist a slot with more than b pigeons.
Proof: I deliberately ignore it, try to prove yourself！
Now, aside those mathematical results, there are some surprising results proved using pigeonhole principle.
Amazing Result 1: For any random 100 numbers you choose, there is a way to choose 15 of them such that any of two’s difference is divisible by 7.
Proof: Assume the opposite. If any of the 15 numbers cannot all be divisible by 7, it means 2 of the 15 numbers have different modulo 7 (the reminder of a divided by 7 is not the reminder of b divided by b). Now, using general pigeonhole principle, we know there exists more than 14 numbers having the same modulo 7 (reminder divided by 7). (Why? think of the 100 numbers pigeons, and there are 7 slots (modulo 7), then use general pigeonhole principle).
Amazing Result 2: For any party with more than 2 people, and every person know at least one other person at the party(excluding him/herself), then there are two people who know same amount of people.
Proof: Let n be number of people at the party. Since each person cannot known him/herself, so the maximum number of people a person can know is n-1, also the minimum number of people a person can know is 1, that leaves the fact that each person can know 1 to n-1 people, a n-1 choices, or pigeonholes. Now, we have n people, or n pigeons, so by pigeonhole principle, there must exists 2 people that knows the same number of people at the party.
Amazing Result 3: You have an ancestor A such that there was a person P that is both A’s mother’s and father’s ancestor.
Proof: Consider yourself as a root of tree. One level above you are your father and mother, (2 nodes). Another level above your parents are your 2 grandmother and 2 grandfather (4 nodes). Continue down this process, we have 1+2+4+8+…2^n nodes for nth ancestor level above you. Now, assume that every generation is produced at the rate of 25 years old(it is an estimate, for rigid analysis, refer to anthropologist’s work), then in past 1000 years, we have 40 generations grown. Thus, the total number of nodes in the tree is 1+2+…+2⁴⁰ = 2⁴¹-1. Then, 2⁴¹-1 is about 18 times larger than the estimated 117 billion cumulative population on earth for entire history. Now, if there does not exists an A as described, then any nodes in the tree represents different people, otherwise, there will such an ancestor A for you (Why?). If that’s true, we would have 2⁴¹-1 people lived on earth which is far far larger than estimated 117 billion. Using pigeonhole principle, we derive to an contradiction. Result is proved.
Of course, there are tons of other applications of pigeonhole principle other than the few mentioned above, for instance, you can actually prove the Chinese Reminder Theorem by pigeonhole principle, you can prove art gallery problem pigeonhole principle ect. Simple pigeonhole principle sometimes lead to nontrivial results, so next time if you are stuck at some discrete math problem, try to apply pigeonhole principle. It may give you some surprise!
