Принцип Дирихле
Этот принцип очень часто встречается среди олимпиадных тем и задач, но, как правило, тяжело принимается и осознается ребятами. Давайте обсудим, в чем же он заключается?
Если у вас есть 5 клеток, а кроликов 6, то при расселении кроликов по клеткам где-то обязательно будет тесно. Невозможно рассадить 6 кроликов в 5 клеток так, чтобы в каждой клетке было по 1 жильцу. Кому-то придется жить с соседом.
Формулировки принципа Дирихле в простой и общей форме можно записать следующим образом:
«Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика.»
«Если n+1 элемент разбит на n множеств, то по крайней мере одно множество содержит не менее двух элементов.»
В каких же задачах он встречается?
🐧 Обратные задачи
Известно, что какие-бы 10 человек из класса мы не взяли, среди них обязательно найдется девочка. Сколько может быть мальчиков в таком классе?
Фраза «среди любых 10 найдется девочка» означает, что из мешка с детьми мы не глядя достаем 10 детей и там точно будет девочка. Какое наибольшее количество мальчиков в таком мешке? Мальчиков будет 9 человек, потому что если их будет 10 и нам не повезет, то мы вытащим всех мальчиков, а в условии должна быть 1 девочка. Вариации таких задач на принцип Дирихле часто встречаются на олимпиадах и ставят в тупик учеников.
🐧 Задачи на доказательство
Докажите, что точно найдутся 2 москвича, у которых одинаковое количество волос на голове. При этом в Москве живет 10 миллионов человек, а максимум волос на голове может быть 8 миллионов волосков.
Почему найдется как минимум 2 человека с одинаковым количеством волос? Здесь количество волос — это клетки. В первую клетку садятся люди, у которых 0 волос. Во вторую — все люди, у которых 1 волос, в следующую — все, у кого 2 волоса, и так далее, в последней клетке сидят люди, у которых ровно 8 миллионов волос.
А людей у нас 10 миллионов человек. Мы не можем их рассадить по одному человеку в каждую клетку, где-то точно будет тесно. А значит, найдется хотя бы 2 человека с одинаковым количеством волос на голове. Казалось бы, абсурдная задача на доказательство, но она решается при помощи принципа Дирихле.
🐧 Геометрические задачи
У вас есть квадрат 4 на 4 клетки, в этот квадрат вы произвольным образом кидаете 15 монет. Докажите, что точно найдется такая клетка, в котором нет ни одной монеты.
Здесь такое же рассуждение. Если бы в любом квадрате была монета, то монет было бы 16. А у нас 15 монет, значит в какой-то клетке будет пусто.
Или еще задача. Квадрат 4 на 4 нарисован в узлах сетки точками. Какое наименьшее количество треугольников надо нарисовать, чтобы все точки лежали на сторонах как минимум 1 треугольника.
У нас 16 точек, если бы они все лежали на сторонах одного треугольника, то у нас бы нашлась сторона, на которой лежит минимум 6 точек. А если вы нарисуете и посмотрите, то увидите, что в таком квадрате нет прямой, на которой лежало бы 6 точек.
Итак, задачи на принцип Дирихле встречаются часто и по отдельности, и в составе других задач. Такой вот он популярный и полезный! 💗