The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Dan Christensen

Posts: 6,540
Registered: 7/9/08
Re: Pigeonhole Principle ?
Posted: Oct 14, 2013 1:57 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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

Download my DC Proof 2.0 software at

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.