19.19 Принцип Дирихле

Всего при делении на существует различных остатков, а так как чисел , то по принципу Дирихле найдутся числа с одинаковыми остатками, следовательно, их разность будет делиться на .

Разность чисел будет делиться на 5 при условии, что остатки от деления этих чисел на 5 равны. Всего существует пять таких остатков: 0, 1, 2, 3 и 4. По принципу Дирихле (остатки — клетки, числа на доске — кролики) получаем, что найдется хотя бы два числа с одинаковыми остатками от деления на 5.

Если бы монет каждого из четырех типов было не более шести, то всего было бы не более монет, а их 25.

Пусть дни недели — это клетки, а футболисты — кролики. Тогда необходимо разлоджить 11 кроликов по 7 клеткам. Тогда по принципу Дирихле существует хотя бы одна клетка, в которой находится по крайней мере два кролика.

Пусть у нас имеется клетка с номерами от 0 до . Тогда в эти клетки нужно рассадить кроликов-елок. Тогда по принципу Дирихле найдется хотя бы одна клетка, в которой будет по крайней мере два кролика-елки.

У нас имеется 16 клеток, где каждая соответствует возрасту от 20 до 35, и 20 туристов-кроликов, которые требуется рассадить по клеткам. Так как кроликов больше, чем клеток, то по принципу Дирихле найдется хотя бы одна клетка, в которой будет сидеть по крайней мере два кролика.

В 9 кучках, в которых количество шариков попарно различныро, суммарно как минимум шариков, что меньше 44.

Если людей, родившихся в один месяц, не более трех, то всего не более человек.

Пусть все собрали разное количество орехов. Тогда всего собрано не менее орехов, что больше 200.

Всего существует 11 остатков при делении на 11: 0, 1, , 10. Пусть остатки — это клетки, а числа — это кролики. Тогда по принципу Дирихле, так как кроликов больше клеток, найдется хотя бы одна клетка, в которой будет по крайней мере два кролика.

Пусть в компании человек. Тогда у каждого человека имеется от до друзей. Таким образом, количество друзей может принимать различных значений: . Поэтому если бы человек имели различное число друзей, то в компании присутствовало бы по одному человеку, имеющему друзей. С другой стороны, если есть человек, имеющий друга, то он дружит со всеми, следовательно, нет человека, который имеет 0 друзей. Противоречие.

Рассмотрим 1988 степеней двойки. Тогда среди них есть как минимум два числа, имеющие одинаковые остатки при делении на 1987 (так как таких остатков всего — 1987 штук — это 0, 1, , 1986). Следовательно, разность двух найденных чисел с одинаковыми остатками при делении на 1987 делится на 1987.

Разобьем остатки при делении на 100 на 50 групп: , , , , , . Так как чисел больше 50. найдутся два числа, которые попадут в одну группу. Следовательно, либо их сумма (если это первые 49 пар) будет делиться на 100, либо их разность и сумма будет делиться на 50, значит, выражение будет делиться либо на 100, либо на

Сумма трех чисел, каждое из которых может равняться или , может равняться числам — всего семь разных сумм. Следовательно, варианты суммы – это клетки, суммы по строкам, столбцам или диагоналям — кролики. Тогда по принципу Дирихле, расположить 8 кроликов по 7 клеткам можно только таким образом, чтобы по крайней мере в одной клетке было хотя бы два кролика.

Пронумеруем людей от 1 до 100 и разобьем на пары: , , , . Тогда в каждой паре находятся люди, сидящие диаметрально противоположно друг другу. Всего таких пар — 50 штук, а мужчин больше 50. Следовательно, по принципу Дирихле найдутся хотя бы два мужчины, номера которых оказались в одной паре. Значит, они сидят напротив друг друга.

В условии требуется, чтобы значения сумм ( строк, столбцов и две диагонали) были различны. Каждая из этих сумм состоит из слагаемых, принимающих одно из значений , , . Поэтому каждая из сумм принимает целочисленное значение в диапазоне от до . Всего возможных значений сумм — . Поскольку , какие-то две из сумм обязательно принимают равные значения.

а) Действительно, предположим, что в каждой из аудиторий сидят не более двух учеников из этой школы. Но тогда во всех девяти аудиториях сидят не больше таких школьники — противоречие. Значит, в какой-то аудитории сидят по крайней мере три ученика из этой школы.

б) Нет, неверно. Например, все эти школьники могли оказаться в одной аудитории.

Правильный шестиугольник можно разбить на шесть правильных треугольников со стороной 1. Тогда хотя бы в одном из этих треугольников будет лежать две отмеченные точки. Расстояние между ними не будет превосходить стороны треугольника.

Всего существует три различных остатка при делении на 3 — 0, 1 или 2. Так как , то по обобщенномау принципу Дирихле (остатки — это клетки, числа — это кролики) найдется как минимум одна клетка, в которой будет находиться по крайней мере кролика. То есть найдется три числа, имеющие одинаковый остаток при делении на 3. Следовательно, их сумма будет делиться на 3.

а) На каждой грани написано одно из пяти чисел: 0, 1, 2, 3 или 4. Но граней всего шесть, и значит, на некоторых двух гранях будут написаны совпадающие числа.

б) Решение такое же, только на каждой грани написано одно из пяти чисел .