Skip to content

Pigenhole Principle

February 15, 2021


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 {n} items are put into {m} boxes, with {n > m}, then at least one box must contain more than one item.

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

\displaystyle  1 \le x_{1} < x_{2} < x_{3} < \dots < x_{55} \le 100,

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 {f(y,x)} be the number of collisions when placing {y} into {x}. Claim:

\displaystyle  f(x+d,x) \ge f(x+1,x),

for {x \ge 1} and {d \ge 1} and

\displaystyle  f(x+1,x) \ge f(x,x-1),

for {x \ge 2}.

Note the first is really simple. Consider the first {x+1} pigeons. They are placed into {x} places and the inequality follows. The second is about the same. Consider the first {x} pigeons. There are two cases. They are all placed in {x-1} places. Then we are done. So there must have been some placed into the last place. But if two are there then we are also done. So {x-1} are placed into {x-1}. But where does the last one go? In either case we are done.

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]

9 Comments leave one →
  1. February 15, 2021 1:02 pm

    Could you clarify the definition of f?

  2. February 15, 2021 1:11 pm

    In a related story …

    🙞 Infinite Uses → Finite Means

    • February 15, 2021 3:18 pm

      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.

  3. February 15, 2021 1:26 pm

    and the classic: if you have 10 numbers between 1 and 100, there are two subsets with the same total.

    • February 18, 2021 10:03 pm

      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.

      • miklosi permalink
        February 22, 2021 1:44 pm

        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

  4. February 16, 2021 12:12 am

    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.

  5. 12876182 permalink
    February 16, 2021 2:35 am

    Geometric theorems including Pythagoras Theorem.

Trackbacks

  1. New, Old, Ancient Results | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s