# Pigeonhole Principle

Printable View

• May 30th 2012, 09:50 AM
BlinkyBoo
Pigeonhole Principle
How is the PHP the same as saying that one of the numbers n1, n2, ... , nk is greater than or equal to their average?
• May 30th 2012, 01:02 PM
MathoMan
Re: Pigeonhole Principle
Basic PHP says that if you have k+1 pigeons and only k pigeonholes than at least one of the pigeonholes will have at least two pigeons in it.

Identify each pigeonhole with a number, starting from 1 to k. Then form a sequence of numbers n_1,n_2,...,n_k like this: n_j is the number of pigeons inside the j-th pigeonhole. Calculate the average for such sequence of numbers: (k+1)/k=1+1/k<=2. Since you have more pigeons than pigeonholes at least one of the numbers n_1, n_2,..., n_k will be greater than or equal to two and hence at least one of the numbers in that sequence will be greater than or equal to the average of that sequence .
• May 30th 2012, 04:16 PM
BlinkyBoo
Re: Pigeonhole Principle
hm, i still don't entirely see how this relates the two. But thank you for the reply!