The Pigeonhole principle

The Pigeonhole principle states that if there are pigeons, and all of them sits in one of holes, then there has to be a hole that contains at least 2 pigeons. More generally, if there are pigeons in holes, there must be a hole that contains a t least pigeons.

Boxes are another analogy used to describe this principle. If we have objects (socks, gloves, balls, etc.) placed in boxes, then at least one box contains two.

This argument was popularized by Peter Gustav Lejeune Dirichlet in 1834. It is also common to refer to the idea as Dirichlet's principle or the Dirichlet principle.

(TODO: Tell the story about the inhabitants of Paris.)

Dividing the difference

Given integers, there exists a pair such that divides .

The most crucial step in applying the Dirichlet principle is identifying what plays the role of the pigeons and holes. In this problem, the pigeons are clearly the integers. To get the argument through, we need to pick holes. Let us choose these to be the numbers between and inclusive, that is, the possible remainders when dividing an integer by . (Note that the remainder of is .) Under this scheme, each of the possible integers we started with will be associated with its remainder. Dirichlet's principle implies there are at least two integers with the same remainder, and hence their difference must be divisible by .

The idea of using the remainders is a very powerful tool in mathematics. Let us introduce then some notation. The remainder of a number when divided by will be called its congruence class modulo . Whenever two numbers and have the same congruence class modulo , we will say they are coungruent modulo and write write .

Summing to 10

For every 6-element subset of , there exists a pair of distinct integers such that .

Let us choose categories in a way that can help us with this problem. The idea is to group together elements which sum up to 10. The first one will be , the second , then , , and at last the element 5 alone, .

We now have 6 integers in 5 boxes, so there is at least one box that contains two of them. This box cannot be since it the set has only one element. Then the box containing two has to be one of the others, which proves that there are two integers whose sum is 10.

We have the same number of friends!

Is it possible that at a party all guests have different numbers of friends attending?

SOLUTION ONE: Let us say the number of people attending the party is . The possibilities for the number of friends that people can have at the party vary from 0 (in case somebody does not know anybody else) to (for someone knowing everybody else). This gives us possibilities. On the other hand, we also have people, so we cannot conclude that there are two people with the same number of acquaintances.

We need to also analyze the possibility that there is exactly one person knowing nobody else, one person knowing exactly one other, one person knowing two, and so on until exactly one person that knows anybody else. But this is not possible. If there is a person A not knowing anybody, then there cannot be a person B that knows anybody else, because B cannot know A!

Rephrasing this, we can use a similar strategy to the previous provlem and "group" the possibilities and in one box. We know that at most one possibilitiy in this box will be achieved, so we are in the situation of categories with people associated with them. It follows that there are two people having the same number of friends.

SOLUTION TWO: We will present an inductive argument which makes the use of of Dirichlet's principle a little more transparent. Suppose we know that for any group of people there are two that have the same number of friends (this is called the inductive hypothesis).

Consider a party of people. If there is a person knowing 0 people, we can consider the remaining people. You can say they are "disconnected" from , so we restrict the problem to this smaller group of people. But we already know that two of them must have the same number of friends by the inductive hypothesis.

On the other hand, consider the opposite situation in which everyone has at least one friend. Then we can apply the Dirichlet principle, because we have people, and possibilities for the number of friends they have (the numbers from 1 to ).

To conclude the proof by induction, we need to do what is called "proving the base case". Suppose that we have two people (the simplest that this problem can be, because with one person the problem does not make sense), that let us prove our statement. The only two possibilities here are that they know each other, or that they don't. In both cases, they have the same number of friends, so the claim follows.

The Friendship Theorem

Given a group of six people, show that there always exist three such that either

  • all know each other, or
  • none of them are acquaintances.

Even though it sounds simple, this is a very tricky problem.

Start by picking one of the six people, and call her A. Let's analyze her relations with the other 5. To apply Dirichlet's principle, we will use the the two possible relation types (acquantance or not) as categories. It follows that there are at least three people (call them B, C, and D) that have the same relation with A.

First, let us say that they all know A. In this case, either two of them know each other (and hence together with A they form a triple of people that all know each other) or there is no couple of them that know each other (and in such case B, C, D form of a triple that has no acquaintances). This concludes the first case.

The case in which B, C and D do not know A is exactly the same, because the problem is symmetric. This means that if we can toggle the relations between every pair of people, the second case reduces to the first - so it must be true as well.

REMARK-MATH-HISTORY: Following the same argument, we can prove the same result that among 18 people there are 4 that either all know each other, or are not acquainted at all.

What would happen if we decrease 18 to 17. Would the same statement be true? More generally, what is the minimum number such that this situation occurs? The solutions to this problem are called Ramsey numbers. For example, this exercise showed that is at most 6. Proving that required an extensive check using a computer of all possibilities. The only thing we know nowadays about is that it lies between 43 and 49 inclusive.

The combinatorialist Joel Spencer has an anecdote about Paul Erdős, a Hungarian mathematician that spent many years working on this type of problems.

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for . In that case, he believes, we should attempt to destroy the aliens.

The square orchard

You own a small orchard containing 51 trees. The shape of the garden is a square with side length 70 meters. It is possible to use a circular fence of radius 10 meters to enclose at least 3 of the trees?

The statement of this problems reminds us immediately of Dirichlet theorem. We have 51 trees (pigeons), and we want 3 to be close enough so they are contained in a circle of radius 10.

To explain the solution of the problem, let us apply some reverse thinking. How many boxes do we need so that at least 3 of the 51 trees are in the same box? The answer is 25. (We solved and to find ). This tells us that if we divide the square in 25 regions, then there is a region that contains 3 trees. For obvious reasons, we cannot split a square in 25 circles of radius 10, there's no way we can have the boundaries to adhere to one other.

On the other hand, we can try to divide the square in 25 regions each of which is contained in a circle of radius 10. The obvious choice is to divide it in smaller squares of radius . The biggest square that is contained in a circle of radius 10 has side , so a circle of radius 10 can indeed contain a square of side 14. Wrapping everything up, recall that we found that there is one of the little squares that contains at least 3 trees, hence we also have a circle of radius 10 containing the same 3 trees.

The monochromatic rectangle

Imagine that each point with integer coordinates in the plane is colored either black or white. Show that there always exists a rectangle with sides parallel to the axes and vertices of the same color.

In this problem, unlike many of the others, we are given a huge amount of information, way more that what we need. In fact, we will restrict to analyze only a rectangle as in the picture below, and prove that a monochromatic rectangle exists inside that rectangle. This is not the only way: the reader is encouraged to try if the same argument works for differently shaped rectangles.

(TODO: PICTURE)

Let us consider one column in our rectangle. How many different ways are there of coloring it? The answer is 8, because of the 2 choices for the upper point, 2 for the middle, and 2 for the lower. So, by Dirichlet principle, we have two columns in our rectangle that are two columns that are colored in the same way. In these two columns, moreover (still by Dirichlet principle) we have at least two points of the same color. Considering the 4 points obtained in this way, we get a monochromtic rectangle.

BONUS QUESTION: How can we modify the proof to show that there is a monochromatic rectangle in a rectangle? And what about ?