Pigeon Hole

[gene]

Pigeon Hole Theory. Is it still relevant? How can we apply it to our daily lives and mathematics? What exactly is it about? Is it applicable only for numbers?

[matt grime]

You mean the pigeon hole principal? As in assigning n letters to n-1 letter boxes means someone gets two letters at least? Yes, it is a very important lemma in mathematics that crops up all over the place. I doubt that it is of little practical value to the "real world" directly in the sense you appear to be geting at.

[gene]

You mean the pigeon hole principal? As in assigning n letters to n-1 letter boxes means someone gets two letters at least? Yes, it is a very important lemma in mathematics that crops up all over the place. I doubt that it is of little practical value to the "real world" directly in the sense you appear to be geting at.

 

Ya. I only got a brush with the principal, it wasn't really very in-depth as i read on the net about it. But, i can;t seem to apply it to mathematics that i'm studying as i'm unsure when to use it.

[matt grime]

How about this example:

 

suppose S is a finite set and f a function from S to itself. If f is injective then f is surjective.

 

Or one I saw recently: Suppose that you have six numbers, none of them divisible by 6. Show that at least two of them have difference that is divisible by 6.

 

Or, given any six people, there wll either be 3 people who all know each other, or 3 who are all mutual strangers (assuming that if x knows y, then y knows x).

 

The principal is just something that is useful in proving many theorems, especially those in combinatorics.

[123rock]

I don't if this is along the lines, but:

 

The sum of consecutive integers is S(n)=1/2n^2+1/2n where n is the integer.

Now for the integer of n-1, we get the equation 1/2n^2-1/2n.

 

If S(n)=1/2n^2+1/2n, then to get S(n-1) we replace n with n-1, which is obviously a contradiction, but the formula works. Can anyone elaborate why or how this happens, and what I'm interpreting wrong?

[matt grime]

What has this to do with the pigeon hole principal, and what contradiction are you talking about? That in order to evaluate the sum of the first n-1 integers you put n-1 in the formula? That's what the formula is, how on earth can that be a contradiction?

[123rock]

I meant if S(n)=1/2n^2+1/2n then S(n-1)=1/2(n-1)^2+1/2(n-1); We replace n with n-1, but then why do we replace n with n-1 and call it equal?

[MandrakeRoot]

I meant if S(n)=1/2n^2+1/2n then S(n-1)=1/2(n-1)^2+1/2(n-1); We replace n with n-1, but then why do we replace n with n-1 and call it equal?

 

I think you are confusing two things here, the definition of a mapping and evaluation of a mapping at some element. S is a mapping from the set of integers into the set of integers and has the following descriptive formula :

[math]m \mapsto \frac{1}{2}m(m+1)[/math]

Now you can evaluate the mapping S at any integer n or n-1 or whatever and get an expression for their values.

 

Mandrake

[matt grime]

Why should S(n-1) equal S(n)? one is the sum of the first n integers, the other the sum of the first n-1 integers. S(n-1)+n=S(n), fortunately

[gene]

matt, is it quite to understand this principal? cause i don't see the link in post 4.

about the 3 knowing each other and 3 strangers, can seem to understand.

 

what can simply understand about pigeon holes is that there are 7 birds and 6 pigeon holes, definitely there is 1 pigeon hole that will ahve 2 birds. the probability would then be 1/7.

[matt grime]

the probability of what is 1/7?

 

here's how to use the pigeon hole principle in the example of people and friends.

 

pick one person. of the other five he must either know or not know at least 3 of them by the pigeon hole principle.

 

assume he knows three of them, if any of two those three know each other then we have three common friends, if not then all three of them must be mutual strangers and we are done. (the other option is completely analogous.)

[gene]

probability that one hole has 2 birds.

[gene]

Is there a definition for this theory?

[Dogtanian]

probability that one hole has 2 birds.

The probability that one hole has 2 pigeons is 1.

Surely it's the probablity of a particular hole has 2 that is 1/7, which is nothing directly related to the Pigeon Hole Principle.

 

If by definition you mean a more formal statement of the Principle then it would be hard to find anything better than what has already been said. It basically goes as follows:

 

If we put N+1 pigeons in N pigeon-holes, then some pigeon-hole contains at least two pigeons.

 

The statment doesn't say anthing about needing to put at least one pigeon in each hole, but just that if you have more pigeons than holes and randomly place all the pigeons in a hole, then there will be at least one hole with at least 2 pigeons.

[gene]

ok. thanks. Simply done.

 

My trouble now is exploiting this principle.