鸽笼原理简介

1 . The Pigeonhole Principle 09/28/18 1 

2 . The Pigeonhole Principle • In words: – If n pigeons are in fewer than n pigeonholes, n some pigeonhole must contain at least two pigeons What is n? http://www.blog.republicofmath.com/archives/3115 2 09/28/18 

3 . The Pigeonhole Principle • In math: Let f : A → B, where A and B are finite sets and A > B . Then there exist distinct elements a1,a2 ∈A such that f (a1) = f (a2 ). 3 09/28/18 

4 .The Pigeonhole Principle Let f : A → B, where A and B • What is a set? are finite sets and A > B . • a finite set? Then there exist distinct elements • What is |A|? a1,a2 ∈A such that f (a1) = f(a2 ). • What is a function? • the domain of a function? • the codomain of a function? • Why say “distinct”? 4 09/28/18 

5 .Applications of The Pigeonhole Principle • In any group of 8 people, two were born on the same day of the week • What are the “pigeons” and what are the “pigeonholes”? • A = the set of people, B = {Sun, … Sat}, f(a) = the day of the week on which a was born 5 09/28/18 

6 . Applications of The Pigeonhole Principle • Suppose each D D D D D pigeonhole contains D D D D D one bird, and every bird D D D D D moves to an adjacent square (up, down, left D D D D D or right). Show that no D D D D D matter how this is done, some pigeonhole winds up with at least 2 birds. 6 09/28/18 

7 . Applications of The Pigeonhole Principle • Suppose each D D D D D pigeonhole contains D D D D D one bird, and every bird D D D D D moves to an adjacent square (up, down, left D D D D D or right). Show that no D D D D D matter how this is done, some pigeonhole winds up with at least 2 birds. 7 09/28/18 

8 . Applications of The Pigeonhole Principle • Suppose each D D D D D pigeonhole contains D D D D D one bird, and every bird D D D D D moves to an adjacent square (up, down, left D D D D D or right). Show that no D D D D D matter how this is done, A = birds on red squares some pigeonhole winds B = gray squares up with at least 2 birds. f (a) = the square a moves to A =13, B =12 8 09/28/18