mozaMedical by Mozaik Education

The pigeonhole principle

Example 1

There are \latex{2} rabbits and \latex{3} pigeons in the magician’s hat. The magician conjures the animals out of the hat at random. So far he has conjured \latex{3} animals. Which of the following statements are true for sure with respect to the conjured animals?

There are two rabbits.
There are two pigeons.
There are two animals of the same type.
There is a pigeon.

Solution

A and B can be both true and false, therefore it is not true for sure.

C is true for sure, because there are two types of animals, so it is possible to conjure two animals so that they are of different types, but the type of the third animal will surely be the same as one of the previous two.

D is true for sure, because there are \latex{2} rabbits in the hat, so no matter how we take out three animals, there needs to be a pigeon among them.

Example 2

There are seven registers for coins in a cash register: for \latex{ 1 }; \latex{ 2 }; \latex{ 5 }; \latex{ 10 }; \latex{ 20 }; \latex{ 50 } euro cents and for \latex{ 1 } euro. At the beginning the cash register is empty; the customers keep paying with coins.

At least how many coins should be there in the cash register so that there is a register with at least two coins?
At least how many coins should be there in the cash register so that there is a register with at least \latex{ 11 } coins?

Solution (a)

If there were \latex{7} coins in the cash register, then it would be still possible to have exactly one coin in each of the \latex{7} registers. But if there were \latex{8} coins, then there must be a register in which there are at least two coins.

Therefore there should be at least \latex{8} coins so that there is at least one register for sure in which there are at least two coins.

\latex{\blacklozenge} \latex{\blacklozenge} \latex{\blacklozenge}

We can also formulate this way of thinking generally:

THE PIGEONHOLE PRINCIPLE: We place \latex{n} objects in \latex{k} pigeonholes.

If \latex{n \gt k}, then there will be a pigeonhole for sure in which there are at least two objects.

The statement is obviously true, since if in all the \latex{k} pigeonholes there was at most one object, then there would be a total of \latex{k} objects at most.

Solution (b)

If there were \latex{70} coins in the cash register, then it would be still possible to have exactly \latex{10} coins in each of the \latex{7} registers.

But if there are \latex{ 71 } coins, then there is a register for sure in which there are at least \latex{ 11 } coins. Since if in all \latex{ 7 } registers there were at most \latex{ 10 } coins, then there would be a total of \latex{ 70 } coins at most.

Therefore there should be at least \latex{71} coins so that there is at least one
register for sure in which there are at least \latex{11} coins.

\latex{\blacklozenge} \latex{\blacklozenge} \latex{\blacklozenge}

Based on this we can formulate the pigeonhole principle more generally:

We place \latex{n} objects in \latex{k} pigeonholes. If \latex{n \gt k \times p} then there will be a pigeonhole for sure in which there are at least \latex{p + 1} objects.

The statement is obviously true, since if in all the \latex{k} pigeonholes there were at most \latex{p} objects, then there would be a total of \latex{k \times p} objects at most.

Note: The English “pigeonhole principle” expression represents the problem well.

Example 3

\latex{30} shots are on a square shaped target with \latex{5\, dm} long sides. Let us show that there are two shots for sure the distance of which is at most \latex{1.5\, dm}.

Solution

With the help of line segments parallel with the sides let us divide the square with the \latex{5\, dm} long sides into \latex{25} pieces of squares with \latex{1\, dm} long sides. Among the \latex{30} points there are two for sure which are in the same square with \latex{1\, dm} long sides. (Figure 17)

The diagonal of the small square is \latex{\sqrt{2}\lt 1.5}, thus the distance of the two points in the small square must be less than \latex{1.5\, dm}.

Example 4

Is it true that there are two people in any company of six so that these two have the same number of acquaintances in this company? (People are acquainted with each other mutually; people are not acquainted with themselves.)

Solution

Let us draw a graph: let us assign the points of the graph to the people, and let us connect two points with an edge if the two people corresponding to the points are acquainted. Let us write the number of acquaintances, i.e. the edges starting from the points, next to the points. This number is the degree of the point in the graph. Regarding the acquaintanceships among the \latex{6} people we realise that we can always find two people who have the same number of acquaintances. (Figure 18)

\latex{5}\latex{5}\latex{5}\latex{5}\latex{5}\latex{5}\latex{1}\latex{3}\latex{5}\latex{4}\latex{2}\latex{3}\latex{0}\latex{2}\latex{3}\latex{4}\latex{1}\latex{2}Figure 18

We can realise that nobody has more than \latex{5} acquaintances. The number of acquaintances can be \latex{0}; \latex{1}; \latex{2}; \latex{3}; \latex{4}; \latex{5}. But if someone has \latex{5} acquaintances, then he/she knows everyone in the company, so there cannot be a person who does not know anyone. Similarly if someone does not have acquaintances, then there cannot be a person who knows everyone. Therefore \latex{0} and \latex{5} cannot appear at once, i.e. there are \latex{5} possibilities regarding the number of acquaintances. Since there are \latex{6} people, there must be two among them who have the same number of acquaintances.

Example 5

We wrote down five positive whole numbers. Is it true that there are two among them for sure the difference of which is divisible by \latex{4}?

Solution

The possible remainders when dividing the positive whole numbers by \latex{4} are as follows: \latex{0}; \latex{1}; \latex{2} or \latex{3}. Considering five numbers there must be two among them, which leave the same remainder when divided by \latex{4}. If two numbers leave the same remainder when divided by \latex{4}, then their difference is divisible by \latex{4}. Therefore we can surely find two among the five numbers the difference of which is divisible by \latex{4}.

Example 6

Is it true that we can always choose some (one, two, three or four) numbers out of any four positive whole numbers so that the sum of the chosen numbers is divisible by \latex{4}?

Solution

Let the four numbers be: \latex{a}, \latex{b}, \latex{c}, \latex{d}. Let us consider the following four numbers: \latex{a}, \latex{a + b}, \latex{a + b + c}, \latex{a + b + c + d}.

Let us divide them by \latex{4}, and let us examine the remainders; these can be \latex{0}; \latex{1}; \latex{2} or \latex{3}. If there is a \latex{0} remainder among them, then we are ready, because this number is divisible by \latex{4}, and since it is the sum of some of the original numbers, we found some numbers the sum of which is divisible by \latex{4}.

If there is no \latex{0} remainder among them, then there are \latex{3} different remainders and \latex{4} numbers, so there must be two numbers which leave the same remainder when divided by \latex{4}. When subtracting these two numbers the difference is divisible by \latex{4}, and it is also true that it is the sum of some of the original numbers.

Therefore there must be some numbers among the original numbers the sum of which is divisible by \latex{4}.

Note:

Two players write down positive whole numbers in turns on a piece of paper. The player who can find some numbers (possibly even one) – among the numbers on the paper after the opponent wrote down his/her number – the sum of which is divisible by \latex{4}. Let us play! Who has a winning strategy, and after at most how many steps is the game finished, if the players pay attention and count correctly?

Solution: Instead of the numbers let us examine the remainders they leave when divided by \latex{4}. Let us represent the steps of the game on a directed graph. A number is denoted by a blue circle, if the starting player wins with it, and it is denoted by a green square, if the second player wins. (Figure 19)

starting player the remainder
of the first number
when divided by \latex{4}\latex{ 0 } second player
the remainder
of the second number
when divided by \latex{4} starting player the remainder
of the third number
when divided by \latex{4} second player
the remainder
of the fourth number
when divided by \latex{4}\latex{ 2 }\latex{ 1 }\latex{ 3 }\latex{ 0 }\latex{ 3 }\latex{ 1 }\latex{ 2 }\latex{ 0 }\latex{ 1 }\latex{ 2 }\latex{ 3 }\latex{ 0 }\latex{ 1 }\latex{ 2 }\latex{ 3 }\latex{ 0 }\latex{ 1 }\latex{ 2 }\latex{ 3 }\latex{ 0 }\latex{ 1 }\latex{ 2 }\latex{ 3 }\latex{ 0 }\latex{ 1 }\latex{ 2 }\latex{ 3 }\latex{ 0 }\latex{ 1 }\latex{ 2 }\latex{ 3 }\latex{ 0 }\latex{ 1 }\latex{ 2 }\latex{ 3 }\latex{ 0 }\latex{ 1 }\latex{ 2 }\latex{ 3 }\latex{ 3 }\latex{ 2 }\latex{ 1 }\latex{ 0 }\latex{ 0 }\latex{ 1 }\latex{ 2 }\latex{ 3 }

Figure 19

If the first player writes down \latex{0}, the second player chooses that number and immediately wins. If the first player writes down \latex{1}, and the second player writes down \latex{2}, then no matter what the first player writes down, the second player wins. If the first player writes down \latex{2}, and whether the second player writes down \latex{1} or \latex{3}, he/she wins in any case. If the first player writes down \latex{3}, the second player writes down \latex{2}, thus the second player wins for sure.

If the two players realise for sure that there are some numbers the sum of which is divisible by \latex{4}, then the game will definitely finish in four steps.

Example 7

We write down the first \latex{100} positive whole numbers on separate pieces of paper and we put these pieces of paper into a hat. Blindfolded and without replacement we draw \latex{55} numbers from the hat. Is it true that there are surely two numbers among the drawn ones the difference of which is exactly \latex{9}?

Solution I

Let us list the numbers which leave the same remainder when divided by \latex{9}.
\latex{0} as a remainder:

\latex{9;\, 18;\, 27;\, 36;\, 45;\, 54;\, 63;\, 72;\, 81;\, 90;\, 99 \qquad} these are \latex{11} numbers.

\latex{1} as a remainder:

\latex{1;\, 10;\, 19;\, 28;\, 37;\, 46;\, 55;\, 64;\, 73;\, 82; \,91;\, 100 \qquad} these are \latex{12} numbers.

\latex{2} as a remainder:

\latex{2;\, 11;\, 20;\, 29;\, 38;\, 47;\, 56;\, 65;\, 74;\, 83;\, 92 \qquad} these are \latex{11} numbers.

\latex{3} as a remainder:

\latex{3;\, 12;\, …;\,93 \qquad} these are \latex{11} numbers.

\latex{4} as a remainder:

\latex{4;\, 13;\, …;\, 94 \qquad} these are \latex{11} numbers.

\latex{5} as a remainder:

\latex{5;\, 14;\, …;\, 95 \qquad} these are \latex{11} numbers.

\latex{6} as a remainder:

\latex{6;\, 15;\, …;\, 96 \qquad} these are \latex{11} numbers.

\latex{7} as a remainder:

\latex{7;\, 16;\, …;\, 97 \qquad} these are \latex{11} numbers.

\latex{8} as a remainder:

\latex{8;\, 17;\, …;\, 98 \qquad} these are \latex{11} numbers.

Since we drew \latex{55} numbers, there are \latex{9} different remainders, and \latex{55 \gt 6 \times 9}, thus according to the pigeonhole principle there must be a remainder so that at least \latex{7} numbers leave the same remainder when divided by \latex{9}. If this remainder is \latex{1}, then we drew \latex{7} out of the \latex{12} numbers leaving \latex{1} as a remainder. And this is only possible if there are two numbers among them which are adjacent ones in the list below, i.e. their difference is exactly \latex{9}:

\latex{\bold{1};\, 10;\, \bold{19};\, 28;\, \bold{37};\, 46;\, \bold{55};\, 64;\, \bold{73};\, 82;\, \bold{91};\, 100}.

If the \latex{7} numbers leave a different remainder, then we drew \latex{7} out of \latex{11} numbers leaving the same remainder; similarly it is true that there are two among them which are adjacent ones in the list above, i.e. their difference is exactly \latex{9}.
Therefore there are certainly two numbers among the drawn ones the difference of which is exactly \latex{9}.

Since we drew \latex{55} numbers, there are \latex{9} different remainders, and \latex{55 \gt 6 \times 9}, thus according to the pigeonhole principle there must be a remainder so that at least \latex{7} numbers leave the same remainder when divided by \latex{9}. If this remainder is \latex{1}, then we drew \latex{7} out of the \latex{12} numbers leaving \latex{1} as a remainder. And this is only possible if there are two numbers among them which are adjacent ones in the list below, i.e. their difference is exactly \latex{9}:

Solution II

Let us denote the drawn numbers as follows: \latex{x_1, x_2, ..., x_{55}}.

The set \latex{A} contains the drawn numbers, and the set \latex{B} contains the numbers \latex{9} greater than the elements of the set \latex{A}:

\latex{\text{A:\quad}1 \le x_1\lt x_2 \lt x_3 \lt ... \lt x_{55} \le 100}.

\latex{\text{B:\quad}10 \le x_1 + 9 \lt x_2 + 9 \lt ... \lt x_{55} + 9 \le 109}.

The elements of \latex{\text{A} \cup \text{B}} are greater than or equal to \latex{1} and less than or equal to \latex{109}, therefore there can be at most \latex{109} types of elements. There are \latex{110} elements in the set \latex{\text{A}} and the set \latex{\text{B}} together, there are at most \latex{109} elements in the set \latex{\text{A} \cup \text{B}}, which means that the set \latex{\text{A}} must have an element which is also in the set \latex{\text{B}}: \latex{x_i = x_j + 9}, which means that there are two numbers among the drawn ones the difference of which is \latex{9}.

Exercises

{{exercise_number}}. There are \latex{3} rabbits and \latex{5} pigeons in the magician’s hat. The magician conjures the animals out of the hat at random. So far he has conjured \latex{5} animals. Which of the following statements are true for sure with respect to the conjured animals?

There are two rabbits.
There are two pigeons.
There are two animals of the same type.
There is a pigeon.

What can we say about the \latex{3} animals that remained in the hat?
At least how many animals should be drawn so that the statement A would be true for sure?
At least how many animals should be drawn so that the statement B would be true for sure?
At least how many animals should be drawn so that the statement C would be true for sure?
At least how many animals should be drawn so that the statement D would be true for sure?
At least how many animals should be drawn so that the statement A and the statement B would be true for sure?
At least how many animals should be drawn so that the statement A or the statement D would be true for sure?

{{exercise_number}}. Out of the \latex{33} students of the class \latex{15} learn Spanish, \latex{13} learn German and \latex{5} learn French as a foreign language. About which foreign language group can we say that there are at least two students in the group for sure who were born in the same month?

{{exercise_number}}. \latex{33} students of a class wrote a language test, and they received grades \latex{\text{A}} to \latex{\text{E}}. Show that there are \latex{7} students who received the same grade.

{{exercise_number}}. There are three types of balls in a box: \latex{14} red, \latex{17} blue and \latex{21} green balls. At least how many balls should be drawn without replacement at random so that there would be

at least two of the same colour;
at least one of each of the three colours;
at least two green ones;
at least two red ones among the drawn balls?

{{exercise_number}}. There are three types of balls in a box: \latex{4} red, \latex{7} blue and \latex{11} green balls. We have drawn \latex{5} balls without replacement and at random. Which of the following statements are true for sure with respect to the balls left in the box?

There

are no red balls left in the box.
is a ball of each colour left in the box.
is a blue ball left in the box.
are balls of at least two different colours left in the box.

{{exercise_number}}.

In the mess in Gladys' drawer there are \latex{5} pairs of different gloves (the glove for the left hand is different from the one for the right hand). At least how many gloves should she pull out without looking there so that there would be a matching pair for sure among the pulled ones?

In the mess in Sue's drawer there are \latex{5} pairs of alike gloves (the glove for the left hand is different from the one for the right hand). At least how many gloves should she pull out without looking there so that there would be a matching pair for sure among the pulled ones?

{{exercise_number}}. There are four types of apples in a box, equal amount of each type, \latex{100} pieces all together. How many apples should be taken out blindfolded so that there would be at least \latex{10} apples of one of the types for sure? How many apples should be taken out blindfolded so that there would be at least \latex{1} apple of each type for sure?

{{exercise_number}}. In a dark room there are \latex{12} red and \latex{12} blue socks in a drawer.

At least how many socks shall I take out of the drawer so that there would be at least two socks of the same colour for sure?
At least how many socks shall I take out so that there would be two red socks among them for sure?

{{exercise_number}}. Let us assume that there are a number of blue and a number of red socks in a drawer, and we know that I have to take out at least as many socks to have a pair of socks of the same colour for sure as many at minimum to have two socks of different colours. How many socks are there in the drawer?

{{exercise_number}}. Let us write “\latex{1}” on one disc, “\latex{2}” on two discs, “\latex{3}” on three discs and so on, “\latex{30}” on thirty discs. Let us put the discs in a box, and then let us draw discs at random without replacing them. At least how many discs should be drawn so that there would be at least \latex{10} discs for sure which have the same number written on?

{{exercise_number}}. \latex{100} people attend at a ball; each of them has blond or brown hair. They settle down in the four rooms as they like. We are looking for the largest n for which we can definitely find a room in which there are \latex{n} people with the same hair colour.

{{exercise_number}}. \latex{10} shots are on a square shaped target with \latex{6\, dm} long sides. Show that there are two shots for sure the distance of which is at most \latex{3\, dm}.

{{exercise_number}}. \latex{7} shots are on a regular hexagon shaped target with \latex{40\, cm} long sides. Show that there are at least two among them the distance of which is not greater than \latex{40\, cm}.

{{exercise_number}}. Place \latex{30} points in a square with \latex{1}-unit-long sides. Is it true that we can always find \latex{4} points which can be covered by a disc with \latex{0.25}-unit-long radius? (It is ok if a part of the disc is outside the square.)

{{exercise_number}}. \latex{18} straight lines are given in the plane so that there are no parallel ones among them. Is it true that there always are two among them so that the angle included between them is at most \latex{10º}?

{{exercise_number}}. A rectangle is intersected by \latex{13} straight lines so that each straight line divides the rectangle into two quadrilaterals the ratio of the areas of which is \latex{1 : 5}. Show that there are \latex{4} straight lines which intersect each other at one point.

{{exercise_number}}. \latex{100} flies are flying around in a \latex{5} m \latex{\times} \latex{6} m \latex{\times} \latex{3} room. Is it true that there always are two among them so that the distance between them is less than \latex{2\, m}?

{{exercise_number}}. We randomly choose \latex{2,001} points inside a cube with \latex{4}-unit-long sides. Show that we can choose \latex{32} points out of these so that no matter in which order we connect the \latex{32} points by creating a closed polygon, the perimeter of this polygon cannot be greater than \latex{32 \times \sqrt{3}} .

{{exercise_number}}. Some people shake hands in a company of \latex{10}. Then everyone is asked how many people he/she shook hands with. Are there always two people who shook hands with the same number of people in the company?

{{exercise_number}}. \latex{8} teams were playing in a championship; each team played against all the other teams once. During the championship it was counted how many matches each of the teams had played till then, and it was stated that each of the teams had played different numbers of matches.
Was this statement true?

{{exercise_number}}. At least how many whole numbers should be written down so that there would be two among them for sure the difference of which is divisible by \latex{8}?

{{exercise_number}}.

Is it true that if we write down \latex{ 15 } consecutive whole numbers, then there must be two among them the sum of which is divisible by \latex{ 15 }?
Is it true that if we write down \latex{ 15 } positive whole numbers, then there must be two among them the sum of which is divisible by \latex{ 15 }?
At most how many whole numbers can be written down so that neither the sum nor the difference of any two is divisible by \latex{ 15 }?

{{exercise_number}}. In the expression \latex{1–2–3–4–5–6–7–…– 2,001} we can give the order of operations by appropriately placing pairs of parentheses. Prove that there are such places for the parentheses which give the same result.

{{exercise_number}}. Is it true that we can always choose some (one, two, three, four or five) numbers out of any five positive whole numbers so that the sum of the chosen numbers is divisible by \latex{5}? Which number can be written instead of \latex{5}?

{{exercise_number}}. Two players write down positive whole numbers in turns on a piece of paper. The player, who can find some numbers – among the numbers on the paper after the opponent write down his/her number – the sum of which is divisible by \latex{5}, wins.

Let us play! Who has a winning strategy, and after at most how many steps is the game finished, if the players pay attention and count correctly?

{{exercise_number}}. Is there a natural number starting with \latex{2,001} which is divisible by \latex{17}?

{{exercise_number}}. Is there a natural number consisting only of digits \latex{0} and \latex{1} which is divisible by \latex{17}?

{{exercise_number}}. We write down the first \latex{100} positive whole numbers on separate pieces of paper and we put these pieces of paper into a hat. Blindfolded and without replacement we draw \latex{55} numbers from the hat. Is it true that there are surely two numbers among the drawn ones the difference of which is exactly \latex{10}? Examine the problem for \latex{11} and then also for \latex{12} instead of \latex{10}.

Puzzle

The seven volumes of an encyclopaedia are on a shelf in the following order: \latex{1; 5; 6; 2; 4; 3; 7}. How can these be put into ascending order if we can grasp three volumes at once and these can moved at once to the left or to the right of the others or between any two but without changing the order of the three? (We can obviously perform this action several times.)

Mathematics 10.

-