The Pigeonhole Principle - Dr. Travers Page of Math

The Pigeonhole Principle

Some Questions

Does there have to be two trees on Earth with the same number of leaves?

Some Questions

Does there have to be two trees on Earth with the same number of leaves? How large of a set of distinct integers between 1 and 200 is needed to assure that two numbers in the set have a common divisor?

Some Questions

Does there have to be two trees on Earth with the same number of leaves? How large of a set of distinct integers between 1 and 200 is needed to assure that two numbers in the set have a common divisor? How large a set of distinct integers between 1 and n to assure that the set contains a subset of five equally spaced integers a1, a2, a3, a4, a5; that is a2 - a1 = a3 - a2 = a4 - a3 = a5 - a4?

Some Questions

Does there have to be two trees on Earth with the same number of leaves? How large of a set of distinct integers between 1 and 200 is needed to assure that two numbers in the set have a common divisor? How large a set of distinct integers between 1 and n to assure that the set contains a subset of five equally spaced integers a1, a2, a3, a4, a5; that is a2 - a1 = a3 - a2 = a4 - a3 = a5 - a4? Given a positive integer k, how large a group of people is needed to ensure that either there exists a subset of k people in the group that know each other or a subset of k people none of whom know each other?

The Pigeonhole Principle

Theorem The Pigeonhole Principle If k + 1 pigeons are placed into k pigeonholes then at least one of the pigeonholes contains two or more pigeons.

The Pigeonhole Principle

Theorem The Pigeonhole Principle If k + 1 pigeons are placed into k pigeonholes then at least one of the pigeonholes contains two or more pigeons.

A more general statement of the theorem: Theorem If m pigeons are to be placed into k pigeonholes, then at least one of the pigeonholes will contain more than

m-1 k

pigeons.

Proof of Generalized Version

Proof. If the largest number of pigeons in a pigeonhole is at most

m-1 k

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download