Pigeonhole principle

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, $n = 10 m = 9$ , 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 $n$ items and $k containers$ such that $n>m$ . put each item at a time in a different container, after $m$ 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 $n$ items to $m$ containers. Put in each container one items at most. We got that in the maximal case, $m$ items are in a container, but $n>m$ 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 $A$ and the set of containers by $B$ . What we’re trying to do formally is to map each element of $A$ to an element of $B$ in such a way that if $a_1,a_2\in A$ , then they can’t be sent to the same element in $B$ . 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 $f$ from the set of piegons $A$ to the set of piegonholes $B$ .

The map $f$ goes from $A$ to $B$ . I am going to give it a special symbol: $f:A\to B$ .

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

|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 $m,n\geq 0$ be some integers. Then for every sequence of $mn+1$ real and differenet numbers, there is an increasing sequence of length $m+1$ or a decreasing sub-sequence with length $n+1$ .

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

Notice that $mn+1$ is the ‘best’ possible number: For every $m,n\geq 0$ , there is a sequence of length $mn$ without an increasing subsequence of length $m+1$ and without decreasing sequence of length $n+1$ 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 $n$ decreading sequences of length $m$ .

The Proof

Suppose that $(x_1,\dots,x_k)$ is a sequence of $k$ different real numbers without increasing subsequence of length $m+1$ and without decreasing sequence of length $n+1$ .

I am going to prove that $k\leq mn$ . 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 $mn+1$ . If I manage to prove it, then I showed that there aren’t such ‘bad sequences’ of length $mn+1$ , Which is exactly what I wanted.

Ok, so let’s prove it. I am going to define for every $1\leq i\leq k$ two things:

$a_i$ = the length of the longest increasing sequence that starts at $x_i$
$b_i$ = the length of the longest decreasing sequence that starts at $x_i$

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 $(a_i,b_i)$ . By our assumption, there is no increasing subsequence of length $m+1$ , we can conclude that $1\leq a_i\leq m$ for every $i$ . Moreover, by similar argument, we can conclude that $1\leq b_i\leq n$ .

Let’s define a map: $f:\{1,\dots,k\}\to \{1,\dots,m\}\times \{1,\dots,n\}$ by:

f(i)=(a_i,b_i)

Notice that $|\{1,\dots,k\}|=k$ and $|\{1,\dots,m\}\times \{1,\dots,n\}|=m\cdot n$ . If we will prove that $f$ 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 $i\neq j$ then $(a_i,b_i)\neq (a_j,b_j)$ . We can assume WLOG that $i<j$ . Now, there are two cases:

$x_i < x_j$ : this means that for every increasing sub-sequence that starts in $x_j$ , we can add $x_i$ to it to get a longer sub-sequence. Thus, $a_i > a_j$ , an in particular, $a_i\neq a_j$ .
$x_i > x_j$ : this means that for every decreasing sub-sequence that starts in $x_j$ , we can add $x_i$ to it to get a longer sub-sequence. Thus, $b_i > b_j$ , an in particular, $b_i\neq b_j$ .

In both cases we have $(a_i,b_i) \neq (a_j,b_j)$ 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 $\mathbb{R}$ . In other words: for every real number, we can always find a rational number as close to it as we want.

Formally: for every $\alpha in \mathbb{R}$ , and for every $\varepsilon > 0$ . There exitsts $n,m\in \mathbb{Z}$ such that:

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

This is equivalent to $|n\alpha-m| < n\varepsilon$ . However, can we find a better approximation? As it turns out, you can!

I state that for any $\alpha\in\mathbb{R},\varpsilon>0$ we can find $n,m\in\mathbb{Z}$ 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 $n$ , which is not the same as before.

How can we prove such a thing? First, notice that we can assume that $\varpsilon = \frac{1}{N}$ for some $N\in\mathbb{N}$ , this follows from the fact that for every real number, we can find a number of the form $\frac{1}{N}$ smaller than it.

Recall that for every $x\in\mathbb{R}$ , we can define:

$\lfloor x\rfloor = \max \{k\in\mathbb{Z}:k\leq x\}$ – the floor function
$\{x\}=x-\lfloor x\rfloor$ – 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 $[0,1)$ . Therefore, every number from the first sequence is in one of the intervals from the second sequence (Recall that for every $x\in\mathbb{R}$ , $\{x\}\in[0,1)$ ).

There are $N+1$ elements in the first sequence, while there are only $N$ 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 $\{l\alpha\},\{k\alpha\}$ . Since each interval has length of $\frac{1}{N}$ , then:

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

But, recall that $\{x\} = x-\lfloor x\rfloor$ . 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, $|n\alpha-m|<\frac{1}{N}$ 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!

Proofs

Formal definition

Trees and leaves

Triangle and dots

Erdős–Szekeres theorem

The Proof

Approximating with the rationals

Summary

Like this:

Leave a Reply Cancel reply

Proofs

Formal definition

Trees and leaves

Triangle and dots

Erdős–Szekeres theorem

The Proof

Approximating with the rationals

Summary

Share

Like this:

Leave a Reply Cancel reply