Pierre de Fermat : Happy Birthday!!

Pierre de Fermat celebrates his 410th birthday today.The versatile Frenchman gave a very popular theorem,
"Fermat's Last Theorem".He famously wrote "I have a truly marvelous demonstration of this proposition which this margin is too small to contain.",on the margin of his copy of Bachet's translation of the greek Diophantus' "Arithmetica".

The theorem states that:
 xⁿ + yⁿ = zⁿ has no non-zero integral solutions for x,y and z when n>2.


This apparently simple theorem took about 300 years to prove!


He also gave "Fermat's Little Theorem".There are Fermat Numbers too!!

The Pigeonhole Principle layman's way

In very simple terms,suppose there are n pigeons living in m holes,such that n>m,then at least one of the holes must have more than one pigeons.

Let us take an example with numbers.If we have 11 pigeons and only 10 holes,we start by putting one pigeon in each hole.When 10 holes are full,there is one pigeon left.What do we do?We simply put the remaining pigeon in any of the ten holes.Thus, one of the holes will have 2 pigeons.

Increase the number of pigeons in the above example and we get the concept of 'at least'.

This apparently simple idea is very useful in mathematics and computer science.The first formal presentation of this concept was done by Johann Peter Gustav Lejeune Dirichlet of  in 1834,thus the name 'Dirichlet's Box Principle' or 'Dirichlet's Drawer Principle'.He was a German mathematician of great fame during his time.

Professor Edsger W. Dijkstra has done a very lucid commentary on the principle Dijkstra University of Texas

Generalizations


If n discrete objects are assigned to m drawers,then

1. at least one of the drawers must contain no fewer than   objects;where   refers to ceiling function on x:smallest integer >=x.
2. at least one of the drawers must contain not more than   objects;where   refers to floor function on x:largest integer<=x.

In terms of probability,the Pigeonhole principle can be understood as follows:
If n pigeons are put in m pigeonholes randomly,each pigeonhole has the uniform probability of 1/m of containing a pigeon.
By pigeonhole principle,there is at least one pigeonhole will hold more than one pigeons with probability where  (m)_{n is m(m-1)(m-2)....(m-n+1).}


Tequila shots and Mathematics

If we have 5 tequila shots and only 3 drinkers,we can safely say that at least one of them had more than one shots.But we can only predict the probability of a drinker having more than one shots.
Number of pigeons n=5
Number of holes m=3
After distributing 3 shots,we have 2 more to go.
P(man A having extra shot) P(A)=1/5
Note that the remaining shot is free from preconditions.In other words,there is no conditional probability.
Thus,
Probability that at least one of the men,say A,will drink more than one shots = 1-P(no second shot for A)
One shot can be distributed in 3 ways.For each of these ways,
1st shot=3 ways
2nd shot=2 ways
3rd shot=1 ways
4th and 5th shot=0 ways
Therefore,
P(no second shot for A)=3x2x1x0x0=0
P(A drinks >one shots)=1-0=1

This is the simple,childish representation.Now let us see a formal expression using generalization formula seen above.

Probability that at least one of the holes will have at least more than one pigeon = 


=1-[(3x2x1x0x-1)/(3x3x3x3x3) =1


Applications


This principle finds application in both finite sets ,like drawers,pigeons,etc.,as well as in infinite sets which cannot be called one-one correspondence;in which case we use the formal phrase "there does not exist an injective function on finite sets  whose codomain is smaller than its domain".


Siegel's lemma is another useful derivation based on Dirichlet's principle.It is valid only for a system of linear equations.