Thread: 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?

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 .

hm, i still don't entirely see how this relates the two. But thank you for the reply!