抽屉原理

$Pigeonhole$ $Principle!$

The Pigeonhole Principle is pretty intuitive and follows from the logical observation that if there are n boxes, into which more than n objects have been placed, then at least one of the boxes must have received more than one of the objects.

For example, let's say we have the problem:

Suppose that we draw cards consecutively and without replacement from a 52 card deck. How many do we need to draw to ensure that there will be a pair?

We can consider the possible values of the cards to be the boxes, or Pigeon Holes, and the cards to be the objectsm or Pigeons. Then there are 13 boxes, and to get there to be 2 objects to be in the same box, then we need 14 objects. So by the 14th draw we must have a pair.

Extension of the Pigeonhole Principle: If $(m-1)*n+1$ objects have been placed in n boxes, then at least one of the boxes must contain m of the objects.

Try to see how it works by yourself, it's pretty easy to see.

Pigeonhole Principle : The Statement

Credits of the image to this site.

Yes, what could be easier than the observation that if we put more than $n$ pigeons into $n$ pigeonholes, there will be a hole containing at least $2$ pigeons.

However, many results in mathematics are all consequences of this observation, which is called the Pigeonhole Principle (or the Dirichlet's box principle).

Well, that's the statement of the pigeonhole principle. But does it really have any real world applications, you might ask. Well, yes, here's a simple example.

We'll exclude February $29$ for the purposes of this problem.

There're $366$ people in a room. Prove that $2$ of them have the same birthdays.

Indeed, this follows immediately from the pigeonhole principle.

Pigeonhole Principle : Generalized

If you have $p$ pigeons and $h$ holes, then at least one hole contains at least $\lceil\frac{p}{h}\rceil$ pigeons.

Credits to this site.

Here's an example of the generalized pigeonhole principle in action.

$41$ rooks are placed on a $10 \times 10$ chessboard. Prove that there must exist five rooks, none of which attack each other.

Ok, so the pigeonhole principle tells us that there exists a row with at least $5$ rooks. Now, let's consider the other rows. There are at most $31$ rooks left in the other rows, so by the pigeonhole principle, there exist another row with at least $4$ rooks.

Applying the same concept proves the existence of another row with at least $3$ rooks, another row with at least $2$ rooks, and finally another row with at least one rook.

Now, consider these five rows.

Select a rook from the row with at least one rook.

We can pick a rook from the row with at least two rooks that is not in the same column with the rook we just chosen.

Then, we pick a rook from the row with at least three rooks that is not in the same column with the rooks we just chosen.

Continuing the process, we obtain our $5$ desired rooks. $\blacksquare$.

Now, see the power of the pigeonhole principle now?

Now we are talking about a fundamental method or process of elementary number theory. I try to describe the pigeonhole principle informally at a bit rate for the first. If you are form Bangladesh, you know very well that Dhaka is one of the crowded cities all over the world. Perhaps we can find approximately 2 cores people here. Now if I ask- can we able to get more than two people who have same number of hairs? What will be your answer? At first you had better know that, there are approximately 200000 hairs staying on your head. How can we solve this problem? Can you remember how to divide an integer number? Of, course. Why can’t?

But I claim that many of you can hardly know that division is one of the process what is determined by subtraction. If I say to you that you should divide 100 by 10. What will be your answer? 10, right?

How do you solve this? Simply, 100/10. But there is an another fundamental process to get the answer. How? Please say to me, how many times can you subtract 10 from 100? Answer -10 . isn’t it ?

Actually it is one of the process. If you divide an integer number by an another integer number and want to get the quotient as an integer number, you can use this process which is described now. It is time to get our answer how many people we can find in Dhaka who have same numbers of hairs. Simple , we can divide 2 cores by 200000 . The answer is 100. On other hand we can find how many times, we subtract 200000 from 2 cores. The answer is also 100. If you have 10 pigeon holes for pigeon. And you also have 11 pigeons. If you try to attach every pigeons in every hole, you will face a problem. You have to attach at least 2 pigeons for a hole. Actually it is called pigeonhole principle. ‘’In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item.’’ (This definition is from Herstein 1964, p. 90 ) So if we have 3 holes and 7 pigeons, then we can keep every pigeon in every hole. After the first round 4 pigeons remain outside the box. Then we operate the same operation. After the second operation, 1 pigeon will stay. Then we have to choose one box for the last pigeon. And the last box or hole has 3 pigeons. We can solve it by an another method.

7/3 = 2.333. This term means that we have to choose 2 pigeons for every box if we want to arrange them similarly. But lastly we have to break the law of similarity and choose one of the box among them for the last pigeon. If we observe 2.3, we can say that there will be a box among all who has 3. If we observe 2.93784 , or , 2.394 whatever , the answer is always same. If we get a quotient as a non-integer number we should round the number as if it can reach the next integer. To site and example-

4.4543 is to 5

67.234 is to 68

Bla bla bla.

Tomorrow I will try to describe more things of pigeonhole principle.

If $n$ objects are placed into $k$ boxes, then there is at least one box containing at least $\lceil\frac{n}{k}\rceil$ objects, and at least one box containing at most $\lfloor\frac{n}{k}\rfloor$ objects. This is easily proven by contradiction.

Often, the hard part is determining what the boxes and objects are.

The best way to familiarize yourself with the Pigeonhole Principle is simply to do problems.

Problem: Show that among any $n+1$ integers not exceeding $2n,$ there must be two integers which are relatively prime to each other.

Generalized Pigeonhole Principle: If $N$ objects are placed into $k$ boxes, then there is at least one box containing at least $\lceil\frac{N}{k}\rceil$ objects and there is at least one box containing at most $\lfloor\frac{N}{k}\rfloor$ objects.

Usually, the hardest part is determining what the "boxes" and "objects" are.

Example 1: Show that for every positive integer $n,$ there is a multiple of $n$ that has only 0s and 1s in its decimal expansion.

Solution: For any given integer $n>0,$ construct the integers $1,11,111, ..., 11111...11,$ where the last integer has exactly $n + 1$ 1's. When these $n + 1$ integers are divided by $n,$ two of the remainders must be the same, as the remainder can only be one of $0, 1, 2, ..., n-1.$ The larger of these two integers less the smaller one is a multiple of $n,$ and it is an integer consisting of only 0s and 1s.

Example 2: The side of a square is of length 2. How many points can you plot in this square such that the distance between any two of these points is greater than $\sqrt{2}?$

Solution: Clearly, we can find a set of 4 points which satisfies the conditions. Note that the distance between any two points in a square must not be longer than the diagonal of the square. Split the square into four unit squares. If we choose 5 or more points, at least two of these points must be in the same square. However, this means that the distance between these points is less than or equal to $\sqrt{2},$ a contradiction!

Example 3: Show that among any $n + 1$ positive integers not exceeding $2n,$ there must be an integer that divides one of the other integers.

Solution: Any such number can be written as $2^k \cdot j,$ where $k$ is a whole number and $j$ is an odd number with $1\le j < 2n.$ Since there are at most $n$ odd numbers between 0 and $2n,$ there must be two positive integers not exceeding $2n$ that can be written as a power of 2 multiplying the same odd number. Therefore, one of these two must divide the other.

Example 4: Show that at least four of any 22 days must fall on the same day of the week.

Solution: $\lceil\frac{22}{7}\rceil=\boxed{4.}$