Imagine that you are a pigeon owner, and let’s say that you have 10 pigeons. however, there is a problem – you have 9 pigenholes. How can you fit all the pigeons to different pigenholes? That’s right – you cant!

You don’t have to be a mathematician in order to understand the situation. It is so simple! At first sight, it seems like this has nothing to with math, that’s just simple logic. Even if it related to math somehow, it doesn’t really look like there’s much to do with it, at least that’s what I’ve thought when I first saw it…

The problem I have descirbed in the begining is called the **Pigeonhole principle**, and it goes like this (quote from wikipidea):

In our example, , the items are **pigeons** and the containers are the **pigeonholes**.

##### Proofs

First things first, I need to prove this stamement, luckily the proof is one of the shortest proofs in math:

We have items and such that . put each item at a time in a different container, after items all the containers are full and you still have items which are not in the container.

That’s a **really** detailed proof, Let me show you another one:

Suppose that you can fit items to containers. Put in each container one items at most. We got that in the maximal case, items are in a container, but and we have a contradiction.

Those proofs are very similar and they show you how simple the prinicple is, which is going to be a huge suprise seeing it in action.

##### Formal definition

There is a formal definition for this principle, in the language of **set theory**. We can denote the set of object by and the set of containers by . What we’re trying to do formally is to map each element of to an element of in such a way that if , then they can’t be sent to the same element in . If such a map satisfies this property, we call it a **one-to-one** map.

So as a pigeon owner, I want to find a one-to-one** **map from the set of piegons to the set of piegonholes .

The map goes from to . I am going to give it a special symbol: .

Now, how we can transalte the pigeonhole principle into formal math? what this principle basically says is that if ( |A| is the number of element in the set , same goes for ), then there **isn’t** one to one map, i.e. there are such that :

|A|>|B|\Rightarrow f:A\to B\text{ can't be one-to one}

This is equivalent to the statement:

f:A\to B\text{ is one-to-one} \Rightarrow|A|\leq|B|

Alright then, now that we are familiar with the principle, let’s see some examples that will demonstrate us how powerful this theorem can be:

## Trees and leaves

How many leaves can a tree have? let’s exaggerate and say that a tree has **million** leaves at most.

How many trees out there? I just checked, and there are around **400 billion trees**.

We can now use the pigeonhole principal to conclude that there must be at least two trees with the same number of leaves.

Why? out ‘object’ are going to be the trees – there are **400 billion** of them. On the other hand, we want to match each tree to it’s number of leaves, however, we know that there are ‘only’ a **million** options and clearly, 400 billion is greater than 1 million.

## Triangle and dots

Suppose that you have an equilateral triangle where each edge is 2 inches long. Now draw 5 arbitrary points **inside **the triangle

I state that there must be **at least one** pair of points, such their distance is less than one inch. How can I prove such a thing? There is a nice trick here, I am going to divide the triangle into 4 smaller equilateral triangles:

Each one of the small triangles is also an equilateral triangle, but with length one – you can easily see (and prove) that if two dots are inside the same triangle, then their distance must be smaller than 1. However, there are 5 dots, and only 4 small triangles, therefore, we can use the pigeonhole principle to conclude that there are such two dots.

## Erdős–Szekeres theorem

This one is a little more complicated than the previous two, though it is not really complicated.

We are going to deal now with finite sequnces of real numbers, some examples:

1,2,3,4,5,6

-4,8,5.1,4,3,5,5,5

\pi,3,e,\frac{1}{2},0.22223

Our goal is to find an **increasing** **sub-sequnce** of the original sequence, or a **decreasing** **sub-sequnce** of a specific length. For example, an increasing sub-sequence in the second sequence in the above, of length 3 can be:

-4,3,5

However, in the first sequence, you can’t find a decreasing sub-sequence at all. Erdős–Szekeres theorem gives us a criteria for specific cases:

Let be some integers. Then for **every** sequence of **real** and **differenet** numbers, there is an increasing sequence of length or a decreasing sub-sequence with length .

For example, if this theorem states that every sequnce with 5 different numbers, has an increasing / decreasing sub-sequence of length 3.

Notice that is the ‘best’ possible number: For every , there is a sequence of length without an increasing subsequence of length and without decreasing sequence of length as well:

\overbrace{m,m-1,\dots,2,1,}\ \ \overbrace{2m,2m-1,\dots,m+2,m+1}\ \ \dots\ \ \overbrace{nm,nm-1,\dots,(n-1)m+1,}

The sequence is made of decreading sequences of length .

#### The Proof

Suppose that is a sequence of different real numbers without increasing subsequence of length and without decreasing sequence of length .

I am going to prove that . Wait, how it that helpful? First, I want to give a name for such sequences as the above. I am going to name them **‘bad sequences’**.

What I am doing in the proof is taking a ‘bad sequence’, and proving that it’s length must be smaller than . If I manage to prove it, then I showed that there aren’t such ‘bad sequences’ of length , Which is exactly what I wanted.

Ok, so let’s prove it. I am going to define for every two things:

- = the length of the longest
**increasing**sequence that starts at - = the length of the longest
**decreasing**sequence that starts at

For example, consider the following sequence:

(1,4,-1,2,3)

Then we get:

\begin{array}{cccccc} & \boldsymbol{1} & \boldsymbol{4} & \boldsymbol{-1} & \boldsymbol{2} & \boldsymbol{3}\\ \boldsymbol{a_{i}} & 3 & 1 & 3 & 2 & 1\\ \boldsymbol{b_{i}} & 2 & 2 & 1 & 1 & 1 \end{array}

Try it yourself, make sure you understand it.

Now I am going to look on **pairs** . By our assumption, there is no increasing subsequence of length , we can conclude that for every . Moreover, by similar argument, we can conclude that .

Let’s define a map: by:

f(i)=(a_i,b_i)

Notice that and . If we will prove that is one-to-one, we can conclude by the pidgeonhole principal that:

k=|\{1,\dots,k\}|\leq |\{1,\dots,m\}\times \{1,\dots,n\}|=m\cdot n

And that’s exactly what we wanted! Ok, let’s try to prove it: We want to show that if then . We can assume WLOG that . Now, there are two cases:

- : this means that for every
**increasing**sub-sequence that starts in , we can add to it to get a longer sub-sequence. Thus, , an in particular, . - : this means that for every
**decreasing**sub-sequence that starts in , we can add to it to get a longer sub-sequence. Thus, , an in particular, .

In both cases we have as desired, and we’re done!

This proof gives us a little clue on how powerful the pigeonhole principle can be, I think it’s amazing.

## Approximating with the rationals

If you studied calculus before, you are probably already familiar with the special property of the rational numbers – they are **dense** in . In other words: for every real number, we can always find a rational number as close to it as we want.

Formally: for every , and for every . There exitsts such that:

|\alpha-\frac{m}{n}|<\varepsilon

This is equivalent to . However, can we find a better approximation? As it turns out, you can!

I state that for any we can find such that:

|n\alpha-m|<\varepsilon

It may not seem strong at first sight, but, if you look carefully, then you will relise that it is. Here, the absolute value is bounded by some real number independent of , which is not the same as before.

How can we prove such a thing? First, notice that we can assume that for some , this follows from the fact that for every real number, we can find a number of the form smaller than it.

Recall that for every , we can define:

- – the floor function
- – the fractional part.

Consider the following sequences:

\{\alpha\},\{2\alpha\},\{3\alpha\},\dots,\{(N+1)\alpha\}

And:

[0,\frac{1}{N}),[\frac{1}{N},\frac{2}{N}),\dots,[\frac{N-1}{N},1)

The second sequence cover the whole interval . Therefore, every number from the first sequence is in one of the intervals from the second sequence (Recall that for every , ).

There are elements in the first sequence, while there are only intervals in the second sequence.

Can you guess what I am going to use? That’s right – The pigenhole principle. It allows us to conclude that there are two elements from the first sequnce in the same interval. Let’s denote them by . Since each interval has length of , then:

|\{l\alpha\}-\{k\alpha\}|<\frac{1}{N}

But, recall that . Therefore:

|\{l\alpha\}-\{k\alpha\}|=|(l\alpha-\lfloor l\alpha\rfloor)-(k\alpha-\lfloor k\alpha\rfloor)|=|\overbrace{(l-k)}^n\alpha-\overbrace{(\lfloor l\alpha\rfloor-\lfloor k\alpha\rfloor)}^m|

Then, as we wanted!

## Summary

All this post was dedicated to one simple statement – the pigenhole principle. Even though it is such a simple statement, we saw many applications for it. And trust me, there are a **lot** more! That’s it for now, I hope that you have found this simple statement fascinating, since… well… It is **so** simple!