Тема: Принцип Дирихле и его применение в решении задач на доказательство. Шаравии Бимбажап Алексеевич, 10 класс. Россия, Республика Тыва, г.Кызыл, МБОУ СОШ 12. Руководитель: Донгак Шончалай Хажыт-ооловна – учитель математики МБОУ СОШ 12.

Цель работы: Рассмотреть задачи на доказательство, решаемые с помощью принципа Дирихле. Задачи исследования: 1. Изучить литературные источники о жизни П.Г.Л. Дирихле. 2. Познакомиться с принципом Дирихле для решения задач на доказательство. 3. Выяснить, где еще применяют этот принцип Дирихле. 4. Научиться решать задачи по принципу Дирихле.

1. Введение. Принцип Дирихле - это утверждение, согласно которому в любой совокупности из «N» множеств, содержащих более «n» элементов, есть хотя бы одно множество содержащее не менее двух элементов.

Биография ученого Дирихле Петер Густав Лежен (с учетом этимологии правильнее Дирищле) родился 13 февраля 1805 года в вестфальском г.Дюрине. В 12 лет начал учиться в гимназии в Боне, в 14 лет в Кёльне,(учителем был Георг Ом). В 1827 году -доцент в Бреславе. В 1829 году-работал в Берлине. В годах - профессор Берлинского университета, а после - Гёттингенского университета. В 1831 г. Дирихле женится на Ребекке Мендельсон Бартольди, сестре знаменитого композитора Феликса Мендельсон-Бартольди. Дирихле умер 5 мая 1859 года в Геттингенсе.

ОТКРЫТИИ: Сделал ряд крупных открытий в теории чисел; Создал общую теорию алгебр, единиц в алгебраическом числовом поле. В области математического анализа впервые точно сформулировал и исследовал понятие условной сходимости ряда, дал строгое доказательство возможности разложения в ряд Фурье кусочно-непрерывной и монотонной функций, что послужило обоснованием для многих дальнейших исследований.

2. Принцип Дирихле. Общая формулировка: «Если n кроликов сидят в k ящиках, то найдется ящик, в котором сидят не меньше чем n/k кроликов, и найдется ящик, в котором сидят не больше чем n/k кроликов». Самая популярная формулировка принципа Дирихле звучит так: ФОРМУЛИРОВКА 1. "Если в n клетках сидит n+1 или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца". Заметим, что в роли зайцев могут выступать различные предметы и математические объекты - числа, отрезки, места в таблице и т. д.

ФОРМУЛИРОВКА 2. "При любом отображении множества P, содержащего n+1 элементов, в множество Q, содержащее n элементов, найдутся два элемента множества P, имеющие один и тот же образ".

Пример 1. Докажите, что никакая прямая не может пересекать все три стороны треугольника. Решение: Прямая делит плоскость на две полуплоскости, которые мы назовем «клетками». Три вершины треугольника назовем «кроликами». По принципу Дирихле, «найдется клетка, в которой сидит по крайней мере два кролика», то есть найдутся две вершины, лежащие в одной полуплоскости относительно данной прямой. Сторона, соединяющая эти вершины, не пересекает данную прямую.

Конечно, задача 1, как мы убедились, очевидна, и легко может быть решена без помощи принципа Дирихле. Поэтому, естественно, возникает вопрос: "Для чего тогда нужен принцип Дирихле?" В дальнейшем мы увидим, что некоторые задачи не так очевидны при непосредственном решении, но в то же время достаточно просто решаются при помощи принципа Дирихле. Простота решения в значительной степени зависит от того, насколько удачно будут выбраны «клетки" и «кролики". То есть, при использовании принципа Дирихле необходимо указать, что будет «клеткой", а что - «кроликом".

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

Доказательство: Используя принцип Дирихле, мы должны распределить данные из задачи на «кроликов и клеток», тогда мы увидим, что у нас больше «кроликов» или «клеток». Итак, на голове может быть 0, 1, …, волос - всего вариант. Каждого москвича отнесем к одной из групп в зависимости от количества волос; если 34 москвича с одинаковым количеством волос не найдутся, то это значит, что в любую из созданных групп входит не более 33 человек; тогда всего в Москве живёт не более 33* = < человек по условию. Значит, такие 34 москвича найдутся.

ФОРМУЛИРОВКА 3. "Если nk+1 зайцев размещены в n клетках, то найдутся k+1 зайцев, которые посажены в одну клетку (n, k - натуральные числа)".

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

Решение: Выберем любых двух учеников класса, которые не дружат между собой. (Если таких нет, то все ученики класса дружат между собой, значит, у каждого имеется 24 друга, и задача решена.) Из оставшихся 23 учеников каждый дружит с одним из этих двух, иначе мы имели бы тройку учеников, среди которых не было бы друзей. Тогда у одного из выбранных двух учеников не менее 12 друзей. (23 "зайца" рассажены в двух "клетках".)

3. Практическая часть. Рассмотрим некоторые задачи, которых составил и решил сам. Задача 1. В классе 20 человек. Учитель составляет 17 ячеек, где располагаются фамилии учеников класса. Известно, что в двух ячейках находятся одинаковые фамилии и они не более 3. Доказать, что существуют хотя бы 2 различных совпадающих фамилий.

Доказательство: Здесь «кролики» - ученики класса, «клетки» - число ячеек, в которые помещаются фамилии учеников. Получается, есть 17 клеток для 20 зайцев, так как имеется 2 одинаковых фамилий. В клетку «1» впишем фамилию одного ученика класса, в клетку «2» другого, и так до «17-го». Теперь применим «принцип Дирихле». Оставшиеся три зайца должны войти в 2 различные ячейки, т.к. в некоторую ячейку входят не более трех однофамильцев. Получается в 17 клеток из 20 кроликов, трое обязательно должны поместиться в некоторую клетку, и двое должны поместиться в другую клетку. Докажем утверждение задачи от противного. Предположим, что никаких 3 и 2 учеников не имеют одинаковых фамилий, т. е. в каждую из «клеток» 1, 2, 3, …,17 попало меньше по 2 и 3 одинаковых фамилий. Тогда в каждой из них есть по 1 человеку или отсутствует, значит всего в этих клетках 1*17=17 (учеников). Противоречие.

Использованная литература: et.html et.html Андреев А.А., Горелов Г.Н., Люлев А.И., Савин А.И. "Принцип Дирихле", Самара "Пифагор", 1997 г.

4. Вывод. В результате исследовательской работы мною рассмотрены: формулировка и доказательство принципа Дирихле, определение условий, позволяющих применять этот принцип. И выяснил, что есть множество задач, которые решаются методом «от противного», используя принцип Дирихле. Спасибо за внимание.