鸽笼原理简介

本文主要介绍了鸽笼原理,原理:如果鸽子多于N个鸽子洞,一些鸽子洞必须至少包含两只鸽子。由鸽笼原理引出函数问题,什么是函数?函数的域是什么?函数的余域是什么等等。本文还探讨了鸽笼原理的应用。通过例题讲解鸽笼原理的应用。
展开查看详情

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