Pigeonhole principle

Author Topic: Pigeonhole principle  (Read 1847 times)

Offline Masuma Parvin

  • Sr. Member
  • ****
  • Posts: 323
    • View Profile
Pigeonhole principle
« on: November 13, 2012, 03:46:20 PM »
In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item. This theorem is exemplified in real-life by truisms like "there must be at least two left gloves or two right gloves in a group of three gloves". It is an example of a counting argument, and despite seeming intuitive it can be used to demonstrate possibly unexpected results; for example, that two people in London have the same number of hairs on their heads.
The pigeonhole principle is a powerful tool used in combinatorial math. But the idea is simple and can be explained by the following peculiar problem.

Imagine that 3 pigeons need to be placed into 2 pigeonholes. Can it be done? The answer is yes, but there is one catch. The catch is that no matter how the pigeons are placed, one of the pigeonholes must contain more than one pigeon.

The logic can be generalized for larger numbers. The pigeonhole principle states that if more than n pigeons are placed into n pigeonholes, some pigeonhole must contain more than one pigeon. While the principle is evident, its implications are astounding. The reason is that the principle proves the existence (or impossibility) of a particular phenomenon.

One Example Of this principle:
Two or more people reading this blog will have the same birthday.

There are 366 possible birthdays (including February 29 in a leap year) and this blog has many more than 367 readers. Therefore two of you must share the same birthday.

Offline msu_math

  • Jr. Member
  • **
  • Posts: 81
    • View Profile
Re: Pigeonhole principle
« Reply #1 on: November 13, 2012, 07:17:07 PM »
Pigeonhole principle is a historically famous principle. Thanks for highlighting such an application here. Lets try to find  some other practical applications. 
« Last Edit: November 14, 2012, 09:26:48 AM by msu_math »
Mohammad Salah Uddin

Lecturer in Mathematics
Department of Natural Sciences

Offline snlatif

  • Faculty
  • Sr. Member
  • *
  • Posts: 267
    • View Profile
Re: Pigeonhole principle
« Reply #2 on: November 14, 2012, 02:48:59 PM »
Interesting..and also very informative post,madam.. :)