Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Pigeonhole Principle ?
Replies: 9   Last Post: Oct 14, 2013 2:15 AM

 Messages: [ Previous | Next ]
 Dan Christensen Posts: 8,219 Registered: 7/9/08
Re: Pigeonhole Principle ?
Posted: Oct 14, 2013 1:57 AM

On Sunday, October 6, 2013 10:55:59 PM UTC-4, shaoyi he wrote:
> in discrete mathematics and its applications 6th ,in Pigeonhole Principle, the author give a THEOREM(page 351):
>
> Every sequence of n^2 + 1 distinct real numbers contains a subsequence of length n + 1 that is either strictly increasing or strictly decreasing.
>
>
>
> i donnot know what's the theorem for? because when we sort the n^2 + 1 distinct real numbers, we can get n^2+1 that is either strictly increasing or strictly decreasing. so how to understand this?

The usual way to state this principle is:

If a finite number of objects are put into a smaller number of categories, then there would have to be least 2 of those objects in the same category.

More formally:

If P,H,f and g are such that

1. P is finite
2. f: P --> H
3. g: H --> P is an injection , but not a surjection (i.e. there are more elements in P than in H)

then there exists distinct p1 and p2 in P such that f(p)=f(q).

Example: Suppose we have a finite set P of pigeons, and a set H of holes into which we are to put to the pigeons. Suppose the function f assigns a hole to each pigeon. Suppose there are more pigeons than holes. Then at least two distinct pigeons, p1 and p2 are will be assigned to the same hole, i.e. f(p1)=f(p2).

For my formal development of the Pigeon Hole Principle, see "Dedekind's Pigeons" at my math blog http://www.dcproof.wordpress.com

Dan
Download my DC Proof 2.0 software at http://www.dcproof.com

Date Subject Author
10/6/13 何少仪
10/6/13 quasi
10/7/13 Graham Cooper
10/7/13 Jussi Piitulainen
10/8/13 Graham Cooper
10/8/13 Virgil
10/14/13 Dan Christensen
10/14/13 Dan Christensen
10/14/13 Dan Christensen
10/14/13 Dan Christensen