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!!

## Wednesday, August 17, 2011

## Wednesday, August 10, 2011

### 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

If

If

By pigeonhole principle,there is at least one pigeonhole will hold more than one pigeons with probability where (

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

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 "

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- at least one of the drawers must contain no fewer than objects;where refers to ceiling function on
*x*:smallest integer*>=x*. - at least one of the drawers must contain not more than objects;where refers to floor function on
*x*:largest integer*<=x*.

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.
Location:
Bangalore,India

Subscribe to:
Posts (Atom)