Math 504, Lecture 12, Spring 2015.doc

Math 504, Lecture 12, Spring 2004 Pigeons, integer equations, and congruence A final topic in combinatorics: The Pigeonhole Principle The basic Pigeonhole Principle: If there are n+1 pigeons in n pigeonholes, then at least one hole has at least two pigeons. Proof: The contrapositive is trivial: The sum of n integers no larger than 1 can be no larger then n. Examples: This trivial theorem leads to results that are sometimes astonishing and sometimes even useful. I have heard that the corrected proof of Fermat’s Last Theorem (from 1994 by Andrew Wiles and R. Taylor) depends on the Pigeonhole Principle to close some of the gaps from Wiles’s original proof. If there are 13 students in a class, then at least two were born in the same month. In a group of 367 people, at least two share a birthday. Note that this is not a probabilistic statement. It takes only 23 people to have better than a 50% chance of two people sharing a birthday, but it takes 367 to get certainty by the Pigeonhole Principle. In every set of 6 integers at least two leave the same remainder when divided by 5. Equivalently, at least two have a difference that is a multiple of 5. Equivalently at least two are congruent modulo 5. Why? There are only 5 possible remainders when dividing by 5. If m and n are integers with mn, then there is no injection f:[m]→[n]. Why? Think of the elements of [n] as pigeonholes and the elements of [m] as pigeons. A more general Pigeonhole Principle: If m pigeons roost in n pigeonholes, then at least one pigeonhole has at least ceil(m/n) pigeons, where ceil(x) is the ceiling function. Proof: Again prove the contrapositive. If each of n pigeonholes has fewer then m/n pigeons, then the total number of pigeons is less than n(m/n)=m. So at least one pigeonhole has at least m/n pigeons. The number must also be an integer, so it must be at least the smallest integer greater than or equal to m/n, namely ceil(m/n). Examples In a group of 11 people, there are at least 6 men or 6 women