|
Study Guide
Tucker: Applied Combinatorics
§App.4 - The Pigeonhole Principle
Dr. Lee Eimers |
|
|
Introduction:
In this section you become acquainted with one of the most useful principles
for proofs in mathematics. In its simplest form it is very straightforward,
but its application can involve great subtilty.
Concepts and Vocabulary:
The following boldfaced (or italic) terms
and phrases introduced in this section. (These are just 3 names for the
same thing.)
Dirichlet's Box Principle
Dirichlet drawer principle
Pigeonhole principle
Points of Interest:
1. Study the examples
closely. They will give you some idea of the variety of situations that
the pigeonhole principle applies to.
2. Pay close attention
to the examples studied in class. We will do some rather sophisticated reasoning
to be able to apply this principle.
Homework Assignment:
Go to
Pigeonhole Principle.
Study the examples. Try some examples from the list of 32 at the end of the page.
From Tucker, Appendix A.4: Do these to see how well you understand:
#3, 5, 6, 8, 11
Enrichment problems: Anything
after #8 not already covered in class.
Web Sites Related to Appendix 4
The Pigeon Hole
Principle
Good discussion of the P.H.P. and many good examples.
The Pigeon Hole Principle
A series of web pages with theory and
problems
involving the P.H.P. by Ludmil Katzarkov,
UC Irvine.
The Pigeon Hole Principle
Very good collection of problems
The Pigeon Hole Principle
Has an interesting birthday problem.
The Pigeon Hole Principle
Application problems: some good examples. (Don't peek at
solutions
until you try them.)
Pigeon-hole
principle originator
Picture and brief bio of DIRICHLET-LEJEUNE, Johann Peter Gustav
Thought for the
Day
Wisdom is the principal
thing;
Therefore get wisdom:
And with all thy getting get understanding.
Prov. 4:7