Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.
Get a random Fun Fact!
or
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  The Math Fun Facts App!
 
  List All : List Recent : List Popular
  About Math Fun Facts / How to Use
  Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su
All rights reserved.

From the Fun Fact files, here is a Fun Fact at the Easy level:

Pigeonhole Principle

Here's a challenging problem with a surprisingly easy answer: can you show that for any 5 points placed on a sphere, some hemisphere must contain 4 of the points?

How about an easier question: can you show that if you place 5 points in a square of sidelength 1, some pair of them must be within distance 3/4 of each other?

If you play with this problem for a while, you'll realize quickly that the extreme case occurs when 4 points are at the corners of the square with a 5th point at the center. In this case adjacent points are exactly distance Sqrt[2]/2 ~ 0.707 apart. But what may be harder to show is that this is really the extreme case; why can't any other configuration be more extreme?

The pigeonhole principle is one of the simplest but most useful ideas in mathematics, and can rescue us here. A basic version says that if (N+1) pigeons occupy N holes, then some hole must have at least 2 pigeons. Thus if 5 pigeons occupy 4 holes, then there must be some hole with at least 2 pigeons. It is easy to see why: otherwise, each hole as at most 1 pigeon and the total number of pigeons couldn't be more than 4. (This proof shows that it does not even matter if the holes overlap so that a single pigeon occupies 2 holes.)

So, if I divide up the square into 4 smaller squares by cutting through center, then by the pigeonhole principle, for any configuration of 5 points, one of these smaller squares must contain two points. But the diameter of the smaller square is Sqrt[2]/2, so these two points must be closer than 3/4, as claimed. The pigeonhole principle made what seemed like a slippery argument airtight.

The Math Behind the Fact:
The pigeonhole principle has many generalizations. For instance:

If you have N pigeons in K holes, and (N/K) is not an integer, then then some hole must have strictly more than (N/K) pigeons. So 16 pigeons occupying 5 holes means some hole has at least 4 pigeons.

If you have infinitely many pigeons in finitely many holes, then some hole must have infinitely many pigeons!

If you have an uncountable number of pigeons in a countable number of holes, then some hole has an uncountable number of pigeons!

Did you think about the challenge problem? Here is the answer: for any configuration of 5 points on a sphere, any two of them determine a great circle on the sphere (a circle whose center is the center of the sphere), and that great circle divides the sphere into 2 hemispheres. Considering the remaining 3 points, the pigeonhole principle says that one of the hemispheres must contain at least 2 of those 3 points. Together with the 2 points on the great circle, that hemisphere contains at least 4 points.

How to Cite this Page:
Su, Francis E., et al. "Pigeonhole Principle." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

References:
    The sphere problem comes from a recent Putnam examination.

Keywords:    combinatorics
Subjects:    combinatorics
Level:    Easy
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
4.43
 
current
rating
Click to rate this Fun Fact...
    *   Awesome! I totally dig it!
    *   Fun enough to tell a friend!
    *   Mildly interesting
    *   Not really noteworthy
and see the most popular Facts!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!