Идеи и методы решения нестандартных задач: принцип Дирихле

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

В простейшем виде его выражают так: «Если десять кроликов сидят в девяти ящиках, то в некотором ящике сидят не меньше двух».

Общая формулировка: «Если n кроликов сидят в k ящиках, то найдётся ящик, в котором сидят не меньше чем кроликов, и найдётся ящик, в котором сидят не больше чем кроликов». Пусть вас не смущает дробное число кроликов – в предыдущем случае получается, что в ящике не меньше кроликов, значит, не меньше двух.

Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются.

Допустим, что в каждом ящике сидят меньше чем кроликов. Тогда во всех ящиках вместе кроликов меньше чем · k = n. Противоречие.

Принцип Дирихле кажется очевидным, однако, чтобы его применить, бывает не просто догадаться, что считать кроликами, а что – ящиками.

Зная принцип Дирихле, можно догадаться, в каких случаях его применять. Например, если каждому элементу множества A соответствует ровно один элемент множества B, то элементы A можно назвать кроликами, а элементы B – ящиками.

Принцип Дирихле бывает непрерывным: «Если n кроликов съели m кг травы, то какой-то кролик съел не меньше кг и какой-то съел не больше кг» (а если кто-то съел больше среднего, то кто-то съел меньше среднего).

Заметим, что в последней формулировке кролики играют роль ящиков для травы, а трава – роль кроликов, сидящих в ящиках.

Пример 1. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.

Решение. Всего в году бывает 366 дней. Назовём дни ящиками, а учеников – кроликами. Тогда в некотором ящике сидят не меньше кроликов, т. е. больше одного. Следовательно, не меньше двух.

Можно рассуждать от противного. Допустим, что каждый день отмечают день рождения не больше одного ученика, тогда всего учеников не больше 366. Противоречие.

Пример 2. Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6 × 6 из чисел +1, −1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.

Решение. Допустим, что квадрат составлен. Тогда суммы чисел могут меняться в пределах от −6 до +6. Всего 13 значений. Строк в квадрате 6, столбцов 6, диагоналей 2. Получаем 14 различных сумм. Противоречие, значит составить такой квадрат невозможно.

Пример 3. На Земле океан занимает больше половины площади поверхности. Докажите, что в мировом океане можно указать две диаметрально противоположные точки.

Решение. Отразим океан симметрично относительно центра Земли. Поскольку сумма площадей океана и его образа превышает площадь земной поверхности, то существует точка, принадлежащая океану и его образу. Возьмём эту точку вместе с противоположной к ней.

Пример 4. На собеседование пришли 65 школьников. Им предложили 3 контрольные работы. За каждую контрольную ставилась одна из оценок: 2, 3, 4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на всех контрольных?

Решение. Рассмотрим множество наборов из трёх оценок за соответствующие контрольные. Количество таких наборов равно 4³ или 64 (4 возможности за каждую из трёх контрольных). Поскольку число учащихся больше 64, по принципу Дирихле каким-то двум учащимся соответствует один набор оценок.

Задачи для самостоятельного решения

1. В классе 30 учеников. Во время контрольной работы Петя сделал 13 ошибок, а остальные – меньше. Докажите, что найдутся три ученика, сделавшие одинаковое число ошибок.

2. На Земле больше шести миллиардов жителей, людей старше 150 лет не существует. Докажите, что на Земле есть два человека, родившихся одновременно с точностью до секунды.

3. На плоскости проведено 12 прямых. Докажите, что какие-то две из них образуют угол не больше 15.

4. В ящике лежат носки: 10 чёрных, 10 синих, 10 белых. Какое наименьшее количество носков надо вынуть не глядя, чтобы среди вынутых оказалось два носка
а) одного цвета; б) разных цветов; в) чёрного цвета?

5. На карьере добыли 36 камней. Их веса составляют арифметическую прогрессию: 490 кг, 495 кг, 500 кг, . . . , 665 кг. Можно ли увезти эти камни на семи трёхтонных грузовиках?

6. Какое наименьшее число карточек спортлото «6 из 49» надо купить, чтобы наверняка хоть на одной из них был угадан хоть один номер?

7. Докажите, что среди любых пяти человек есть двое с одинаковым числом знакомых среди этих пяти человек. (Возможно, эти двое ни с кем не знакомы.)

8. Докажите, что из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100.

9. Квадратная таблица (2n+1)×(2n+1) заполнена числами от 1 до 2n+ 1 так, что в каждой строке и в каждом столбце представлены все эти числа. Докажите, что если это расположение симметрично относительно диагонали таблицы, то на этой диагонали тоже представлены все эти числа.

10. В классе 25 человек. Известно, что среди любых трёх из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.

11. Комиссия из 60 человек провела 40 заседаний, причём на каждом присутствовало ровно 10 членов комиссии. Докажите, что какие-то два члена комиссии встречались на её заседаниях по крайней мере дважды.

12. Каждая из 9 прямых разбивает квадрат на два четырёхугольника, площади которых относятся как 2 : 3. Докажите, что по крайней мере три из этих прямых проходят через одну точку.

13. Первоклассник Петя знает только цифру 1. Докажите, что он может написать число, делящееся на 1989.