
Re: Pigeonhole Principle ?
Posted:
Oct 14, 2013 1:57 AM


On Sunday, October 6, 2013 10:55:59 PM UTC4, 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

