Принцип Дирихле в олимпиадных задачах: теория и практика
Принцип Дирихле — один из самых интуитивно понятных, но мощных методов решения логических и комбинаторных задач. В простейшей формулировке он гласит: «Если n+1 кроликов рассадить в n клеток, то хотя бы в одной клетке окажется не менее двух кроликов».
Несмотря на кажущуюся очевидность, применение этого принципа в олимпиадной математике требует навыка правильно определять «кроликов» и «клетки». Рассмотрим классическую задачу: доказать, что в любой компании из 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых. Здесь объектами выступают связи между людьми.
Более сложные вариации принципа Дирихле применяются в теории чисел и геометрии. Например, при доказательстве существования приближений иррациональных чисел рациональными дробями. Важно помнить, что принцип утверждает лишь существование объекта, но не дает алгоритма его поиска (неконструктивное доказательство).
Для успешного решения задач уровня районных и городских олимпиад необходимо отработать этот метод на задачах про раскраски, делимость чисел и покрытие фигур. Часто принцип Дирихле комбинируется с методом «от противного».
Закрепим материал серией упражнений: 1. В классе 30 учеников. Петя сделал в диктанте 13 ошибок, а остальные — меньше. Докажите, что по крайней мере 3 ученика сделали одинаковое количество ошибок (возможно, 0).
