Pigenhole Principle
Mathematics is based on the application of simple ideas over and over: From tiny nuts do big trees grow.
Jorgen Veisdal is an assistant professor at the Norwegian University of Science and Technology. He is also the editor in chief at Cantor’s Paradise, which is a publication of math and science essays.
Today I thought we would discuss a post of his on the famous Pigenhole Princeiple (PP).
Recall the PP states that if 
The paradox in my opinion is that this idea has any power at all. I wonder if I could explain why it was stated as an explicit principle by the famous Peter Dirichlet under the name Schubfachprinzip (“drawer principle” or “shelf principle”) in 1834.
Parts of mathematics not only use PP, but could not live without it. Other parts of mathematics—I believe—are almost untouched by it. Am I right about this? Number theory and combinatorics especially Ramsey theory could not survive without it. What happens in your favorite area? Is there some area of math that is almost untouched by PP?
|
An Example of PP
The main issue is why is PP so indispensable to some areas of math. But I though it might be fun to give a sample type of proof that uses PP.
Prove that however one selects 55 integers
there will be some two that differ by 9, some two that differ by 10, a pair that differ by 12, and a pair that differ by 13. Surprisingly, there need not be a pair of numbers that differ by 11.
Proof
Let 
for 
for 
Note the first is really simple. Consider the first 
Open Problems
Are there areas that almost never use the PP? I would like to hear about areas that just do not use PP.
[some word fixes]
Could you clarify the definition of f?
In a related story …
🙞 Infinite Uses → Finite Means
In other words, if you have only a finite number of resources to handle an infinite number of instances then some resources will have to be infinitely resourceful.
and the classic: if you have 10 numbers between 1 and 100, there are two subsets with the same total.
Isn’t this a counter-example?
Take the set of 10 integers 1 to 10. If the theorem is true, then you could divide them into two subsets each of which sums to n. So 2n=55, so n cannot be an integer.
The two subsets are not necessarily cover the ground set. Thus, your example contains lots of solutions, for example 1+4 = 2+3, so the subsets {1,4} and {2,3} have the same total
In information theory, the pigeonhole principle can be used to refute the proposition there is such a thing as a universal, recursive, lossless data compression algorithm. To be lossless each unique input must map to a unique output code, e.g. pigeonhole. Recursive application to compressed data cannot losslessly reduce the required minimum number of pigeonholes. The proof is so simple you can recite it while standing on one leg. This does not prevent a new charlatan from coming along every month or two with a claim on the Web of discovering such an algorithm.
Geometric theorems including Pythagoras Theorem.